Leetcode brushes questions the next day

1. Print linked list from end to end

Enter the head node of a linked list , Return the value of each node from the end to the end （ Return with array ）.

analysis ：

Build a stack , First press each node in the linked list into the stack , Stack and print the value of each node .

class Solution {
    public int[] reversePrint(ListNode head) {
        LinkedList<Integer> stack = new LinkedList<Integer>();
        while(head != null) {
            stack.addLast(head.val);
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for(int i = 0; i < res.length; i++)
            res[i] = stack.removeLast();
    return res;
    }
}

2. Reconstruction of binary tree

Enter the results of preorder traversal and inorder traversal of a binary tree , Build the binary tree and return its root node .

It is assumed that the results of the input preorder traversal and the middle order traversal do not contain repeated numbers .

analysis ：

The order of preorder traversal ： The root node - The left subtree - Right subtree

The order in which the order is traversed ： The left subtree - The root node - Right subtree

It can be seen that the first node of the preorder traversal must be the root node , According to this point and the characteristics of middle order traversal, we can judge which endpoints the left subtree has , What are the endpoints of the right subtree , Thus, the root node of the left subtree and the root node of the right subtree can be determined . According to this characteristic , Divide and conquer algorithm can be used .

Analysis of divide and conquer algorithm ：

1. Recursive parameter ： Index traversed by the root node in the preorder root 、 The left boundary of the subtree traversal in the middle order left 、 The subtree traverses the right boundary of the middle order right ;
2.   Termination conditions ： When left > right , Represents that you have crossed the leaf node , Return at this time null ;
3. Recursive work ： Establish root node node ： The node value is preorder[root] ; Divide the left and right subtrees ： Find the root node in the order traversal inorder Index in i ; To improve efficiency , This article uses hash table dic The mapping between the value of the order traversal and the index in the storage , The time complexity of the lookup operation is O(1)O(1) ;
4. Construct left and right subtrees ： Turn on left and right subtree recursion ;
5. Return value ： Backtracking return node , As the left node of the root node in the upper recursion / The right child node ;

class Solution {
    int[] preorder;
    HashMap<Integer, Integer> dic = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0; i < inorder.length; i++)
            dic.put(inorder[i], i);
        return recur(0, 0, inorder.length - 1);
    }
    TreeNode recur(int root, int left, int right) {
        if(left > right) return null;                          //  Recursive termination 
        TreeNode node = new TreeNode(preorder[root]);          //  Establish root node 
        int i = dic.get(preorder[root]);                       //  Partition root node 、 The left subtree 、 Right subtree 
        node.left = recur(root + 1, left, i - 1);              //  Turn on left subtree recursion 
        node.right = recur(root + i - left + 1, i + 1, right); //  Turn on right subtree recursion 
        return node;                                           //  Backtracking returns the root node 
    }
}

3. Queues are implemented with two stacks

Use two stacks to implement a queue . The declaration of the queue is as follows , Please implement its two functions appendTail and deleteHead , The functions of inserting integers at the end of the queue and deleting integers at the head of the queue are respectively completed .( If there are no elements in the queue ,deleteHead  Operation return -1 ).

analysis ：

Set up two stacks , One is input stack , One is output stack .

class CQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public CQueue() {
        inStack = new ArrayDeque<Integer>();
        outStack = new ArrayDeque<Integer>();
    }

    public void appendTail(int value) {
        inStack.push(value);
    }

    public int deleteHead() {
        if (outStack.isEmpty()) {
            if (inStack.isEmpty()) {
                return -1;
            }
            in2out();
        }
        return outStack.pop();
    }

    private void in2out() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

4. Fibonacci sequence

Write a function , Input n , Fibonacci, please （Fibonacci） The number of the sequence n term （ namely F(N)）. Fibonacci series is defined as follows ：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), among N > 1.
The Fibonacci series is composed of 0 and 1 Start , The Fibonacci number after that is the sum of the two numbers before .

The answer needs to be modelled 1e9+7（1000000007）, If the initial result of calculation is ：1000000008, Please return 1.

analysis ：

Recursion will time out （ There will be a lot of double counting ）. Adopt dynamic programming to solve .

Dynamic planning analysis ：

1. State definition ： set up dp  It's a one-dimensional array , among dp[i] The value of represents Fibonacci number one i A digital .
2. Transfer equation ： dp[i + 1] = dp[i] + dp[i - 1], That is, the definition of the corresponding sequence f(n + 1) = f(n) + f(n - 1) ;
3. The initial state ： dp[0] = 0, dp[1] = 1 , That is, initialize the first two numbers ;
4. Return value ： dp[n] , That is, the second of the Fibonacci sequence n  A digital .

class Solution {
    public int fib(int n) {
        int a = 0, b = 1, sum;
        for(int i = 0; i < n; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}

5. The problem of frog jumping on the steps

A frog can jump up at a time 1 Stepped steps , You can jump on it 2 Stepped steps . Ask the frog to jump on one n  How many jumps are there in the steps .

The answer needs to be modelled 1e9+7（1000000007）, If the initial result of calculation is ：1000000008, Please return 1.

analysis ：

The law is consistent with Fibonacci sequence , namely  f(n)=f(n-1)+f(n-2).

class Solution {
    public int numWays(int n) {
        int a = 1, b = 1, sum;
        for(int i = 0; i < n; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}