Daily question brushing record (XIV)

The first question is : The finger of the sword Offer 62. The last number in the circle

LeetCode: The finger of the sword Offer 62. The last number in the circle

describe :
0,1,···,n-1 this n Number in a circle , From numbers 0 Start , Delete the... From this circle every time m A digital （ Delete and count from the next number ）. Find the last number left in the circle .

for example ,0、1、2、3、4 this 5 Numbers make a circle , From numbers 0 Start deleting the 3 A digital , Before deleting 4 The numbers in turn are 2、0、4、1, So the last remaining number is 3.

Their thinking :

1. Here we use mathematical thinking
2. for the first time When deleting , 0 1 2 3 4, Delete 2
3. The second time When deleting , 3 4 0 1 , Delete 0
4. third time When deleting , 1 3 4 , Delete 4
5. The fourth time When deleting , 1 3 , Delete 1
6. The fifth time There is no need to delete , 3, return 3
    
   Here you can use reverse push ,
   For example, in the fifth time , The initial position subscript position is 0 , To know the subscript position of the fourth time , adopt index = (index + m) % i, Here is index Is the current subscript , m Is the deleted subscript , i Is the number of times from back to front ( For example, the fourth time here , The opposite is the second time ).
   So calculate the subscript to get index = (0 + 3) % 2 = 1 , So at the fourth time , Finally, the remaining subscripts are 1
   

Code implementation :

class Solution {
    
    public int lastRemaining(int n, int m) {
    
    	//  The last remaining elements ,  The subscript can only be 0
        int index = 0;
        for (int i = 2; i <= n; i++) {
    
        	//  The last coordinate position can be obtained by mathematical backward deduction 
            index = (index + m) % i;
        }
        //  Calculate the initial time ,  Subscript location 
        return index;
    }
}

The second question is : The finger of the sword Offer 63. The biggest profit of stocks

LeetCode: The finger of the sword Offer 63. The biggest profit of stocks

describe :
Suppose you store the price of a stock in an array in chronological order , What's the maximum profit you can get from buying and selling this stock at one time ？

Their thinking :

1. The initial conditions , Give Way min = prices[0], Record the maximum max
2. Traversal array ,
3. If at present prices[i] Greater than min, Record the maximum , max = Math.max(max, prices[i] - min)
4. If at present prices[i] Less than min, Just replace min

Code implementation :

class Solution {
    
    public int maxProfit(int[] prices) {
    
        if(prices.length == 0) return 0;
        int min = prices[0];
        int max = 0;
        for(int price : prices) {
    
            if (min > price) {
    
                min = price;
            }else{
    
                max = Math.max(max,price-min);
            }
        }
        return max;
    }
}

Third question : The finger of the sword Offer 64. seek 1+2+…+n

LeetCode: The finger of the sword Offer 64. seek 1+2+…+n

describe :
seek 1+2+...+n, It is required that multiplication and division shall not be used 、for、while、if、else、switch、case Wait for keywords and conditional statements （A?B:C）.

Their thinking :

1. Because it can't be used for loop
2. Here we use recursion to evaluate
3. utilize boolean flg = (A) && (B), here If A by false End recursion . therefore A Play a if effect , B Play a for effect

Code implementation :

class Solution {
    
    public int sumNums(int n) {
    
        boolean flg = n > 0 && (n += sumNums(n - 1)) >0;
        return n;
    }
}

Fourth question : The finger of the sword Offer 66. Building a product array

LeetCode: The finger of the sword Offer 66. Building a product array

describe :
Given an array A[0,1,…,n-1], Please build an array B[0,1,…,n-1], among B[i] Is the value of an array A In addition to subscript i The product of other elements , namely B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]. Division cannot be used .

Their thinking :

1. Because division cannot be used , You can't get rid of yourself here
2. First multiply it from left to right , Every time I can't be myself
3. Multiply again from right , Every time I can't be myself
   

Code implementation :

class Solution {
    
    public int[] constructArr(int[] a) {
    
        int[] res = new int[a.length];
        int ret = 1;
        for(int i = 0; i < a.length; i++) {
    
            res[i] = ret;
            ret *= a[i];
        }
        ret = 1;
        for(int i = a.length-1; i >=0 ; i--) {
    
            res[i] *= ret;
            ret *= a[i];
        }
        return res;
    }
}

