Sword finger offer (simple level)

(1) Fibonacci sequence

(2) Repeated numbers in an array

describe

At a length of n All in the array of The numbers are all there 0 To n-1 Within the scope of . Some numbers in the array are repeated , But I don't know how many numbers are repeated . I don't know how many times each number is repeated . Please find any duplicate number in the array . for example , If the input length is 7 Array of [2,3,1,0,2,5,3], Then the corresponding output is 2 perhaps 3. If there is illegal input, output -1

Data range ：0≤n≤10000 0≤n≤10000

Advanced ： Time complexity O(n) O(n) , Spatial complexity O(n) O(n)

Breakthrough point of thinking ： The data are all there 0～n-1 Within the scope of , That is, if there is no repetition, the corresponding value of each position can be its subscript

from 0 The subscript begins to look for index = 0

        1、 If the subscript is different from the currently stored value , Change the value to the corresponding position .

                 If there is already a matching value in this position, there will be duplicates , return ; Otherwise exchange

        2、 If the subscript is the same as the currently stored value , be index++

(3) Replace blank space

(4) Print linked list from end to end

Output with required order can often be considered in combination with stack queue

Note that the object is null Is to return is null, Or some object with no content .

(5) Queues are implemented with two stacks

(6) Minimum number of rotation array

There is a length of n Of Non descending array , such as [1,2,3,4,5], Rotate it , That is, move the first elements of an array to the end of the array , Into a rotating array , For example, it became [3,4,5,1,2], perhaps [4,5,1,2,3] In this way . Excuse me, , Given such a rotation array , Find the minimum value in the array .

Data range ：1≤n≤100001≤n≤10000, The value of any element in the array : 0≤val≤100000≤val≤10000

requirement ： Spatial complexity ：O(1)O(1) , Time complexity ：O(logn)O(logn)

Fully understand the difference between these words ：

If it conforms to a(n+1)>an, Then the number sequence is increasing , It is also in ascending order
If it conforms to a(n+1)<an, Then the decreasing of the sequence , It is also in descending order
If it conforms to a(n+1)≤an, Then the sequence is non ascending
If it conforms to a(n+1)≥an, Then the sequence is not in descending order

So the array AB Rotation array of BA It has the following characteristics ：B Is not in descending order ,A Is not in descending order . The minimum value is A The first number of .

Use dichotomy , determine min stay mid Left or right

Only with right or left Comparison confirms min The approximate location of

Pay attention to the handling of both cases ：1、mid Less than right or left, here min May be in mid Left or mid It's about , Should be right=mid

2、mid The value is equal to right value ,right Minus one

(7) Binary 1 The number of

There are two simple methods involved here

1、n&（1<<i）eg use n And 001 And whether the first place is 1

                              use n And 010 And whether the second place is 1

                            ......

                              use n And 1000 0000 0000 0000 ... 0000 Get the first 32 Whether a is 1

2 n&=（n-1） Each time will be n The lowest point of 1 Reverse into 0 And n Progress and . Remember a 1

                        if n Change into 0 Description none 0, Can end .

(8) Print from 1 To the biggest n digit ​​​​​​​

(9) Delete the node of the linked list

(10) Last in the list k Nodes

(11) Reverse a linked list

Note that the linked list is empty , Return to linked list directly .

(12) Merge two ordered linked lists

(13) Image of binary tree

The essence here is to exchange the left and right subtrees of each node

1、 If recursion is used , Be careful not to store the changed nodes in advance

2、 If stack is used , You just need to stack the left and right nodes in turn , Switch the left and right nodes when bouncing the stack .

(14) Symmetric binary tree ​​​​​​​( Ideas )

Pay attention to where to compare , How to compare .

1. Recursive implementation ： Two pointers start from the same starting point .

public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        return isSym(pRoot,pRoot);
    }
    boolean isSym(TreeNode root1,TreeNode root2){
        if(root1==null&&root2==null)
            return true;
        if(root1==null||root2==null||root1.val!=root2.val)
            return false;
        return isSym(root1.left,root2.right)&&isSym(root1.right,root2.left);
    }
    
}

2、 thought ： Using middle order traversal , If it is symmetric, the result is the same as that of left middle right and right middle left .

