LeetCode 652 Find Duplicate Subtrees
Link: leetcode.com/problems/fi…
Methods: recursion, hash, tree numbering
Time complexity: O(n), where n is the number of nodes in the tree. . The idea is to hash the tree structure so that trees of the same structure, even if they are different and have different addresses, will correspond to the same value. One way to do this problem is to use binary tree serialization, but it’s obviously too cumbersome. So what we’re doing here is we’re giving the binary tree a numbered ID. Each tree is represented by a string (optimized to a long number in the code below), which can be the value of the current node + the id on the left + “,”+ the ID on the right. This recursion to the leaf node will result in the same leaf node, hash the same string, recursion all the way back will result in the tree of the same structure with the same string. There is also a hash table for COUNTS that maps from ID to number, indicating how many trees will correspond to that ID. Id = ids.size() + 1; id = ids.size() + 1; Every time a key-value pair with a value of 2 is counted, an ID is duplicated. The subtree with the current node as root is duplicated and added to the result. Another learning point: Val, left ID, and right ID, and the number range of the problem allows. Therefore, it is much faster to concatenate the three values into a value of type long than to concatenate a string and then find a string. Code:
class Solution { public List<TreeNode> findDuplicateSubtrees(TreeNode root) { List<TreeNode> res = new ArrayList<>(); Map<Long, Integer> ids = new HashMap<>(); Map<Integer, Integer> counts = new HashMap<>(); getId(root, res, ids, counts); return res; } private int getId(TreeNode root, List<TreeNode> res, Map<Long, Integer> ids, Map<Integer, Integer> counts){ if (root == null) { return 0; } long key = ((long)root.val << 32) | (getId(root.left, res, ids, counts) << 16) | (getId(root.right, res, ids, counts)); int id = 0; if (ids.containsKey(key)) { id = ids.get(key); } else { id = ids.size() + 1; ids.put(key, id); } int tmp = counts.getOrDefault(id, 0) + 1; counts.put(id, tmp); if (tmp == 2) { res.add(root); } return id; }}Copy the codeLeetCode 644 Maximum Average Subarray II
Link: leetcode.com/problems/ma…
Method: dichotomy
Time complexity: O(nlogL), where n is the length of the array and L is the range of the values in the array. On medium, it is hard to read. On medium, it is hard to read. On medium, it is hard to read. The first thing is to think of binary solutions. The two variables in this problem are the maximum average value v and the required minimum length of the subarray k, where the minimum length of the subarray k required to satisfy is the independent variable, and the maximum average value V under this requirement is the variable. Our dichotomy answer is to dichotomy the variable. The intuitive idea is that the lower the minimum length k of the subarray, the greater the maximum average of the subarray that can be achieved. That clears up the first part of the problem. The second part of the problem: given the minimum length of the stator array in an array, how can we efficiently calculate if there are such subarrays that the average value is greater than or equal to some value target? A nice trick here is that I don’t bother with the old array and the average, I subtract target from all the numbers in the old array, and that turns the question into whether there are subarrays of length >=k, and >=0. This is a lot easier than the previous problem, so we can get rid of the problem of averages and focus on prefixes. Let’s do two prefixes, one called leftSum, starting from the left, and one called rightSum, k units to the right of it. Then update these two values each time to maintain the minimum value of leftSum. So as long as rightSum >= the minimum of leftSum at any time, we find such a subarray, and the problem is solved. This is something to learn, and I remember where else I used it, but I forgot, and I had time to find that problem and update this place. Code:
Class Solution {public double findMaxAverage(int[] nums, int k) {double left = -10000.0, right = 10000.0; while (left + 1e-5 < right) { double mid = (left + right) / 2; if (canFind(nums, k, mid)) { left = mid; } else { right = mid; } } return left; } private boolean canFind(int[] nums, int k, double target) { double leftSum = 0, rightSum = 0, minLeftSum = 0; for (int i = 0; i < k; i++) { rightSum += (nums[i] - target); } for (int i = k; i <= nums.length; i++) { if (rightSum >= minLeftSum) { return true; } if (i < nums.length) { rightSum += (nums[i] - target); leftSum += (nums[i - k] - target); minLeftSum = Math.min(minLeftSum, leftSum); } } return false; }}Copy the codeLeetCode 406 Queue Reconstruction by Height
Link: leetcode.com/problems/qu…
Solution: Be greedy
Time complexity: O(n2) Idea: Let’s see if we can observe it. The first element of each pair is height, and the second element is how many people are in front of them height >= him. A very general idea is that tall people must be easier to deal with, because there are fewer tall people in front of tall people, so the state is relatively less complicated, so to do this problem should start from the tall people. And for people of the same size, the second element that’s smaller means he’s standing a little bit further forward, so that should also be dealt with first. Then sort the original array according to the above scheme. Insert each element directly into the corresponding index of the result list, where index is the second element of each person’s pair. Why is this right? Because we sorted by said before, when an element is put behind haven’t put the elements of the no taller than he is, the current has been in the list of elements or is as tall as he, or taller than him, that at this time, for example, is now processing, pair 3, the second element is that there are three people in front of the > = his height, I’m just going to insert it at the third position in the list. Code:
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (a, b) -> {
if (a[0] != b[0]) {
return b[0] - a[0];
}
return a[1] - b[1];
});
List<int[]> lst = new ArrayList<>();
for (int[] p : people) {
int index = p[1];
lst.add(index, p);
}
int[][] res = new int[lst.size()][2];
int tt = 0;
for (int[] p : lst) {
res[tt++] = p;
}
return res;
}
}
Copy the codeLeetCode 341 Flatten Nested List Iterator
Link: leetcode.com/problems/fl…
Method 1: Fully flattened
Idea: The way I started… … class = ‘class_constructor’ > insert NestedInteger into the list. Code:
public class NestedIterator implements Iterator<Integer> { private List<Integer> lst; private int i; private int size; public NestedIterator(List<NestedInteger> nestedList) { this.lst = new ArrayList<>(); dfs(lst, nestedList); this.i = 0; this.size = lst.size(); } private void dfs(List<Integer> lst, List<NestedInteger> nestedList) { for (NestedInteger ni : nestedList) { if (ni.isInteger()) { lst.add(ni.getInteger()); } else { dfs(lst, ni.getList()); } } } @Override public Integer next() { return this.lst.get(i++); } @Override public boolean hasNext() { return this.i < this.size; }}Copy the codeMethod 2: stack
Idea: The idea is to push the original list backwards, and then call the method that calls hasNext() and next() each time, and then flatten the top of the stack inside hasNext(), making sure that the top element is Integer. In this case, pop out the top value in next. Code:
public class NestedIterator implements Iterator<Integer> {
private Stack<NestedInteger> stack = new Stack<>();
public NestedIterator(List<NestedInteger> nestedList) {
for (int i = nestedList.size() - 1; i >= 0; i--) {
stack.push(nestedList.get(i));
}
}
@Override
public Integer next() {
return stack.pop().getInteger();
}
@Override
public boolean hasNext() {
while (!stack.isEmpty()) {
NestedInteger head = stack.peek();
if (head.isInteger()) {
return true;
}
stack.pop();
List<NestedInteger> lst = head.getList();
for (int i = lst.size() - 1; i >= 0; i--) {
stack.push(lst.get(i));
}
}
return false;
}
}
Copy the code