Fifth question : The finger of the sword Offer 67. Convert a string to an integer

LeetCode: The finger of the sword Offer 67. Convert a string to an integer
describe :
Write a function StrToInt, Realize the function of converting string to integer . Out of commission atoi Or other similar library functions .

First , This function discards the useless start space characters as needed , Until the first non space character is found .

When the first non empty character we find is a positive or negative sign , Then combine the symbol with as many consecutive numbers as possible on the back face , As the sign of the integer ; If the first non empty character is a number , Then combine it directly with the following consecutive numeric characters , Form an integer .

In addition to the valid integer part of the string, there may be extra characters , These characters can be ignored , They should have no effect on functions .

Be careful ： If the first non space character in the string is not a valid integer character 、 When the string is empty or the string contains only white space characters , Then your function doesn't need to be converted .

In any case , If the function cannot be effectively converted , Please return 0.

explain :
Suppose our environment can only store 32 A signed integer of bit size , So the value range is [−231, 231 − 1]. If the value exceeds this range , Please return INT_MAX (231 − 1) or INT_MIN (−231) .

Their thinking :

1. First, remove the spaces before and after
2. Then judge whether the current is empty , It may be free after removal
3. Judge the first character , Is it a number , Or is it a symbol , If it's not a direct return 0
4. If the first character is a minus sign , Record the current symbol
5. Cycle the current numeric characters ,
6. Use one long Type to calculate the current number size
   • If the current number is greater than Integer.MAX_VALUE , And the symbol is positive , return Integer.MAX_VALUE
   • If the current number is greater than Integer.MAX_VALUE , And the sign is negative , return Integer.MIN_VALUE
7. If the cycle ends , Not more than Integer.MAX_VALUE, Returns the current res, A positive sign returns res, Negative sign return -res

Code implementation :

class Solution {
    
    public int strToInt(String str) {
    
        str = str.trim();
        int index = 0;
        if(index>=str.length()) return 0;
        if(!Character.isDigit(str.charAt(0)) && str.charAt(0)!='-' && str.charAt(0)!='+'){
    
            return 0;
        }
        int flg = 1;
        if(str.charAt(0) == '-'){
    
            flg = -1;
            index++;
        }else if(str.charAt(0) == '+'){
    
            index++;
        }
        long res = 0;
        while(index < str.length() && Character.isDigit(str.charAt(index))){
    
            res = res * 10 + str.charAt(index)-'0';
            if(res > Integer.MAX_VALUE && flg == 1){
    
                return Integer.MAX_VALUE;
            }else if (res > Integer.MAX_VALUE && flg == -1) {
    
                return Integer.MIN_VALUE;
            }
            index++;
        }
        res = flg==1?res:-res;
        return (int)res;
    }
}

Sixth question : The finger of the sword Offer 68 - I. The nearest common ancestor of a binary search tree

LeetCode: The finger of the sword Offer 68 - I. The nearest common ancestor of a binary search tree

describe :
Given a binary search tree , Find the nearest common ancestor of the two specified nodes in the tree .

In Baidu Encyclopedia, the most recent definition of public ancestor is ：“ For a tree T Two nodes of p、q, Recently, the common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible （ A node can also be its own ancestor ）.”

for example , Given the following binary search tree : root = [6,2,8,0,4,7,9,null,null,3,5]

Their thinking :

Pay attention to several situations here .

1. root by Empty When , Go straight back to null
2. If at present root The value of the node , Greater than p Value , And Greater than q Value , Then it's in the left subtree .
3. If at present root The value of the node , Less than p Value , And Less than q Value , So it's in the right subtree .
4. No , p , q On the left and right , Or the root node , Go straight back to root

Code implementation :

class Solution {
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        if(root == null) return null;
        if(root.val > p.val && root.val > q.val) {
    
            return lowestCommonAncestor(root.left,p,q);
        }else if(root.val < p.val && root.val < q.val) {
    
            return lowestCommonAncestor(root.right,p,q);
        }else{
    
            return root;
        }
    }
}