import java.util.*;
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot==null)
            return true;
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        queue1.add(pRoot);
        queue2.add(pRoot);
        while(!queue1.isEmpty()&&!queue2.isEmpty()){
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            // Note the handling of the two conditions here 
            if(node1==null&&node2==null)
                continue;
            if(node1==null||node2==null||node1.val!=node2.val)
                return false;
         
            queue1.add(node1.left);
            queue1.add(node1.right);

            queue2.add(node2.right);
            queue2.add(node2.left);

        }
        return true;
    }
}

（15） Print matrix clockwise  

  Pay attention to up and down , It is possible for left and right to repeat the record . Therefore, it is necessary to judge whether it has been recorded .

 public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> array = new ArrayList<Integer>();
        int r = matrix.length;
        int c = matrix[0].length;
        int ccount = (r<c)?r:c;
        ccount = ccount/2+ccount%2;
        for(int i=0;i<ccount;i++){
            int r1 = i,r2 = r - i -1;
            int c1 = c-i-1,c2 = i;
            for(int l1 = i;l1 < c-i;l1++)
                array.add(matrix[r1][l1]);
            for(int l2 = i+1;l2<r-i-1;l2++)
                array.add(matrix[l2][c1]);
            if(r2!=r1)
                for(int l3 = c-i-1;l3 >= i;l3--)
                    array.add(matrix[r2][l3]);
            if(c2!=c1)
                for(int l4 = r-i-2;l4>i;l4--)
                    array.add(matrix[l4][c2]);
            
        }
        return array;
    
    }

（16） contain min Function of the stack  

thought ： Another stack to store the minimum value currently stored in the stack .

(17) Print binary tree from top to bottom

Recursion not completed

(18) A number that appears more than half the times in an array

(19) The maximum sum of successive subarrays

My own way of thinking ： There may be cases where the maximum value is negative .

                        initialization ：sum = 0 ,max = Integer.MIN_VALUE

Every time sum+ After the operation ：1、 Compare whether it is greater than max, Is an update max.

                                        2、sum Is less than 0, Less than 0 Will sum Reset 0. Because at this time sum Negative , Should start over , Otherwise, the value after negative addition will make it smaller .                                        

（20） A number in a sequence of numbers

 public int findNthDigit (int n) {
        if(n==0)
            return 0;
        int digit = 1;
        // Be careful ： More than... Will occur during the calculation int So the two numbers are long
        long start = 1;
        long sum = 9;
        /*
         Calculate the total number of digits in the current digit range 
         If it is greater than, the total number of current digits will be subtracted , Keep looking for 
         If it is less than, calculate first , Numbers 
         Convert numbers to strings 
         Then calculate which one of them 
        */
        while(n>sum){
            n -= sum;
            digit++;
            start*=10;
            sum = digit*(start*10-start);
        }
        int num = (int)start+(n/digit)-1;
        String numStr = Integer.toString(num);
        int index = (n+digit-1)%digit;
        return numStr.charAt(index)-'0';// Note that the final destination is an integer 
        
    }

(21) The first character that appears only once

problem ： How to find the first non repeating character in the dictionary . As long as you traverse through the input string, the first non repeating character you encounter is the first non repeating character .

(22) The first common node of two linked lists

There's a simple way ：

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if( pHead1==null || pHead2 == null)
            return null;
        ListNode p1=pHead1;
        ListNode p2=pHead2;
        while(p1!=p2){
            p1 = (p1==null)?pHead2:p1.next;
            p2 = (p2==null)?pHead1:p2.next;
        }
        return p1;
    }

（23）  The number of times a number appears in an ascending array

Here are two points to note

A special case [3]4

[3,3,3,3]4

 public int GetNumberOfK(int [] array , int k) {
        
        int start = 0;
        int end = array.length-1;
        while(start<end&&(array[start]!=k||array[end]!=k)){
            int mid = (start+end)/2;
            if(array[mid]<k){
                // A kind of mid When copying, pay attention to mid The value has excluded the use of mid+1 or mid-1 Otherwise, you may fall into an infinite loop 
                start = mid+1;
            }
            else if(array[mid]>k)
                end=mid-1;
            else{
                if(array[start]!=k)
                    start++;
                if(array[end]!=k)
                    end--;
            }
        }
        // Possible [2]4 start=0 end=0  The result should be 0 The situation of 
        if(start<=end&&array[start]==k&&array[end]==k)
            return end-start+1;
        else
            return 0;
    }

