This is the 17th day of my participation in the Novembermore Challenge.The final text challenge in 2021
Some of the problems in the LeetCode problem set may have been skipped directly, so clean up the previous brush with LeetCode
111. Minimum depth of a binary tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.
Note: Leaf nodes are nodes that have no child nodes.
Example:
Given a binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
Copy the codeReturns its minimum depth of 2.
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
// The null node does not participate in the comparison
if (root.left == null&& root.right ! =null) {
return 1 + minDepth(root.right);
}
// The null node does not participate in the comparison
if (root.right == null&& root.left ! =null) {
return 1 + minDepth(root.left);
}
return 1+ Math.min(minDepth(root.left), minDepth(root.right)); }}Copy the code112. Sum of paths
Given a binary tree and a destination sum, determine whether there is a path from the root node to the leaf node in the tree. The sum of the values of all nodes along the path equals the destination sum.
Note: Leaf nodes are nodes that have no child nodes.
Example: Given the following binary tree with the target and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
Copy the codeReturns true because there is a target and path 5->4->11->2 from the root node to the leaf node of 22.
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return sum - root.val == 0;
}
returnhasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); }}Copy the code113. Sum of paths II
Given a binary tree and a destination sum, find all paths from the root node to the leaf node where the sum of paths equals the given destination sum.
Note: Leaf nodes are nodes that have no child nodes.
Example: Given the following binary tree with the target and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
Copy the codeReturns:
,4,11,2 [[5], [5,8,4,5]]
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root == null) return new ArrayList<>();
List<List<Integer>> ans = new ArrayList<>();
if(root.val == sum && root.left == null && root.right == null){
List<Integer> arr = new ArrayList<>();
arr.add(root.val);
ans.add(arr);
return ans;
}
List<List<Integer>> left = pathSum(root.left,sum - root.val);
List<List<Integer>> right = pathSum(root.right,sum - root.val);
for(List<Integer> list : left){
// The insertion to the specified coordinates will automatically sort the following coordinates backwards
list.add(0,root.val);
ans.add(list);
}
for(List<Integer> list : right){
list.add(0,root.val);
ans.add(list);
}
returnans; }}Copy the code114. Binary tree expands to a linked list
Given a binary tree, expand it in place as a linked list.
For example, given a binary tree
1 / \ 2 5 / \ 3 4 6Copy the codeExpand it as:
1\2\3\4\5\6Copy the code
class Solution {
// Straighten the left subtree, then straighten the right subtree, empty the left subtree, and splice the right subtree
public void flatten(TreeNode root) {
if(root==null)
return ;
flatten(root.left);
flatten(root.right);
TreeNode temp = root.right;
root.right = root.left;
root.left = null;
while(root.right! =null) root = root.right; root.right = temp; }}Copy the code115. Different subsequences
Given a string S and a string T, count the number of occurrences of T in a subsequence of S.
A subsequence of a string is a new string formed by deleting some (or none) characters without interfering with the relative positions of the remaining characters. (For example, “ACE” is a subsequence of “ABCDE”, but “AEC” is not)
Example 1:
Input: S = “rabbbit”, T = “rabbit”
As shown below, there are three ways to get “rabbit” from S. (Top arrow symbol ^ indicates the selected letter)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
Copy the codeExample 2:
Input: S = “babgbag”, T = “bag”
As shown in the figure below, there are five ways to get “bag” from S. (Top arrow symbol ^ indicates the selected letter)
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^
Copy the codePS: still admire the big guys oriented test case programming 👍
/** * dynamic programming but not high efficiency 20ms 35.83% * most of it is two-dimensional dynamic programming some of the code is the same but is 5ms estimate is the test case change * but see there is still a saving algorithm so step by step optimization ** * b A B G b A G ** 1 1 1 1 1 1 1 1 * b 0 1 1 2 2 3 3 3 * a 0 0 1 1 1 1 4 4 * g 0 0 0 0 1 1 1 5 * @param s * @param t * @return */ public int numDistinct(String s, String t) { int[][] dp = new int[t.length() + 1][s.length() + 1]; // initialize the first line for(int j = 0; j <= s.length(); j++){ dp[0][j] = 1; } for(int i = 1; i <= t.length(); i++){ for(int j = 1; j <= s.length(); j++){ if(t.charAt(i-1) == s.charAt(j-1)){ dp[i][j] = dp[i-1][j-1] + dp[i][j-1]; }else { dp[i][j] = dp[i][j-1]; } } } return dp[t.length()][s.length()]; } /** ** this is 15ms * @param s * @param t * @return */ public int numt2 (String s, String t) { int[] dp = new int[s.length() + 1]; Arrays.fill(dp, 1); int pre = 1; For (int I = 0; i < t.length(); I++){//0-n n+1 for(int j = 0; j <= s.length(); Int temp = dp[j]; if(j == 0){ dp[j] = 0; }else { if(t.charAt(i) == s.charAt(j-1)){ dp[j] = dp[j-1] + pre; }else { dp[j] = dp[j-1]; } } pre = temp; } } return dp[s.length()]; } /** * public int 11ms * @param s * @param t * @return */ public int NumDistinct3 (String s, String t) {// dp[0] indicates empty String int[] dp = new int[t.length() + 1]; // dp[0] is always 1, because no matter how long S is, it can only find an empty string equal to T. for (int i = 0; i < s.length(); i++){ for (int j = t.length() - 1; j >= 0; j--) { if (t.charAt(j) == s.charAt(i)) { dp[j + 1] += dp[j]; } } } return dp[t.length()]; } @param s * @param t * @return */ public int numDistinct4(String s, String t) {// dp[0] = empty String int[] dp = new int[t.length() + 1]; // dp[0] is always 1, because no matter how long S is, it can only find an empty string equal to T. Int [] map = new int[128]; Arrays.fill(map, -1); // for (int j = t.length() -1; // for (int j = t.length() -1; // for (int j = t.length() -1; // for (int j = t.length() -1; // for (int j = t.length() -1; j >= 0; j--) { // if (t.charAt(j) == s.charAt(i)) { // dp[j + 1] += dp[j]; // next[j] = map[s.char (I)] = map[s.char (I)] = map[s.char (I)] = map[s.char (I)] = map[s.char (I)] = map[s.char (I)] = map[s.char (I)] = map[s.char (I)] = map[s.char (I)] nexts = new int[t.length()]; for(int i = 0 ; i < t.length(); i++){ int c = t.charAt(i); nexts[i] = map[c]; map[c] = i; } for (int i = 0; i < s.length(); i++){ char c = s.charAt(i); for(int j = map[c]; j >= 0; j = nexts[j]){ dp[j + 1] += dp[j]; } } return dp[t.length()]; }Copy the code116. Populate the next right node pointer for each node
Given a perfect binary tree, all leaf nodes are at the same level and each parent node has two children. Binary trees are defined as follows:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Copy the codePopulate each of its next Pointers to point to its next right-hand node. If the next right-side node cannot be found, set the next pointer to NULL.
Initially, all next Pointers are set to NULL.
Example:
Input: {$" id ":" 1 ", "left" : {" $id ":" 2 ", "left" : {" $id ":" 3 ", "left", null, "next", null, "right", null, "val" : 4}, "next", null, "right" : {"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left": {"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right": ${" id ", "7", "left", null, "next", null, "right", null, "val" : 7}, "val" : 3}, "val" : 1} output: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null," next": {"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val": 4},"next": {"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"righ t": {"$ref":"7"},"val":1}Copy the codeExplanation: Given A binary tree as shown in Figure A, your function should populate each of its next Pointers to point to its next node on the right, as shown in Figure B.
PS: Using JSON as input and output for this problem is absolutely insane
class Solution {
public Node connect(Node root) {
if(root == null)
return root;
if(root.left ! =null)
root.left.next = root.right;
if(root.next ! =null&& root.right ! =null){
root.right.next = root.next.left;
}
connect(root.left);
connect(root.right);
returnroot; }}Copy the code117. Populate the next right node pointer II for each node
Given a binary tree
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Copy the codePopulate each of its next Pointers to point to its next right-hand node. If the next right-side node cannot be found, set the next pointer to NULL.
Initially, all next Pointers are set to NULL.
Advanced:
You can only use constant level extra space. Using recursion is also acceptable, in this case the stack space occupied by the recursive program does not count as additional space complexity.
Example:
Explanation: Given A binary tree as shown in Figure A, your function should fill each of its next Pointers to point to its next node on the right, as shown in Figure B.
Tip:
The number of nodes in the tree is less than 6000-100 <= node.val <= 100
class Solution {
public Node connect_1(Node root) {
if (root == null) {
return null;
}
// Implement hierarchical traversal with queue
LinkedList<Node> queue = new LinkedList<>();
queue.add(root);
while(! queue.isEmpty()) {int size = queue.size();
while (size-- > 0) {
Node node = queue.remove();
if (size > 0) {
node.next = queue.peek();
}
if(node.left ! =null) {
queue.add(node.left);
}
if(node.right ! =null) { queue.add(node.right); }}}return root;
}
public Node connect(Node root) {
if (root == null) {
return null;
}
if(root.left ! =null) {
if(root.right ! =null) {
// If the right subtree is not empty, next of the left subtree is the right subtree
root.left.next = root.right;
} else {
// If the right subtree is empty, the next of the right subtree is derived from the next of the root noderoot.left.next = nextNode(root.next); }}if(root.right ! =null) {
// Next of the right subtree is derived from next of the root node
root.right.next = nextNode(root.next);
}
// Make sure that the root. Right node is fully connected, because the root. Left node is fully connected
Next, if the root. Right node is not fully connected
Root.left. Next: root. Left. Next: root
// Return an error message. The possible error situations are shown below. At this point, the bottom leftmost node will not exist
// Get the correct next information:
// o root
/ / / /
// root.left o -- o root.right
/ / / / /
// o -- o o o
/ / / / /
// o o o
connect(root.right);
connect(root.left);
return root;
}
private Node nextNode(Node node) {
while(node ! =null) {
if(node.left ! =null) {
return node.left;
}
if(node.right ! =null) {
return node.right;
}
node = node.next;
}
return null; }}Copy the code118. Yang Hui Triangle
Given a non-negative integer numRows, generate the former numRows of the Yanghui triangle.
In Yang Hui’s triangle, each number is the sum of the numbers on its upper left and upper right.
Example:
Input: 5 Output:
[[1], [1,1], [1,2,1], [1,3,3,1]Copy the codeclass Solution {
public List<List<Integer>> generate(int numRows) {
int[][] arry = new int[numRows][numRows];
List<List<Integer>> list = new ArrayList<List<Integer>>();
List<Integer> list1 = null;
for (int i = 0; i < numRows; i++) {
arry[i][0] = 1;
list1 = new ArrayList<Integer>();
list1.add(arry[i][0]);
for (int j = 1; j <= i; j++) {
// The current bit comes from the sum of the column before the current bit and the column before the current bit
arry[i][j] = arry[i-1][j-1] +arry[i-1][j];
list1.add(arry[i][j]);
}
// Add the current row to the total result,
list.add(list1);
}
returnlist; }}Copy the code119. Yang Hui Triangle II
Given a nonnegative index k, where k ≤ 33, return the KTH row of the Yang Hui triangle.
In Yang Hui’s triangle, each number is the sum of the numbers on its upper left and upper right.
Example:
Input: 3 output: [1,3,3,1] advanced:
Can you optimize your algorithm to O(k) space complexity?
C(n, I) = n! /(i! *(n-i)!) * then the (I +1) term is a multiple of the (I) term =(n-i)/(I +1);Copy the codeclass Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> res = new ArrayList<>(rowIndex + 1);
long cur = 1;
for (int i = 0; i <= rowIndex; i++) {
res.add((int) cur);
cur = cur * (rowIndex-i)/(i+1);
}
returnres; }}Copy the code120. Minimum path sum of triangles
Given a triangle, find the minimum sum of paths from top to bottom. Each step can only move to the next node in the next row.
For example, given a triangle:
[[2], [3,4], [6,5,7], [4,1,8,3]Copy the codeThe minimum sum of paths from top to bottom is 11 (that is, 2 + 3 + 5 + 1 = 11).
Description:
If you can solve this problem using only O(n) of extra space (n is the total number of rows of a triangle), then your algorithm will be a bonus.
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) {return 0;
}
// Just record the minimum value of each layer
int[] dp = new int[triangle.size()+1];
for (int i = triangle.size() - 1; i >= 0; i--) {
List<Integer> curTr = triangle.get(i);
for (int j = 0; j < curTr.size(); j++) {
// dp[j] is used at the upper layer by default, and is assigned to the current layer
dp[j] = Math.min(dp[j],dp[j+1]) + curTr.get(j); }}return dp[0]; }}Copy the code