hot100（4）

31.437. 路径总和 III - 力扣（LeetCode）

方法一：递归、dfs

由树的结构想到使用递归解决，且路径相关问题容易考虑到使用dfs和bfs.

使用dfs解决，这里关键在于如何设计递归函数。

递归函数的参数：root,targetSum

递归函数的返回值：以root为根节点，路径和为targetSum的数量

递归函数的单层逻辑：

（1）判断返回条件，root == null,return 0

（2）计算当层结点路径数，需要递归调用得到左节点pathSum(root.left,targetSum - val) 右节点 pathSum(root.right,targetSum - val) 的结果，返回二者之和

rootSum：以当前节点为根节点，路径和等于targetSum的路径数

pathSum：root数中所有路径和等于targetSum的路径数

这种暴力dfs解法的关键之处在于理解需要嵌套两层暴力遍历

public int pathSum(TreeNode root, long targetSum) {if(root ==  null) return 0;int ret = rootSum(root,targetSum);ret += pathSum(root.left,targetSum);ret += pathSum(root.right, targetSum);return ret;}public int rootSum(TreeNode root, long targetSum){if(root == null) return 0;int ret = 0 ;if(root.val == targetSum){ret += 1;}ret += rootSum(root.left,targetSum - root.val);ret += rootSum(root.right, targetSum - root.val);return ret;}

复杂度分析：对于每一个节点，求以该节点为起点的路径数目时，都要遍历以该节点为根节点的子树的所有节点，最大时间为O(N)；对每一个节点都要进行这样的操作，节点数为N，因此时间复杂度为O(N^2)，空间复杂度O(N)

方法二：前缀和 优化方法一

方法一中对每个节点都进行了以该节点为根节点的dfs，这些dfs的很多计算是重复的，可以使用更加合理的计算顺序避免这些重复。

定义前缀和：根节点到当前节点的路径上，除了当前节点以外的所有节点的和

Map<Long,Integer> prefix;public int pathSum(TreeNode root, long targetSum) {prefix = new HashMap<>();prefix.put(0L,1);return dfs(root,targetSum,0);}public int dfs(TreeNode root, long targetSum, long curr){if(root == null) return 0;int res = 0;curr += root.val;res += prefix.getOrDefault(curr - targetSum, 0);prefix.put( curr,prefix.getOrDefault(curr,0) + 1);res += dfs(root.left, targetSum,curr);res += dfs(root.right, targetSum,curr);prefix.put(curr,prefix.getOrDefault(curr,0) - 1);return res;}

32.416. 分割等和子集 - 力扣（LeetCode）

回溯会超时，考虑动态规划。

从背包问题的角度看本题的本质：能否把sum/2的背包装满。

重量和价值都是数字大小，判断能否把sum/2的背包装满即判断背包价值最大是否是sum/2。

用01背包解决这个问题：

（1）dp[j]：容量为j的背包所能装入的最大价值为dp[j]

（2）dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]

（3）dp[0] = 0;

（4）先物品，后背包，背包容量逆序

（5）模拟

public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}if(sum % 2 == 1) return false;int target = sum/2;int[] dp = new int[target + 1];for(int i = 0 ; i < nums.length ; i++){for(int j = target ; j >= nums[i] ; j--){dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);}}return dp[target] == target;}

33.406. 根据身高重建队列 - 力扣（LeetCode）

题目描述：整数对 (h, k) 表示，其中 h 是这个人的身高，k 是排在这个人前面且身高大于或等于 h 的人数。

一般这种数对，且涉及排序的，根据第一个元素降序排序，根据第二个元素升序排序；或根据第一个元素升序排序，根据第二个元素降序排序，往往能够简化解题过程。

具体到这一道题，我们对身高降序排序，让身高大的排在前面；如果身高相同，则对k升序排序，让k小的排在前面。这样是为了先处理身高大的人，在这道题中，先处理身高大的是为了确保在插入过程中，已经排好位置的人能够满足条件。

关键点：

• 每个人的条件是：k个比他高的人已经排在他前面。
• 即处理好身高大的人的k值，这之后对身高小的人的插入是不影响身高大的人的k值的。（可以看成是每个人只能看到比自己高的人，身高大的人看不到身高小的人）

举例排序：

public int[][] reconstructQueue(int[][] people) {Arrays.sort(people,(a,b)->{if(a[0] == b[0]){return a[1] - b[1];}else{return b[0] - a[0];}});List<int[]> list = new ArrayList<>();for (int[] person : people) {list.add(person[1],person);}return  list.toArray(new int[people.length][]);}

34.399. 除法求值 - 力扣（LeetCode）

根据本题的描述，容易考虑到使用图论的方法解决。即是把value考虑成边的权重，var考虑成图的结点。