(24)  The depth of the binary tree

Using recursion , The code I have completed is not as simple as the following ：

public int TreeDepth(TreeNode root) {
        if(root == null)
            return 0;
        return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
    }

Use queue assist to complete

 public int TreeDepth(TreeNode root) {
        if(root==null)
            return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int depth = 0;
        while(!queue.isEmpty()){
            // It can be used size() To get how many elements are in the current queue 
            int levesum = queue.size();
            while(levesum>0){
                TreeNode node = queue.poll();
                if(node.left!=null)
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
                levesum--;
            }
            depth++;
        }
        return depth;
    }

（25） Playing card shunzi  

When we consider the problem, we ignore the case that there are equal values . If there is an equal value, it will fail directly .

Simple thinking , Similar to repeated numbers in an array .

Have equal values directly false, Get rid of 0 Record the maximum and minimum values . If the difference is less than 5 The explanation is shunzi （ That is, the incoherent place must be 0 fill , Because other numbers are between these two numbers , If it is not between , Only for 0）.

 public boolean IsContinuous(int [] numbers) {
        Set<Integer> set = new HashSet();
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = 0;i<numbers.length;i++){
            if(numbers[i] == 0)
                continue;
            else{
                if(set.contains(numbers[i]))
                    return false;
                else{
                    set.add(numbers[i]);
                    if(numbers[i]>max)
                        max=numbers[i];
                    if(numbers[i]<min)
                        min=numbers[i];
                }
            }
        }
        return max-min<5;
    }

(26) The best time to buy and sell stocks ( One )

Another way of thinking , Don't look for the maximum value after the change , Or you'll have to recalculate every time .

Turn to , Record the minimum value before the change , Subtract the previous minimum price from this point , This is the maximum revenue from the sale of this place （ minimum value , It can be updated in time during the convenient process from left to right , It takes the shortest time ）

public int maxProfit (int[] prices) {
        // write code here
        if(prices.length==0)
            return 0;
        int min = prices[0];
        int max = 0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]<min)
                min = prices[i];
            if(prices[i]-min>max)
                max = prices[i]-min;
        }
        return max;
    }

（27） Do not add, subtract, multiply or divide ​​​​​​​

A bit operation tips ：num1 Exclusive or num2（num1^num2） Is the number on each bit before carry .

                                       num1 And num2（num1&num2） Whether each bit should be carried up , So move one bit to the left （<<） Then or gets the carry on each bit

1、 When carry is not 0 Always cycle through

2、 When carry is 0 The calculation will be stopped .

 public int Add(int num1,int num2) {
        int add = num2;
        while(add!=0){
            int sum = num1^add;
            add = (num1&add)<<1;
            num1 = sum;
        }
        return num1;
        
    }

(28) Building a product array

A simple idea

Complete in two cycles

Calculate the triangle at once , From the top down , From left to right . One more number each time

Calculate the triangle at once , From bottom to top , From right to left . One more number each time

public int[] multiply(int[] A) {
        int[] B = new int[A.length];
        B[0] = 1;
        for(int i = 1;i<A.length;i++){
            B[i] = B[i-1]*A[i-1];
        }
        int sum = 1;
        for(int i=A.length-2;i>=0;i--){
            sum*=A[i+1];
            B[i]*=sum;
        }
        return B;
    }

(29)  The nearest common ancestor of a binary search tree

Ideas ：

1、 Non recursive ：

