428.LeetCode

428.LeetCode

Full array

Given a sequence without repeated numbers, return all possible permutations.

Backtracking

Backtracking: An algorithm that finds all solutions by exploring all possible candidate solutions. If the candidate solution is confirmed to be not a solution (or at least not the last solution), the backtracking algorithm will discard the solution by making some changes in the previous step, that is, backtracking and try again. Recursive functions are divided into two cases:

in case first==n\textit{first}==n , it means we have filled innn positions (note that the subscript starts from 0), a feasible solution is found, we willoutput\textit{output} put into the answer array, and the recursion ends.

in case first<n\textit{first}<n , we have to consider thisfirst\textit{first}Which number do we need to fill in the position. According to the requirements of the title, we must not fill in the numbers that have already been filled, so an easy way to think of is that we define a tag arrayvis[]\textit{vis}[] to mark the number that has been filled in, then fill in thefirst\textit{first} number, we traverse the nn numbers given by the title. If this number has not been marked, we try to fill it in, mark it, and continue to try to fill in the next position, that is, call the functionbacktrack(first+1,output)backtrack(first + 1, output) . When backtracking, you need to cancel the number and mark in this position, and continue to try other unmarked numbers.

We can assign the n number array given by the title nums\textit{nums} divided into left and right parts. The left part represents the number that has been filled in, and the right represents the number to be filled. We only need to dynamically maintain this array when backtracking.

Specifically, suppose we have filled in first\textit{first} position, thennums\textit{nums} array[0,first 1][0,\textit{first}-1] is the set of numbers that have been filled in,[first,n 1][\textit{first},n-1] is the set of numbers to be filled. We must try to use[first,n 1][\textit{first},n-1] to fill in the number infirst\textit{first} number, assuming that the subscript of the number to be filled isii , then after filling in, we willii number of and thefirst\textit{first}Exchange the number, which can make thefirst+1\textit{first}+1 countnums\textit{nums} array[0,first][0,first] is the number that has been filled in,[first+1,n 1][\textit{first}+1,n-1] is the number to be filled, and the undo operation can be completed by swapping it back when backtracking.

class Solution{ public List<List<Integer>> permute(int[] nums){ List<List<Integer>> res = new ArrayList<List<Integer>>(); List<Integer> output = new ArrayList<Integer>(): for(int num: nums){ output.add(num); } int n = nums.length; backtrack(n,output,res,0); return res; } public void backtrack(int n, List<Integer> output,List<List<Integer>> res,int first){ if(first == n){ res.add(new ArrayList<Integer>(output)); } for(int i = first; i<n;i++){ Collection.swap(output,first,i); backtrack(n,output,res,first+1); Collection.swap(output,first,i); } } } Copy code

time complexity:O(n n!)O(n/times n!) , where n is the length of the sequence. The complexity of the algorithm is first restricted by the number of backtrack calls. The number of backtrack calls is k=1nP(n,k)/sum_{k = 1}^{n}{P(n, k)} times, whereP(n,k)=n!(n k)!=n(n 1)...(n k+1) P(n, k) =/frac{n!}{(n-k)!} = n (n-1) ... (n-k + 1) , this formula is called the k-permutation of n, or partial permutation.

and k=1nP(n,k)=n!+n!1!+n!2!+n!3!+...+n!(n 1)!<2n!+n!2+n!22+n!2n 2<3n!/sum_{k = 1}^{n}{P(n, k)} = n! +/frac{n!}{1!} +/frac{n!}{2!} +/frac{n! }{3!} + ... +/frac{n!}{(n-1)!} <2n! +/frac{n!}{2} +/frac{n!}{2^2} +/frac{n!}{2^{n-2}} <3n! This shows that the number of backtrack calls is O(n!).

For each leaf node called by backtrack (n! total), we need to copy the current answer using O(n) time to the answer array, and the time complexity is multiplied by O(n n!)O(n/times n!) .

So the time complexity is O(n n!)O(n/times n!) .

Space complexity: O(n), where n is the length of the sequence. In addition to the answer array, the recursive function needs to allocate stack space for each layer of recursive function during the recursion process, so extra space is needed here and the space depends on the depth of the recursion. Here we can see that the recursive call depth is O(n).

In-order traversal of binary tree

Given the root node root of a binary tree, return its mid-order traversal.

Method 1: Recursion

definition inorder(root)inorder(root) represents the current traverse toroot\textit{root}The answer of the node, then by definition, we only need to call recursivelyinorder(root.left)inorder(root.left) to traverseroot\textit{root}the left subtree of the node, and thenroot\textit{root}Add the value of the node to the answer, and then recursively callinorder(root.right)inorder(root.right) to traverseroot\textit{root}The right subtree of the node is sufficient, and the condition for recursive termination is to encounter an empty node.

var inorderTraversal = function(root){ const res = []; const inorder = (root) =>{ if(!root){ return; } inorder(root.left); res.push(root.val); inorder(root.right); } inorder(root); return res; }; Copy code

Time complexity: O(n), where n is the number of binary tree nodes. In the traversal of the binary tree, each node will be visited once and only once.