根据equations和values建好图，从queries中得到from 和 dest，然后在图中进行bfs，bfs的时候要记录from到么每一个节点的ratios（可以考虑成本题中特殊的距离，为路径权重乘积）。

这里bfs的时候没有用到visited数组，因为题目中明确权重>0,因此只要判断ratios[i]是否小于0即可得到是否来过。

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {int nvar = 0;Map<String,Integer> index = new HashMap<>();for (List<String> equation : equations) {if(!index.containsKey(equation.get(0))){index.put(equation.get(0),nvar++);}if(!index.containsKey(equation.get(1))){index.put(equation.get(1),nvar++);}}List<List<Pair>> graph = new ArrayList<>();for(int i = 0 ; i < nvar ; i++){graph.add(new ArrayList<>());}for(int i = 0 ; i < equations.size() ; i++){String sva = equations.get(i).get(0);int va = index.get(sva);String svb = equations.get(i).get(1);int vb = index.get(svb);graph.get(va).add(new Pair(vb,values[i]));graph.get(vb).add(new Pair(va,1.0/values[i]));}double[] res = new double[queries.size()];for(int i = 0 ; i < queries.size() ; i++){Queue<Integer> queue = new ArrayDeque<>();String sfrom = queries.get(i).get(0);String sdest = queries.get(i).get(1);double result = -1.0;if(index.containsKey(sfrom) && index.containsKey(sdest)){if(sfrom.equals(sdest)){result = 1.0;}else{int from = index.get(sfrom);int dest = index.get(sdest);queue.offer(from);double[] ratios = new double[nvar];Arrays.fill(ratios,-1.0);ratios[from] = 1.0;while(!queue.isEmpty() && ratios[dest] < 0){int node = queue.poll();List<Pair> neighbors = graph.get(node);for (Pair neighbor : neighbors) {if(ratios[neighbor.index] < 0){ratios[neighbor.index] = ratios[node] * neighbor.value;queue.offer(neighbor.index);}}}result = ratios[dest];}}res[i] = result;}return res;}class Pair{int index;double value;Pair(){}Pair(int neighbor, double value){this.index = neighbor;this.value = value;}}

方法II 并查集

这里回顾一下并查集和使用场景和使用方法

通常来说，并查集用来解决连通性问题，即判断两个元素是否在同一个集合里的时候，要想到用并查集，通常用于图论里的连通性判断。

并查集里的集合用一维数组来表示，如A,B,C在一个集合里，即father[A] = B,

father[B] = C  father[C] = C.

并查集里的路径压缩：在递归find的过程中，让father[u]接住 find(father[u])的返回结果。

即：

// 并查集里寻根的过程
int find(int u) {if (u == father[u]) return u;else return father[u] = find(father[u]); // 路径压缩
}

完整的并查集Java模板如下：

public class UnionFind {private int[] parent;public UnionFind(int size) {parent = new int[size];init();}// 并查集初始化private void init() {for (int i = 0; i < parent.length; i++) {parent[i] = i;}}// 并查集里寻根的过程public int find(int u) {if (u != parent[u]) {parent[u] = find(parent[u]); // 路径压缩}return parent[u];}// 判断 u 和 v 是否找到同一个根public boolean isSame(int u, int v) {return find(u) == find(v);}// 将 v -> u 这条边加入并查集public void join(int u, int v) {int rootU = find(u); // 寻找 u 的根int rootV = find(v); // 寻找 v 的根if (rootU != rootV) { // 如果根不同，合并两个集合parent[rootV] = rootU;}}public static void main(String[] args) {int n = 1005; // 根据实际情况调整UnionFind uf = new UnionFind(n);// 示例: 加入一些连接uf.join(1, 2);uf.join(2, 3);// 检查是否在同一个集合System.out.println(uf.isSame(1, 3)); // 输出 trueSystem.out.println(uf.isSame(1, 4)); // 输出 false}
}

在本题中，要求的是变量之间的关系，并且变量之间的倍数关系具有传递性，处理具有传递性的问题，可以使用并查集。我们需要再并查集的 合并 与 查询 操作中维护这些变量之间的倍数关系。

