Weekly leetcode - nc9/nc56/nc89/nc126/nc69/nc120

Simple

Niuke Tiba - NC9 The path of a value in a binary tree ( One )

Given a binary tree root And a value sum , Judge whether the sum of node values from root node to leaf node is equal to sum The path of .
1. The problem path is defined as the node passing from the root node of the tree to the leaf node
2. A leaf node is a node that has no children
3. Path can only be from parent node to child node , Cannot from child node to parent node
4. The total number of nodes is n

public class Solution {
    
    /** * * @param root TreeNode class  * @param sum int integer  * @return bool Boolean type  */
    public boolean hasPathSum (TreeNode root, int sum) {
    
         if(root==null){
    
             return false;
         }
         sum = sum - root.val;
         if(root.left==null && root.right==null && sum==0){
    
             return true;
         }
         return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
    }
}

Niuke Tiba - NC56 Palindrome numbers (leetcode-9 Palindrome number )

Determine whether an integer is a palindrome without using additional memory space . Palindrome means that the reverse order and positive order are exactly the same .
Tips ：
Can a negative integer be a palindrome ？（ such as -1）
If you're thinking about converting numbers into strings , Please note the limitation of not using additional space
You can flip integers . however , If you've done a topic “ Reverse the number ”, You will know that there may be overflow when you flip the integer , How do you deal with this problem ？

public class Solution {
    
    /** * * @param x int integer  * @return bool Boolean type  */
    public boolean isPalindrome (int x) {
    
        //  negative ,10,100,1000 This situation 
        if(x<0 || (x%10==0 && x!=0)){
    
            return false;
        }

        //  Reverse this number to see if it is equal to the original number 
        int temp = x;

        int res = 0;
        while (x>0){
    
            res = res*10 + x%10;
            x = x / 10;
        }
        return temp==res;
    }
}

Niuke Tiba - NC89 String deformation

For a length of n character string , We need to deform it .

First of all, the string contains some spaces , It's like "Hello World" equally , Then what we need to do is reverse order the words separated by spaces in this string , Invert the case of each character at the same time .

such as "Hello World" After deformation, it becomes "wORLD hELLO".

Input description ：
Given a string s And its length n(1 ≤ n ≤ 10^6)
Return value description ：
Please return the deformed string . The title ensures that the given string is composed of upper and lower case letters and spaces .

public class Solution {
    
    public String trans(String s, int n) {
    
        Stack<String> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<s.length();i++){
    
            if(s.charAt(i)==' '){
    
                stack.push(sb.toString());
                sb = new StringBuilder();
                stack.push(" ");
                continue;
            }
            sb = sb.append(convert(s.charAt(i)));
        }
        if(sb.length()!=0){
    
            stack.push(sb.toString());
        }
        sb = new StringBuilder();
        while (!stack.isEmpty()){
    
            sb = sb.append(stack.pop());
        }
        return sb.toString();
    }

    private char convert(char dataChar) {
    
        if (Character.isUpperCase(dataChar)) {
    
            dataChar =  Character.toLowerCase(dataChar);
        }else if(Character.isLowerCase(dataChar)){
    
            dataChar = Character.toUpperCase(dataChar);
        }
        return dataChar;
    }
}

Niuke Tiba - NC126 Change money ( One )

Given array arr,arr All values in are positive integers and do not repeat . Each value represents a currency of one denomination , Each denomination of currency can be used in any number of , Give me another one aim, Represents the amount of money to be found , Ask for composition aim The minimum number of currencies . If there is no solution , Please return -1.

public class Solution {
    
    /** *  Minimum number of currencies  * @param arr int Integer one-dimensional array  the array * @param aim int integer  the target * @return int integer  */
    public int minMoney (int[] arr, int aim) {
    
        // write code here
        int[] dp = new int[aim+1];
        for(int i=1;i<=aim;i++){
    
            dp[i] = aim+1;
            for(int j=0;j<arr.length;j++){
    
                if(arr[j]<=i){
    
                    dp[i] = Math.min(dp[i],dp[i-arr[j]]+1);
                }
            }
        }
        return dp[aim]>aim ? -1 : dp[aim];
    }
}

Niuke Tiba - NC69 Last in the list k Nodes

Enter a length of n The linked list of , Set the value of the element in the linked list to ai , Returns the penultimate... In the linked list k Nodes .
If the length of the list is less than k, Please return a length of 0 The linked list of .

public class Solution {
    
    /** *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly  * * * @param pHead ListNode class  * @param k int integer  * @return ListNode class  */
    public ListNode FindKthToTail (ListNode pHead, int k) {
    
        // write code here
        if(pHead==null || k<0){
    
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        for(int i=0;i<k;i++){
    
            if(fast==null){
    
                return null;
            }
            fast = fast.next;
        }
        while (fast!=null){
    
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

Niuke Tiba - NC120 Binary 1 The number of （leetcode-191 position 1 The number of ）

Enter an integer n , Output the number 32 In bit binary representation 1 The number of . Negative numbers are represented by complements .

public class Solution {
    
    public int NumberOf1(int n) {
    
        int res = 0;
        while (n!=0){
    
        	// 0010 & 0001  Determine whether the last digit is 1
            res = res + (n&1);
            //  Move one unsigned right 
            n = n>>>1;
        }
        return res;
    }
}