public int lowestCommonAncestor (TreeNode root, int p, int q) {
       if(root == null)
            return -1;
        ArrayList<Integer> route1 = new ArrayList();
        ArrayList<Integer> route2 = new ArrayList();
        TreeNode t1 = root;
        TreeNode t2 = root;
        while(t1!=null&&t1.val!=p){
            route1.add(t1.val);
            if(t1.val<p)
                t1 = t1.right;
            else
                t1 = t1.left;
        }
        if(t1==null)
            return -1;
        else
            route1.add(t1.val);
        while(t2!=null&&t2.val!=q){
            route2.add(t2.val);
            if(t2.val<q)
                t2 = t2.right;
            else
                t2 = t2.left;
        }
        if(t2==null)
            return -1;
        else
            route2.add(t2.val);
        int conroot = -1;
        for(int i = 0;i<route1.size()&&i<route2.size();i++){
            int x = route1.get(i);
            int y = route2.get(i);
            if(x == y)
            conroot = route1.get(i);
        }
        return conroot;
    }

 2、 Recursive version

if p,q On both sides of the current node （ Included on this node ）, Then this node is the nearest public follow .

if p,q On the same side , Recurse to this side

public int lowestCommonAncestor (TreeNode root, int p, int q) {
        if(root==null)
           return -1;
        if(root.val>=p&&root.val<=q||root.val<=p&&root.val>=q)
            return root.val;
        if(root.val<p&&root.val<q)
            return lowestCommonAncestor(root.right,p,q);
        return lowestCommonAncestor(root.left,p,q);
    }

(30) Skip step  

(31) Step jump expansion problem

The idea of simplification ：

(n)=f(n−1)+f(n−2)+...+f(n−(n−1))+f(n−n)=f(0)+f(1)+f(2)+...+f(n−1), because f(n−1)=f(n−2)+f(n−3)+...+f((n−1)−(n−2))+f((n−1)−(n−1))f(n−1)=f(n−2)+f(n−3)+...+f((n−1)−(n−2))+f((n−1)−(n−1)), After sorting it out f(n)=f(n−1)+f(n−1)=2∗f(n−1)f(n)=f(n−1)+f(n−1)=2∗f(n−1)

(32)  Flip the word sequence

Division + In reverse order

Don't forget to add spaces when reconstituting strings in reverse order .

(34) Judge whether it is a balanced binary tree

1. A function does

It is easy to make mistakes in the early stage of thinking ： Nodes with empty left and right words are 1 layer , Rather than ascend the throne 0

  public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null)
            return true;
        if(root.left==null&&root.right==null)
        {
            // This should be counted as a layer , Empty nodes with nothing are 0
            root.val = 1;
            return true;
        }
        boolean left=true,right=true;
        int dleft=0,dright=0;
        if(root.left!=null){
            left = IsBalanced_Solution(root.left);
            dleft = root.left.val;
        }
        else
            dleft = 0;
            
        if(root.right!=null){
            right = IsBalanced_Solution(root.right);
            dright = root.right.val;
        }
        else
            dright = 0;
        root.val = ((dright<dleft)?dleft:dright)+1;
        if(left&&right){
            if(Math.abs(dleft-dright)<=1)
                return true;
            return false;
        }
        return false;
    }

2、 This can be done with two functions

use -1 Represents that this node is unbalanced .

Therefore, if the return is -1, Direct delivery -1 Indicates that this branch is unbalanced

public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null)
            return true;
        return DeepPath(root)!= -1;
       
    }
    public int DeepPath(TreeNode root){
        if(root == null)
            return 0;
        int left = DeepPath(root.left);
        if(left == -1)
            return -1;
        int right = DeepPath(root.right);
        if(right == -1)
            return -1; 
        return Math.abs(left-right) > 1 ? -1:1+Math.max(left,right);
    }

(35) Adjust the array order so that the odd Numbers precede the even Numbers ( Two )​​​​​​​

(36) The path of a value in a binary tree ( One )

A simpler idea of recursive implementation ： Each time sum The residual value of is compared with the median value of the leaf node

public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root == null)
            return false;
        if(root.left==null&&root.right==null&&sum==root.val)
            return true;
        sum -= root.val;
        return hasPathSum(root.left,sum)||hasPathSum(root.right,sum);
    }

Non recursive ： The value of each node is changed to the length from the root node to this node （ You just need to go through the sequence first ）

     if(root==null)
            return false;
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node.left==null&&node.right==null&&node.val == sum)
                return true;
            if(node.left!=null)
            {
                node.left.val += node.val;
                stack.push(node.left);
            }
            if(node.right!=null){
                node.right.val += node.val;
                stack.push(node.right);
            }
        }
        return false;
    }