class Solution {public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {Map<String,Integer> map = new HashMap<>(equations.size()*2);UnionFind uf = new UnionFind(equations.size()*2);int nvar = 0;for (List<String> equation : equations) {String svar1 = equation.get(0);String svar2 = equation.get(1);if(!map.containsKey(svar1)){map.put(svar1,nvar++);}if(!map.containsKey(svar2)){map.put(svar2,nvar++);}}for(int i = 0 ; i < equations.size() ; i++){int var1 = map.get(equations.get(i).get(0));int var2 = map.get(equations.get(i).get(1));double value = values[i];uf.union(var1,var2,value);}double[] res = new double[queries.size()];for(int i = 0 ; i < queries.size() ; i++){int var1 = map.getOrDefault(queries.get(i).get(0),-1);int var2 = map.getOrDefault(queries.get(i).get(1),-1);if(var1 == -1 || var2 == -1){res[i] = -1.0d;continue;}res[i]  = uf.isConnected(var1,var2);}return res;}class UnionFind{int[] parent;double[] weight;UnionFind(int size) {parent = new int[size];weight = new double[size];Arrays.fill(weight,1.0);for(int i = 0 ; i < size ; i++){parent[i] = i;}}public void union(int x , int y , double value){int rootX = find(x);int rootY = find(y);if(rootX != rootY){parent[rootX] = rootY;weight[rootX] = weight[y] * value/weight[x];}}public int find(int x){if(x != parent[x]){int index = parent[x];parent[x] = find(parent[x]);weight[x] *= weight[index];}return parent[x];}public double isConnected(int x , int y){int rootX = find(x);int rootY = find(y);if(rootX != rootY){return -1.0d;}else{return weight[x]/weight[y];}}}
}

35.394. 字符串解码 - 力扣（LeetCode）

字符串问题，括号问题，使用栈或递归解决

class Solution {public String decodeString(String s) {Deque<Integer> stack_multi = new ArrayDeque<>();Deque<String> stack_string = new ArrayDeque<>();int multi = 0;StringBuilder res = new StringBuilder();for(int i = 0 ; i < s.length() ; i++){if(s.charAt(i) == '['){stack_multi.push(multi);multi = 0;stack_string.push(res.toString());res = new StringBuilder();}else if(s.charAt(i) == ']'){StringBuilder tmp = new StringBuilder();int curr_multi = stack_multi.pop();for(int j = 0 ; j < curr_multi ; j++){tmp.append(res);}res = new StringBuilder(stack_string.pop() + tmp);}else if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){multi = multi * 10 + Integer.parseInt(String.valueOf(s.charAt(i)));}else{res.append(s.charAt(i));}}return res.toString();}
}

36.347. 前 K 个高频元素 - 力扣（LeetCode）

I 暴力比较

要使用Arrays.sort比较自定义的数据结构的话，需要实现Comparator<>接口

public int[] topKFrequent(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>();for (int num : nums) {map.put(num,map.getOrDefault(num,0)+1);}Pair[] pairs = new Pair[map.entrySet().size()];int i = 0;for (Map.Entry<Integer, Integer> entry : map.entrySet()) {pairs[i++] = new Pair(entry.getValue(),entry.getKey());}Arrays.sort(pairs);int[] res = new int[k];for(int j = 0 ; j < k ; j++){res[j] = pairs[j].value;}return res;}class Pair implements Comparable<Pair>{int num;int value;Pair(){}Pair(int num, int value) {this.num = num;this.value = value;}@Overridepublic int compareTo(Pair o) {return Integer.compare(o.num,this.num);}}

II 小根堆 PriorityQueue

public int[] topKFrequent(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>();for (int num : nums) {map.put(num,map.getOrDefault(num,0) + 1);}PriorityQueue<int[]> heap = new PriorityQueue<>((pair1,pair2)->pair1[1] - pair2[1]);for (Map.Entry<Integer, Integer> entry : map.entrySet()) {if(heap.size() < k){heap.add(new int[]{ entry.getKey(),entry.getValue()});}else{if(heap.peek()[1] < entry.getValue()){heap.poll();heap.add(new int[]{entry.getKey(),entry.getValue()});}}}int[] res = new int[k];for(int i = 0 ; i < k ; i++){res[i] = heap.poll()[0];}return res;}

37.338. 比特位计数 - 力扣（LeetCode）

public int[] countBits(int n) {int[] res = new int[n+1];for(int i = 0 ; i <= n ; i++){res[i] = Integer.bitCount(i);}return res;}

38.337. 打家劫舍 III - 力扣（LeetCode）

本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算。

与198.打家劫舍，213.打家劫舍II一样，关键是要讨论当前节点抢还是不抢。

如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子（注意这里说的是“考虑”）

方法I 后序遍历，会时间超限