Space complexity: O(n). The space complexity depends on the recursive stack depth, and the stack depth will reach the level of O(n) when the binary tree is a chain.

Method 2: Iteration

The recursive function of method one can also be implemented in an iterative manner. The two methods are equivalent. The difference is that a stack is implicitly maintained during recursion, and we need to explicitly simulate this stack when iterating. , Others are the same, the specific implementation can be seen in the following code.

var inorderTraversal = function(root) { const res = []; const stk = []; while (root || stk.length) { while (root) { stk.push(root); root = root.left; } root = stk.pop(); res.push(root.val); root = root.right; } return res; }; Copy code

Time complexity: O(n), where n is the number of binary tree nodes. In the traversal of the binary tree, each node will be visited once and only once.

Space complexity: O(n). The space complexity depends on the stack depth, and the stack depth will reach the level of O(n) when the binary tree is a chain.

Method 3: Morris in-order traversal

Morris traversal algorithm is another method of traversing binary trees, which can reduce the space complexity of non-recursive in-order traversal to O(1).

The overall steps of the Morris traversal algorithm are as follows (assuming that the node currently traversed is x):

1. If x has no left child, first add the value of x to the answer array, and then visit the right child of x, that is x=x.rightx = x.\textit{right} .

2. If x has a left child, find the rightmost node on the left subtree of x (that is, the last node of the left subtree in the in-order traversal, and the predecessor node of x in the in-order traversal), we denote it as predecessor\textit{predecessor} . according topredecessor\textit{predecessor} the right child of the is empty, proceed as follows.

3. If predecessor\textit{predecessor} the right child of is empty, point its right child to x, and then visit the left child of x, that isx=x.leftx = x.\textit{left} .

4. if predecessor\textit{predecessor}The right child of is not empty, then its right child points to x at this time, indicating that we have traversed the left subtree of x, we willpredecessor\textit{predecessor}The right child of is left blank, the value of x is added to the answer array, and then the right child of x is accessed, namelyx=x.rightx = x.\textit{right} .

Repeat the above operations until the complete tree is visited.

In fact, we have to do one more step in the whole process: assuming that the node currently traversed is x, point the right child of the rightmost node in the left subtree of x to x, so that after the traversal of the left subtree is completed, we will walk back through this point. x, and we can know that we have traversed and completed the left subtree through this point, instead of maintaining it through the stack, saving the space complexity of the stack.

var inorderTraversal = function(root) { const res = []; let predecessor = null; while (root) { if (root.left) { //The predecessor node means that the current root node takes one step to the left, and then walks to the right until it cannot go predecessor = root.left; while (predecessor.right && predecessor.right !== root) { predecessor = predecessor.right; } //Let the right pointer of the predecessor point to root and continue to traverse the left subtree if (!predecessor.right) { predecessor.right = root; root = root.left; } //It means that the left subtree has been visited, we need to disconnect the link else { res.push(root.val); predecessor.right = null; root = root.right; } } //If there is no left child, go directly to the right child else { res.push(root.val); root = root.right; } } return res; }; Copy code

Time complexity: O(n), where nn is the number of nodes in the binary search tree. In Morris traversal, each node will be visited twice, so the total time complexity is O(2n)=O(n).

Space complexity: O(1).

Valid parentheses

Given a string s that only includes'(',')','{','}','[',']', judge whether the string is valid.

A valid string must meet:

The left parenthesis must be closed with the same type of right parenthesis. The opening parenthesis must be closed in the correct order.

Stack

We traverse the given string s. When we encounter a left parenthesis, we expect that in the subsequent traversal, a right parenthesis of the same type will close it. Since the left parenthesis encountered later must be closed first, we can put this left parenthesis on the top of the stack.

When we encounter a closing parenthesis, we need to close an opening parenthesis of the same type. At this point, we can take out the left parenthesis at the top of the stack and determine whether they are the same type of parenthesis. If it is not the same type, or there is no left parenthesis in the stack, the string s is invalid and False is returned. In order to quickly determine the type of parentheses, we can use a hash table to store each type of parentheses. The key of the hash table is the right parenthesis, and the value is the same type of left parenthesis.

After the traversal is over, if there is no left parenthesis in the stack, it means that we close all the left parentheses in the string s and return True, otherwise return False.

Note that the length of a valid string must be an even number, so if the length of the string is an odd number, we can directly return False to save the subsequent traversal judgment process.

var isValid = function(s) { const n = s.length; if (n% 2 === 1) { return false; } const pairs = new Map([ [')','('], [']','['], ['}','{'] ]); const stk = []; s.split('').forEach(ch => { if (pairs.has(ch)) { if (!stk.length || stk[stk.length-1] !== pairs.get(ch)) { return false; } stk.pop(); } else { stk.push(ch); } }); return !stk.length; }; Copy code

Time complexity: O(n), where n is the length of the string s.

Space complexity:O(n+ X x )O(n + |\Sigma|) , whereX x\Sigma represents the character set, the string in this question only contains 6 kinds of brackets, X x =6|\Sigma| = 6 . The number of characters in the stack is O(n), and the space used by the hash table isO( X x )O(|\Sigma|) , add up to get the total space complexity.