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)); // 输出 true
System.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;
}
@Override
public 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;
}
//不考虑抢劫root
int val1 = rob(root.left) + rob(root.right);
//考虑抢劫root
int 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);
//不考虑抢劫root
int val1 = rob(root.left) + rob(root.right);
//考虑抢劫root
int 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];
}