public int rob(TreeNode root) {if(root == null) return 0;if(root.left == null && root.right == null){return root.val;}//不考虑抢劫rootint val1 = rob(root.left) + rob(root.right);//考虑抢劫rootint val2 = root.val;if(root.left != null) val2  = val2 + rob(root.left.left) + rob(root.left.right);if(root.right != null) val2 = val2 + rob(root.right.left) + rob(root.right.right);return Math.max(val1,val2);}

II 记忆化递推

把当前节点的计算结果存储到map中，如果计算过了，则直接返回，避免重复计算

Map<TreeNode,Integer> map = new HashMap<>();public int rob(TreeNode root) {if(root == null) return 0;if(root.left == null && root.right == null){return root.val;}if(map.containsKey(root)) return map.get(root);//不考虑抢劫rootint val1 = rob(root.left) + rob(root.right);//考虑抢劫rootint val2 = root.val;if(root.left != null) val2  = val2 + rob(root.left.left) + rob(root.left.right);if(root.right != null) val2 = val2 + rob(root.right.left) + rob(root.right.right);map.put(root,Math.max(val1,val2));return Math.max(val1,val2);}

III 动态规划

在上面两种方法，其实对一个节点 偷与不偷得到的最大金钱都没有做记录，而是需要实时计算。

而动态规划其实就是使用状态转移容器来记录状态的变化，这里可以使用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱。

之前用的状态转移容器是数组，这里选择的状态转移容器也是int[]数组，只是结合了树这种数据结构，并根据树形结构的特征结合了递归。

这道题目算是树形dp的入门题目，因为是在树上进行状态转移，下面以递归三部曲为框架，其中融合动规五部曲的内容来进行讲解。

1.确定递归函数的参数和返回值

要维护一个结点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。

dp数组及下标含义：dp[0] : 不偷该节点所得到的最大金钱，dp[1]：偷该节点所得到的最大金钱。

2.确定递归终止条件

if(root == null) return new int[]{0,0};

也相当于dp数组初始化

3.确定遍历顺序

使用后序遍历，因为需要递归函数的返回值做下一步计算。

4.确定单层递归的逻辑

如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果对下标含义不理解就再回顾一下dp数组的含义）

如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);

最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}

5.举例推导dp数组

- 时间复杂度O(n)，每个节点只遍历了一次

- 空间复杂度O(logn),递推系统栈的空间

public int rob(TreeNode root) {int[] res = robTree(root);return Math.max(res[0],res[1]);}public int[] robTree(TreeNode root){if(root == null) return new int[]{0,0};int[] left = robTree(root.left);int[] right = robTree(root.right);//不偷根节点int val1 = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);//偷根节点int val2 = root.val + left[0] + right[0];return new int[]{val1,val2};}

39.121. 买卖股票的最佳时机 - 力扣（LeetCode）

本题限制性要求在于只能买卖股票一次

I贪心

由于只能买卖一次，因此贪心算法选择遍历一次，在遍历的过程中记录每个数字左侧的最小值，与当前能赚到的差价作比较，遍历一次得到最大的差价，即最大的利润。

public int maxProfit(int[] prices) {int low = Integer.MAX_VALUE;int res = 0;for(int i = 0 ; i < prices.length ; i++){low = Math.min(low,prices[i]);res = Math.max(res,prices[i] - low);}return res;}

II动态规划

本题中的状态有持有股票和不持有股票两种

1.dp数组及下标的含义

dp[i][0] : 第i天持有股票所得最多现金

dp[i][1] : 第i天不持有股票所得最多现金

2.递推公式

dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][1] - prices[i]);

dp[i][1] = Math.max(dp[i-1][0] + prices[i] , dp[i-1][1]);

3.初始化

dp[0][0] = - prices[0];

dp[0][1] = 0;

4.遍历顺序

从前向后

5.举例推导dp数组

时间复杂度O(n)

空间复杂度O(n)，使用滚动数组可以优化到O(1)

public int maxProfit(int[] prices) {int[][] dp = new int[prices.length][2];dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1 ; i < prices.length ; i++){dp[i][0] = Math.max(dp[i-1][0], - prices[i]);dp[i][1] = Math.max(dp[i-1][0] + prices[i] ,dp[i-1][1]);}return dp[prices.length - 1][1];}

40.312. 戳气球 - 力扣（LeetCode）

区间dp问题，详细生动题解：312. 戳气球 题解- 力扣（LeetCode）

1.dp数组及下标含义

dp[i][j]：开区间(i,j)，所能得到的最大硬币数

2.状态转移方程

for k (k > i && k < j )

dp[i][j] = max{dp[i][k] + dp[k][j] + val[i] * val[k] * val[j]}

3.初始化

为了方便处理，nums前后加上边界1，题目中称边界视为1，这样可以避开对边界的讨论

4.遍历顺序

遍历长度length 从 2 到哦 list.size()

5.dp模拟

public int maxCoins(int[] nums) {List<Integer> list = new ArrayList<>();for (int num : nums) {list.add(num);}list.add(0,1);list.add(list.size(),1);int[][] dp = new int[list.size()][list.size()];for(int length = 1 ; length <= nums.length; length++){for(int i = 0 ; i < list.size() - length - 1; i++){int j = i + length + 1;int maxCoins = 0;for(int k = i + 1 ; k < j ; k++){if(dp[i][k] + dp[k][j] + list.get(i)*list.get(k)*list.get(j) > maxCoins){maxCoins = dp[i][k] + dp[k][j] + list.get(i)*list.get(k)*list.get(j);}}dp[i][j] = maxCoins;}}return dp[0][list.size()-1];}