海边别墅

# LeetCode 4

2021.5 ~ 2021.7

# 7. 整数反转

class Solution {
    public int reverse(int x) {
        // 怎么知道超出了32的范围
        // 如何直接翻转
        int res = 0;
        while (x != 0) {
            if (res < Integer.MIN_VALUE / 10 || res > Integer.MAX_VALUE / 10) {
                return 0;
            }
            int r = x % 10;
            x = x / 10;
            res = res*10 + r;
            // System.out.println("res:"+res);
        }
        return res;
    }
}

# 1473. 粉刷房子 III

好难的动归，做不出- -！

暴力dfs，通不过的：

class Solution {
	// 上确界，此处可以设置Integer.MAX_VALUE，但可能会爆
    //INF + INF 不会爆int
    int INF = 0x3f3f3f3f;
    int ans = INF;
    int[] hs;
    int[][] cost;
    int m, n, t;
    public int minCost(int[] _hs, int[][] _cost, int _m, int _n, int _t) {
        m = _m; n = _n; t = _t;
        hs = _hs;
        cost = _cost;
		// init  home_i为0，从0开始；color_last为-1，记做上一个房间颜色
		// cnt为0，为当前分区数量
		// sum为0，为当前上色花费
        dfs(0, -1, 0, 0);
        return ans == INF ? -1 : ans;
    }
    // home_i : 当前的房间编号
    // color_last : 上一个房间颜色
    // cnt : 当前分区数量
    // sum : 当前涂色花费
    void dfs(int home_i, int color_last, int cnt, int sum) {
        if (sum >= ans || cnt > t) return;
        // 递归遍历到最后一间房+1时，并cnt==target时，计算最小值
        if (home_i == m) {
            if (cnt == t) {
                ans = Math.min(ans, sum);
            }
            return;
        }
        int color = hs[home_i];
		// 未上色
        if (color == 0) {
			// 遍历n种颜色给当前房间
            for (int i = 1; i <= n; i++) {
				// home_i - 1 < 0 表示此时为第一个房间，则分区计数为1，
				// 否则与上一个颜色比较即可，不相等则cnt+1(分区计数+1)
                int nCnt = home_i - 1 < 0 ? 1 : color_last == i ? cnt : cnt + 1;
				// 递归下一个房间
                dfs(home_i + 1, i, nCnt, sum + cost[home_i][i - 1]);
            }
        } else {
            int nCnt = home_i - 1 < 0 ? 1 : color_last == color ? cnt : cnt + 1; 
            dfs(home_i + 1, color, nCnt, sum);
        }
    }
}

dfs，记忆化优化：

class Solution {
	// 上确界，此处可以设置Integer.MAX_VALUE，但可能会爆
    //INF + INF 不会爆int
    int INF = 0x3f3f3f3f;
    int ans = INF;
    int[] hs;
    int[][] cost;
    int m, n, t;
	// cache[home_i][color_last][cnt] = sum
	int[][][] cache;
    // 三维数组不好做初始化赋值，复杂度可能很高，所以直接使用boolean数组
    boolean[][][] visited;
    public int minCost(int[] _houses, int[][] _cost, int _m, int _n, int _target) {
        m = _m; n = _n; t = _target;
        hs = _houses;
        cost = _cost;
        cache = new int[hs.length+1][n+1][t+1];
        visited = new boolean[hs.length+1][n+1][t+1];
		// init  home_i为0，从0开始；color_last为-1，记做上一个房间颜色
		// cnt为0，为当前分区数量
		// sum为0，为当前上色花费
        int res = dfs(0, 0, 0, 0);
        return res == INF ? -1 : res;
    }
    
    /*
    * home_i : 当前的房间编号
    * color_last : 上一个房间颜色
    * cnt : 当前分区数量
    * sum : 当前涂色花费
    * @return 当前方法入参条件下的花费最小值
    */
    int dfs(int home_i, int color_last, int cnt, int sum) {
        // 递归终止条件：sum涂色花费大于之前的最小答案 或者 分区大于target
        if (sum >= ans || cnt > t) return INF;
        
        // System.out.println("home_i"+home_i+"; color_last:"+color_last+"; cnt:"+cnt);
		if (color_last != -1 && visited[home_i][color_last][cnt]) {
			return cache[home_i][color_last][cnt];
		}
        
        // 递归遍历到最后一间房+1时，并cnt==target时，由于return是返回当前条件下的最小值，因此返回0，否则返回上界
        if (home_i == m) {
            if (cnt == t) {
                return 0;
            }
            return INF;
        }
        
        // 计算当前层遍历到下层的最小sum花费
		int res = INF;
        int color = hs[home_i];
		// 未上色
        if (color == 0) {
			// 遍历n种颜色给当前房间
            for (int i = 1; i <= n; i++) {
				// home_i - 1 < 0 表示此时为第一个房间，则分区计数为1，
				// 否则与上一个颜色比较即可，不相等则cnt+1(分区计数+1)
                int nCnt = home_i - 1 < 0 ? 1 : color_last == i ? cnt : cnt + 1;
				// 递归下一个房间，返回值代表下一个房间开始直到最后的最小花费
                int cur = dfs(home_i + 1, i, nCnt, sum + cost[home_i][i - 1]);
                // 最小花费cur 加上当前值cost[home_i][i - 1]，计算最小值
                res = Math.min(res, cur+cost[home_i][i - 1]);
            }
        } else {
            int nCnt = home_i - 1 < 0 ? 1 : color_last == color ? cnt : cnt + 1; 
            int cur = dfs(home_i + 1, color, nCnt, sum);
            res = Math.min(res, cur);
        }
        
        cache[home_i][color_last][cnt] = res;
        visited[home_i][color_last][cnt] = true;
        return res;
    }
}

动态规划：

class Solution {
    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        int INF = 0x3f3f3f3f;
        // dp数组定义：
        // 前i间房子、第i间房子的颜色为j、前i间房子的分区数量为k的，所有方案中最小花费是val。
        int[][][] dp = new int[m+1][n+1][target+1];
        // init
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j][0] = INF;
            }
        }
        
        // 从dp方程来看，i是从0开始，j是与前一个比较，也是从0开始，k则是也是从0开始到target
        for (int i = 1; i <= m; i++) {
            int color = houses[i-1];
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= target; k++) {
                    
                    if (k > i) {
                        dp[i][j][k] = INF;
                        continue;
                    }
                    
                    // 未被涂色，有两种场景，取两者最小即可：
                    // 1.跟前面涂同一个颜色，也就是同一个分区，可以直接取前一个dp值
                    // 2.跟前面不涂同一个颜色，也就成为新分区，因此在k-1分区中找所有颜色dp值最小的
                    if (color == 0) {
                        int tmp = INF;
                        // 遍历前i-1个房间k-1的分区的所有颜色，找出最小的花费
                        for (int p = 1; p <= n; p++) {
                            if (j != p) {
                                tmp = Math.min(tmp, dp[i-1][p][k-1]);
                            }
                        }
                        // System.out.println("i:"+i+"; j:"+j+"; k:"+k);
                        // dp[i-1][j][k] 代表前i-1个房间，k分区（所以颜色是j）的最小值
                        dp[i][j][k] = Math.min(tmp, dp[i-1][j][k]) + cost[i-1][j-1];

                    } else {
                        // 已被涂色，color只能为j，同样有两种场景，计算方式与上面一致：
                        if (j == color) {
                            int tmp = INF;
                            for (int p = 1; p <= n; p++) {
                                if (j != p) {
                                    tmp = Math.min(tmp, dp[i-1][p][k-1]);
                                }
                            }
                            dp[i][j][k] = Math.min(tmp, dp[i-1][j][k]);
                        } else {
                            dp[i][j][k] = INF;
                        }
                    }
                }
            }
        }
        
        // 结果为 dp[m][?][target]，需要遍历颜色取最小值来确定结果
        int res = INF;
        for (int i = 1; i <= n; i++) {
            res = Math.min(res, dp[m][i][target]);
        }
        
        return res == INF ? -1 : res;
    }
}

# 494. 目标和

暴力dfs：

class Solution {
    int cnt = 0;
    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums, target, 0, 0);
        return cnt;
    }
    
    private void dfs(int[] nums, int target, int i, int sum) {
        // System.out.println("i:"+i+"; sum:"+sum);
        if (i == nums.length) {
            if (sum == target) cnt++;
            return;
        }
        
        dfs(nums, target, i+1, sum-nums[i]);
        dfs(nums, target, i+1, sum+nums[i]);
    }
}

dfs备忘录优化递归：

class Solution {
    private Map<String, Integer> memo;
    public int findTargetSumWays(int[] nums, int target) {
        memo = new HashMap<>();
        return dfs(nums, target, 0, 0);
    }
    
    private int dfs(int[] nums, int target, int i, int sum) {
        // System.out.println("i:"+i+"; sum:"+sum);
        if (i > nums.length) return 0;
        Integer cnt = memo.get(i+";"+sum);
        if (cnt != null) return cnt;
        
        if (i == nums.length) {
            if (sum == target) return 1;
            return 0;
        }
        
        int res = 0;
        
        res += dfs(nums, target, i+1, sum-nums[i]);
        res += dfs(nums, target, i+1, sum+nums[i]);
        
        memo.put(i+";"+sum, res);
        return res;
    }
}

按照官方题解的动归方式，个人觉得不好理解：
由于题目限制，数组中数字的最大和不超过1000，所以设置一个2001大小的数组，可以想象就是一张2001长以及nums.length高度的表格，内循环就是直接遍历2001的长度，初始化只需要将nums[0]的情况覆盖即可。

1620190313807

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int[][] dp = new int[nums.length][2001];
        
        // 有可能是同一个，所以使用+=
        dp[0][nums[0]+1000] = 1;
        dp[0][-nums[0]+1000] += 1;
        
        for (int i = 1; i < nums.length; i++) {
            for (int j = -1000; j <= 1000; j++) {
                // 遍历时，反向考虑，从上一行开始选择，就一定不会越界，其次只有大于0的才会对下方有所增益
                if (dp[i-1][j+1000] > 0) {
                    dp[i][j-nums[i]+1000] += dp[i-1][j+1000];
                    dp[i][j+nums[i]+1000] += dp[i-1][j+1000];
                }
            }
        }

        return dp[nums.length-1][target+1000];
    }
}

普通思路下的动归，由于加和减都有越界的可能，所以都需要做判断：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int[][] dp = new int[nums.length][2001];
        
        // 有可能是同一个，所以使用+=
        dp[0][nums[0]+1000] = 1;
        dp[0][-nums[0]+1000] += 1;
        
        for (int i = 1; i < nums.length; i++) {
            for (int j = -1000; j <= 1000; j++) {
                int sum = 0;
                if (j-nums[i]+1000 >= 0 && j-nums[i]+1000 < 2001) {
                     sum += dp[i-1][j-nums[i]+1000];
                }
                
                if (j+nums[i]+1000 >= 0 && j+nums[i]+1000 < 2001) {
                     sum += dp[i-1][j+nums[i]+1000];
                }
                
                dp[i][j+1000] = sum;
            }
        }
        
        return dp[nums.length-1][target+1000];
    }
}

按照官方题解的优化思路，简化成两个一维数组：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // 利用两个数组减小空间复杂度，cur是当前操作数组，pre是前一轮循环操作数组；
        int[] cur;
        int[] pre = new int[2001];
        
        // 有可能是同一个，所以使用+=
        pre[nums[0]+1000] = 1;
        pre[-nums[0]+1000] += 1;
        
        for (int i = 1; i < nums.length; i++) {
            cur = new int[2001];
            for (int j = -1000; j <= 1000; j++) {
                if (pre[j+1000] > 0) {
                    cur[j-nums[i]+1000] += pre[j+1000];
                    cur[j+nums[i]+1000] += pre[j+1000];
                }
            }
            pre = cur;
        }
        
        return pre[target+1000];
    }
}

更优的构造数组思路，不利用题目的条件范围，而是根据入参判断（画表格有个好处，如果解题出现问题，只要打印dp数组与表格对比即可立马发现问题所在）：

1620189063855

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int t = 0;
        for (int n : nums) {
            t += n;
        }
        int[][] dp = new int[nums.length][t*2+1];
        
        dp[0][nums[0]+t] = 1;
        dp[0][-nums[0]+t] += 1;
        
        for (int i = 1; i < nums.length; i++) {
            
            for (int j = -t; j <= t; j++) {
                int sum = 0;
                if (j-nums[i]+t >= 0 && j-nums[i] <= t) {
                     sum += dp[i-1][j-nums[i]+t];
                }
                
                if (j+nums[i]+t >= 0 && j+nums[i] <= t) {
                     sum += dp[i-1][j+nums[i]+t];
                }
                
                dp[i][j+t] = sum;
            }
        }
        // System.out.println(Arrays.deepToString(dp));
        return dp[nums.length-1][target+t];
    }
}

再次优化成两个一维数组：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int t = 0;
        for (int n : nums) {
            t += n;
        }
        // 如果target大于数字和，直接返回
        if (Math.abs(target) > t) return 0;
        
        int len = t*2+1;
        int[] pre = new int[len];
        
        pre[nums[0]+t] = 1;
        pre[-nums[0]+t] += 1;
        
        for (int i = 1; i < nums.length; i++) {
            int[] cur = new int[len];
            for (int j = -t; j <= t; j++) {
                int sum = 0;
                if (j-nums[i]+t >= 0 && j-nums[i] <= t) {
                     sum += pre[j-nums[i]+t];
                }
                
                if (j+nums[i]+t >= 0 && j+nums[i] <= t) {
                     sum += pre[j+nums[i]+t];
                }
                
                cur[j+t] = sum;
            }
            pre = cur;
        }
        return pre[target+t];
    }
}

go语言：

import "math"
func findTargetSumWays(nums []int, target int) int {
    n := len(nums)
    m := 0
    for i := range nums {
        m += int(math.Abs(float64(nums[i])))
    }
    if target > m {
        return 0
    }
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, 2*m+1)
    }
    dp[0][0+m] = 1
    
    for i := 1; i <= n; i++ {
        x := nums[i-1]
        for j := -m; j <= m; j++ {
            if (j-x)+m >= 0 {
                dp[i][j+m] += dp[i-1][j-x+m]
            }
            if (j+x)+m <= 2*m {
                dp[i][j+m] += dp[i-1][j+x+m]
            }
        }
    }
    return dp[n][target+m]
}

# 518. 零钱兑换 II

dfs暴力递归解，无法AC：

class Solution {
    int cnt = 0;
    public int change(int amount, int[] coins) {
        dfs(amount, coins, 0, 0);
        return cnt;
    }
    
    private void dfs(int amount, int[] coins, int sum, int index) {
        if (sum > amount) return;
        if (sum == amount) {
            cnt++;
            return;
        }
        
        for (int i = index; i < coins.length; i++) {
            // System.out.println("sum:"+(sum+coins[i])+"; c:"+coins[i]);
            dfs(amount, coins, sum+coins[i], i);
        }
    }
}

dfs备忘录优化，可以AC，但仍然非常慢：

class Solution {
    int[][] dp;
    public int change(int amount, int[] coins) {      
        dp = new int[coins.length+1][amount+1];
        for (int i = 0; i <= coins.length; i++) {
            Arrays.fill(dp[i], -1);
        }
        return dfs(amount, coins, 0, 0);
    }
    
    private int dfs(int amount, int[] coins, int sum, int index) {
        if (sum > amount) return 0;
        if (dp[index][sum] != -1) {
            return dp[index][sum];
        }
        
        if (sum == amount) {
            return 1;
        }
        
        int res = 0;
        for (int i = index; i < coins.length; i++) {
            // System.out.println("sum:"+(sum+coins[i])+"; c:"+coins[i]);
            res += dfs(amount, coins, sum+coins[i], i);
        }
        dp[index][sum] = res;
        return res;
    }
}

二维dp，Go解法:

func change(amount int, coins []int) int {
    m := amount
    n := len(coins)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, m+1)
    }
    dp[0][0] = 1
    for i := 1; i <= n; i++ {
        cv := coins[i-1]
        for j := 0; j <= m; j++ {
            dp[i][j] = dp[i-1][j]
            for k := 1; k*cv <= j; k++ {
                dp[i][j] += dp[i-1][j-k*cv]
            }
        }
    }
    return dp[n][m]
}

# 740. 删除并获得点数

同198.打家劫舍一样的题，只是相邻的考虑条件不一样了，所以使用有序去重的TreeMap实现：

class Solution {
    public int deleteAndEarn(int[] nums) {
        TreeMap<Integer, Integer> tree = new TreeMap<Integer, Integer>(
            new Comparator<Integer>() {
                public int compare(Integer obj1, Integer obj2) {
            return obj1.compareTo(obj2);
            }
        });
        // init
        for (int n : nums) {
            tree.put(n, tree.getOrDefault(n, 0)+1);
        }
        
        Set<Map.Entry<Integer, Integer>> set = tree.entrySet();
        Iterator<Map.Entry<Integer, Integer>> it = set.iterator();
        
        Map.Entry<Integer, Integer> np2 = it.next();
        int p1 = 0, p2 = np2.getKey()*np2.getValue();
        if (tree.size() < 2) {
            return p2;
        }
        Map.Entry<Integer, Integer> np1 = it.next();
        if (np1.getKey() - np2.getKey() == 1) {
            p1 = Math.max(p2, np1.getKey()*np1.getValue());
        } else {
            p1 = p2 + np1.getKey()*np1.getValue();
        }
        
        while (it.hasNext()) {
            Map.Entry<Integer, Integer> cur = it.next();
            
            int max = 0;
            if (cur.getKey() - np1.getKey() == 1) {
                max = Math.max(p1, p2 + cur.getKey()*cur.getValue());
            } else {
                max = p1 + cur.getKey()*cur.getValue();
            }
            
            p2 = p1;
            p1 = max;
            np1 = cur;
        }
        
        return p1;
    }
}

使用普通map和list优化掉TreeMap，提高性能：

class Solution {
    public int deleteAndEarn(int[] nums) {
        Arrays.sort(nums);
        // 此处可以直接将value存为当前key的全部和
        HashMap<Integer, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        // init
        map.put(nums[0], 1);
        list.add(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1]) {
                list.add(nums[i]);
            }
            map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
        }
        
        int p1 = 0, p2 = list.get(0)*map.get(list.get(0));
        if (map.size() < 2) {
            return p2;
        }
        if (list.get(1) - list.get(0) == 1) {
            p1 = Math.max(p2, list.get(1)*map.get(list.get(1)));
        } else {
            p1 = p2 + list.get(1)*map.get(list.get(1));
        }
        
        for (int i = 2; i < list.size(); i++) {
            int max = 0;
            int cur = list.get(i)*map.get(list.get(i));
            if (list.get(i) - list.get(i-1) == 1) {
                max = Math.max(p1, p2 + cur);
            } else {
                max = p1 + cur;
            }
            
            p2 = p1;
            p1 = max;
        }
        
        return p1;
    }
}

最快解，核心思路是构造一个0~maxValue的数组，再将nums中的值存入到sum数组中，直接构造出打家劫舍同样的场景，用其方法直接求解：

class Solution {
    public int deleteAndEarn(int[] nums) {
        int max = 0;
        for (int n : nums) {
            max = Math.max(max, n);
        }
        
        int[] sum = new int[max+1];
        for (int n : nums) {
            sum[n] += n;
        }
        
        return rob(sum);
    }
    
    private int rob(int[] sum) {
        int p1 = 0; int p2 = sum[0];
        p1 = Math.max(p2, sum[1]);
        
        for (int i = 2; i < sum.length; i++) {
            int cur = Math.max(p1, p2 + sum[i]);
            p2 = p1;
            p1 = cur;
        }
        
        return p1;
    }
}

重刷时，还是看了题解才做出来，主要卡在使用map无法顺序取，没有构造出《打家劫舍》同样的代码场景

class Solution {
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        int maxVal = 0;
        for (int i : nums) {
            if (i > maxVal) maxVal = i;
        }
                
        int[] sum = new int[maxVal+1];
        for (int i : nums) {
            sum[i] += i;
        }

        int a = 0, b = 0;
        for (int i = 0; i < sum.length; i++) {
            int c = Math.max(a+sum[i], b);
            a = b;
            b = c;
        }
        return b;
    }
}

# 1720. 解码异或后的数组

class Solution {
    public int[] decode(int[] encoded, int first) {
        int[] res = new int[encoded.length+1];
        res[0] = first;
        for (int i = 1; i < res.length; i++) {
            res[i] = res[i-1] ^ encoded[i-1];
        }
        return res;
    }
}

# 474. 一和零


dfs暴力解，加cache优化，但是仍然无法AC：
class Solution {
    Map<Integer, Pair> map;
    Map<String, Integer> cache = new HashMap<>();
    public int findMaxForm(String[] strs, int m, int n) {
        // 初始化计算每个字串的0和1个数
        map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            map.put(i, cal(strs[i]));
        }
        // System.out.println("map:"+map);
        return dfs(strs, 0, m, n);
    }
    private int dfs(String[] strs, int index, int m, int n) {
         // 满足 m，n条件
        if (m < 0 || n < 0) {
            return 0;
        }
        if (index >= strs.length) {
            return 0;
        }
        int res = 0;
        for (int i = index; i < strs.length; i++) {
            // 拿到m和n
            Pair p = map.get(i);
            // System.out.println("index:"+(i+1)+"; m:"+(m-p.v0)+"; n:"+(n-p.v1)+"; cnt:"+(cnt+1)+"; tmp:"+tmp);
            Integer tmp = 0;
            if (m-p.v0 >= 0 && n-p.v1 >= 0) {
                tmp = cache.get((i+1)+";"+(m-p.v0)+";"+(n-p.v1));
                if (tmp == null) {
                    tmp = dfs(strs, i+1, m-p.v0, n-p.v1) + 1;
                    cache.put((i+1)+";"+(m-p.v0)+";"+(n-p.v1), tmp);
                }
            }
            res = Math.max(res, tmp);
        }
        return res;
    }

    private Pair cal(String s) {
        Pair p = new Pair();
        for (char c : s.toCharArray()) {
            if (c == '0') {
                p.v0++;
            } else if (c == '1') {
                p.v1++;
            }
        }
        return p;
    }

    private class Pair {
        public int v0 = 0;
        public int v1 = 0;
        public String toString() {
            return "["+v0+","+v1+"]";
        }
    }
}

动态规划：

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // dp[i][j][k] 表示最大子集是几个
        // i是0-i的字串，j是剩余多少个0，k是剩余多少个1
        int[][][] dp = new int[strs.length+1][m+1][n+1];

        for (int i = 1; i <= strs.length; i++) {
            Pair p = cal(strs[i-1]);
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    int tmp = 0;
                    if (j-p.v0>=0 && k-p.v1>=0) {
                        tmp = dp[i-1][j-p.v0][k-p.v1] + 1;
                    }
                    dp[i][j][k] = Math.max(dp[i-1][j][k], tmp);
                }
            }
        }
        return dp[strs.length][m][n];
    }

    private Pair cal(String s) {
        Pair p = new Pair();
        for (char c : s.toCharArray()) {
            if (c == '0') {
                p.v0++;
            } else if (c == '1') {
                p.v1++;
            }
        }
        return p;
    }

    private class Pair {
        public int v0 = 0;
        public int v1 = 0;
    }
}

一个月后的每日一题，仍然没有想出动态规划的思路，看了题解的提示才知道，不过编码能力有所提升：

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int l = strs.length;
        int[][][] dp = new int[l+1][m+1][n+1];
        for (int i = 1; i <= l; i++) {
            int[] cur = getCount(strs[i-1]);
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    if (cur[0] > j || cur[1] > k) {
                        dp[i][j][k] = dp[i-1][j][k];
                    } else {
                        dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-cur[0]][k-cur[1]]+1);
                    }
                }
            }
        }
        // System.out.println(Arrays.deepToString(dp));
        return dp[l][m][n];
    }
    
    private int[] getCount(String s) {
        int[] cnt = new int[2];
        for (char c : s.toCharArray()) {
            if (c == '0') {
                cnt[0]++;
            } else {
                cnt[1]++;
            }
        }
        return cnt;
    }
}

使用golang解题：

func findMaxForm(strs []string, m int, n int) int {
    l := len(strs)
    dp := make([][][]int, l+1)
    for i := range dp {
        dp[i] = make([][]int, m+1)
        for j := range dp[i] {
            dp[i][j] = make([]int, n+1)
        }
    }
    
    for i := 1; i <= l; i++ {
        cur := getCount(strs[i-1])
        for j := 0; j <= m; j++ {
            for k := 0; k <= n; k++ {
                if cur[0] > j || cur[1] > k {
                    dp[i][j][k] = dp[i-1][j][k]
                } else {
                    dp[i][j][k] = dp[i-1][j][k]
                    if dp[i-1][j][k] < dp[i-1][j-cur[0]][k-cur[1]]+1 {
                        dp[i][j][k] = dp[i-1][j-cur[0]][k-cur[1]]+1
                    }
                }
            }
        }
    }
    // fmt.Println(dp)
    return dp[l][m][n]
}

func getCount(s string) [2]int {
    var cnt [2]int
    for _, value := range s {
        cnt[value-48]++
    }
    return cnt
}

# 1486. 数组异或操作

class Solution {
    public int xorOperation(int n, int start) {
        int res = start;
        for (int i = 1; i < n; i++) {
            res ^= (2*i+start);
        }
        return res;
    }
}

# 1723. 完成所有工作的最短时间

暴力回溯：

class Solution {
    public int minimumTimeRequired(int[] jobs, int k) {
        ks = new int[k+1];
        dfs(jobs, k, 0);
        return min;
    }

    int[] ks;
    int min = Integer.MAX_VALUE;
    private void dfs(int[] jobs, int k, int index) {
        // job分配完了
        if (index >= jobs.length) {
            int max = 0;
            for (int i = 1; i <= k; i++) {
                if (ks[i] == 0) {
                    return;
                }
                max = Math.max(max, ks[i]);
            }
            min = Math.min(min, max);
            return;
        }

        // i从1开始
        for (int i = 1; i <= k; i++) {
            ks[i] += jobs[index];
            dfs(jobs, k, index+1);
            ks[i] -= jobs[index];
        }
    }
}

回溯+剪枝：

class Solution {
    public int minimumTimeRequired(int[] jobs, int k) {
        ks = new int[k+1];
        dfs(jobs, k, 0, Integer.MIN_VALUE, 1);
        return min;
    }

    int[] ks;
    int min = Integer.MAX_VALUE;
    private void dfs(int[] jobs, int k, int index, int curMax, int used) {
        if (curMax >= min) return;
        // job分配完了
        if (index >= jobs.length) {
            min = Math.min(min, curMax);
            return;
        }

        if (used <= k) {
            ks[used] = jobs[index];
            dfs(jobs, k, index+1, Math.max(curMax, ks[used]), used+1);
            ks[used] = 0;
        }

        // i从1开始
        for (int i = 1; i < used; i++) {
            ks[i] += jobs[index];
            dfs(jobs, k, index+1, Math.max(curMax, ks[i]), used);
            ks[i] -= jobs[index];
        }
    }
}

# 39. 组合总和

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, target, 0, 0, new ArrayList<>());
        return res;
    }
    List<List<Integer>> res = new ArrayList<>();
    private void dfs(int[] cd, int t, int index, int sum, List<Integer> record) {
        if (sum == t) {
            res.add(new ArrayList<>(record));
            return;
        }
        if (sum > t || index >= cd.length) {
            return;
        }

        for (int i = index; i < cd.length; i++) {
            record.add(cd[i]);
            dfs(cd, t, i, sum+cd[i], record);
            record.remove(record.size()-1);
        }
    }
}

# 40. 组合总和 II

暴力解，一看只有5%。。：

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, target, 0, 0, new ArrayList<>());
        return res;
    }

    List<List<Integer>> res = new ArrayList<>();
    Set<String> set = new HashSet<>();
    private void dfs(int[] cd, int t, int index, int sum, List<Integer> record) {
        if (sum == t) {
            String s = "";
            for (int r : record) {
                s = s.concat(String.valueOf(r)).concat(",");
            }
            if (!set.contains(s)) {
                set.add(s);
                res.add(new ArrayList<>(record));
            }
            return;
        }
        if (sum > t || index >= cd.length) {
            return;
        }

        for (int i = index; i < cd.length; i++) {
            record.add(cd[i]);
            dfs(cd, t, i+1, sum+cd[i], record);
            record.remove(record.size()-1);
        }
    }
}

排序后，树的同层中，相同的值可以直接跳过，优化到60%：

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, target, 0, 0, new ArrayList<>());
        return res;
    }
    
    List<List<Integer>> res = new ArrayList<>();
    private void dfs(int[] cd, int t, int index, int sum, List<Integer> record) {
        if (sum == t) {
            res.add(new ArrayList<>(record));
            return;
        }
        
        if (sum > t || index >= cd.length) {
            return;
        }
        
        for (int i = index; i < cd.length; i++) {
            if (i > index && cd[i] == cd[i-1]) continue;
            record.add(cd[i]);
            dfs(cd, t, i+1, sum+cd[i], record);
            record.remove(record.size()-1);
        }
    }
}

# 216. 组合总和 III

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(k, n, 0, 1, new ArrayList<>());
        return res;
    }

    List<List<Integer>> res = new ArrayList<>();
    private void dfs(int k, int n, int sum, int index, List<Integer> path) {
        if (sum == n && path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }

        if (sum > n || index > 9 || path.size() >= k) {
            return;
        }

        for (int i = index; i <= 9; i++) {
            path.add(i);
            dfs(k, n, sum+i, i+1, path);
            path.remove(path.size()-1);
        }
    }
}

# 1854. 人口最多的年份（第 240 场周赛）

class Solution {
    public int maximumPopulation(int[][] logs) {
        int[] y = new int[100+1];
        
        for (int i = 0; i < logs.length; i++) {
            int l = logs[i][0];
            int r = logs[i][1]-1;
            for (int j = l-1950; j <= r-1950; j++) {
                y[j]++;
            }
        }
        
        int res = 0;
        int max = 0;
        for (int i = 0; i < 101; i++) {
            
            if (y[i] > max) {
                max = y[i];
                res = i+1950;
            }
        }
        return res;
    }
}

# 1855. 下标对中的最大距离（第 240 场周赛）

class Solution {
    public int maxDistance(int[] n1, int[] n2) {
        int res = 0;
        int j = -1;
        for (int i = 0; i < n1.length; i++) {
            j++;
            for (; j < n2.length; j++) {
                if (n2[j] >= n1[i]) {
                    res = Math.max(res, j-i);
                } else {
                    break;
                }
            }
        }
        return res;
    }
}

# 1856. 子数组最小乘积的最大值（第 240 场周赛）

暴力法，无法AC：

class Solution {
    public int maxSumMinProduct(int[] nums) {
        int n = nums.length;
        // 找nums[i]左右大于等于他的数的范围和，也就是以nums[i]为最小值的最大范围和
        long[] left = new long[n];
        long[] right = new long[n];
        
        // right
        for (int i = n-1; i >= 0; i--) {
            int j = i;
            right[i] = nums[j];
            while (j+1 < n && nums[i] <= nums[j+1]) {
                right[i] += nums[j+1];
                j++;
            }
        }
        
        // left
        for (int i = 0; i < n; i++) {
            int j = i;
            left[i] = nums[j];
            while (j-1 >= 0 && nums[i] <= nums[j-1]) {
                left[i] += nums[j-1];
                j--;
            }
        }
        // System.out.println("left:"+Arrays.toString(left));
        // System.out.println("right:"+Arrays.toString(right));
        long res = 0;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, (left[i] + right[i] - nums[i]) * nums[i]);
        }
        int mod = (int)1e9 + 7;
        return (int)(res % mod);
    }
}

计算每个数nums[i]的左右两边最近的小于nums[i]的坐标，再计算nums数组的前缀和。通过遍历数组，利用前缀和数组获取区间和，同时比较获取最大值即可。

class Solution {
    public int maxSumMinProduct(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        
        // left
        for (int i = 0; i < n; i++) {
            left[i] = i-1;
            while (left[i] >= 0 && nums[i] <= nums[left[i]]) {
                left[i] = left[left[i]];
            }
        }
        // right
        for (int i = n-1; i >= 0; i--) {
            right[i] = i+1;
            while (right[i] <= n-1 && nums[i] <= nums[right[i]]) {
                right[i] = right[right[i]];
            }
        }
        
        // 计算前缀和
        long[] presum = new long[n];
        presum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            presum[i] = presum[i-1] + nums[i];
        }
        
        // System.out.println("left:"+Arrays.toString(left));
        // System.out.println("right:"+Arrays.toString(right));
        // System.out.println("presum:"+Arrays.toString(presum));
    
        long res = 0;
        for (int i = 0; i < n; i++) {
            int l = left[i];
            int r = right[i]-1;
            
            long ll = 0;
            if (l < 0) {
                ll = 0;
            } else {
                ll = presum[l];
            }
            res = Math.max(res, nums[i] * (presum[r] - ll));
        }
        
        int mod = (int)1e9 + 7;
        return (int)(res % mod);
    }
}

# 1482. 制作 m 束花所需的最少天数

二分法：

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        int[] b = bloomDay;
        if (m*k > b.length) return -1;
        // 找到数组的最大值、最小值
        int r = 0, l = Integer.MAX_VALUE;
        for (int i : b) {
            r = Math.max(r, i);
            l = Math.min(l, i);
        }
        // 二分法
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            int cnt = 0;
            int bloom = 0;
            for (int i = 0; i < b.length; i++) {
                if (mid >= b[i]) {
                    bloom++;
                } else {
                    bloom = 0;
                }
                
                if (bloom == k) {
                    bloom = 0;
                    cnt++;
                }
            }
            if (cnt >= m) {
                r = mid;
            } else {
                l = mid+1;
            }
        }
        return r;
    }
}

# 872. 叶子相似的树

class Solution {

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();

        post(root1, l1);
        post(root2, l2);

        if (l1.size() != l2.size()) return false;
        for (int i = 0; i < l1.size(); i++) {
            if (i >= l2.size() || !l1.get(i).equals(l2.get(i))) {
                return false;
            }
        }
        return true;
    }

    private boolean post(TreeNode n, List<Integer> list) {
        if (n == null) {
            return true;
        }

        boolean l = post(n.left, list);
        boolean r = post(n.right, list);

        if (l && r) {
            list.add(n.val);
        }

        return false;
    }
}

# 1734. 解码异或后的排列

class Solution {
    public int[] decode(int[] encoded) {
        int[] e = encoded;
        int[]  res = new int[e.length+1];
        int all = 0;
        for (int i = 1; i <= e.length+1; i++) {
            all ^= i;
        }
        int pre = 0;
        for (int i = 1; i < e.length; i+=2) {
            pre ^= e[i];
        }
        pre ^= all;
        res[0] = pre;
        for (int i = 1; i < res.length; i++) {
            res[i] = pre ^ e[i-1];
            pre = res[i];
        }
        
        return res;
    }
}

# 1310. 子数组异或查询

class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        int[][] q = queries;
        int[] prexor = new int[arr.length];
        
        prexor[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            prexor[i] = prexor[i-1] ^ arr[i];
        }
        
        int[] res = new int[q.length];
        for (int i = 0; i < q.length; i++) {
            int a = 0, b = prexor[q[i][1]];
            if (q[i][0]-1>=0) {
                a = prexor[q[i][0]-1];
                b = a ^ b;
            }
            res[i] = b;
        }
        return res;
    }
}

# 1269. 停在原地的方案数

备忘录dfs，超时：

class Solution {
    long[][] cache;
    public int numWays(int steps, int arrLen) {
        cache = new long[arrLen][steps+1];
        int mod = (int)1e9 + 7;
        return (int) (dfs(arrLen, 0,steps) % mod);
    }

    private long dfs(int arrLen, int index, int rem) {
        if (index < 0 || index >= arrLen) return 0;
        if (rem == 0 && index == 0) {
            return 1;
        }
        if (rem == 0) {
            return 0;
        }
        if (rem < 0) {
            return 0;
        }
        
        if (cache[index][rem] != 0) {
            return cache[index][rem];
        }
        
        long res = 0;

        res += dfs(arrLen, index-1, rem-1);
        res += dfs(arrLen, index, rem-1);
        res += dfs(arrLen, index+1, rem-1);

        cache[index][rem] = res;
        return res;
    }
}

由dfs改成动归实现，内存超出限制（但一定还有超时的用例，只是还没执行到- -！）：

class Solution {
    public int numWays(int steps, int arrLen) {
        int[][] dp = new int[steps+1][arrLen];
		int mod = (int)1e9 + 7;
        // init 
        // for (int j = 0; j < arrLen && j <= steps; j++) {
        //     dp[j][j] = 1;
        // }
		dp[0][0] = 1;

        // dp定义 dp[i][j] 在j位置下，操作i次后，的方案数
        // dp[i][j] 可能有三种场景状态转移过来
        for (int i = 1; i <= steps; i++) {
            for (int j = 0; j < arrLen; j++) {
				if (dp[i][j] != 0) continue;
				long res = dp[i][j];
                // 向左
                if (i-1 >= 0 && j-1 >= 0) {
                    res = (res + dp[i-1][j-1]) % mod;
                }
                // 不动
                res = (res + dp[i-1][j]) % mod;
                // 向右
                if (i-1 >= 0 && j+1 < arrLen) {
					res = (res + dp[i-1][j+1]) % mod;
                }
				dp[i][j] = (int)res;
            }
        }
		// System.out.println(Arrays.deepToString(dp));
        return dp[steps][0];
    }
}

动归，并且优化成一维数组，同时将遍历条件做限制：

class Solution {
    public int numWays(int steps, int arrLen) {
        int[] dp = new int[arrLen];
		int mod = (int)1e9 + 7;
		dp[0] = 1;
		
        for (int i = 1; i <= steps; i++) {
			int[] dp2 = new int[arrLen];
			// 时间限制卡很死，如果条件是arrLen，不优化成Math.min(arrLen, steps-i+1)，仍然会超时
            for (int j = 0; j < Math.min(arrLen, steps-i+1); j++) {
				long res = dp2[j];
                // 向左
                if (j-1 >= 0) {
                    res = (res + dp[j-1]) % mod;
                }
                // 不动
                res = (res + dp[j]) % mod;
                // 向右
                if (j+1 < arrLen) {
					res = (res + dp[j+1]) % mod;
                }
				dp2[j] = (int) res;
            }
			dp = dp2;
        }
		// System.out.println(Arrays.deepToString(dp));
        return dp[0];
    }
}

# 12. 整数转罗马数字

class Solution {
    public String intToRoman(int num) {
        int[] k = new int[]{1000, 500, 100, 50, 10, 5, 1};
        String[] v = new String[]{"M", "D", "C", "L", "X", "V", "I"};
        
        String res = "";
        while (num != 0) {
            for (int i = 0; i < 7; i++) {
                while (num >= k[i]) {
                    num -= k[i];
                    res = res + v[i];
                }
                // System.out.println(res);
                if ((i == 2 || i == 4 || i == 6) 
                    && res.length() >= 4 
                    && res.lastIndexOf(v[i]+v[i]+v[i]+v[i]) + 4 == res.length()) {
                    String rem = res.substring(0, res.length()-4);
                    if (rem.length() > 0 && rem.charAt(rem.length()-1) == v[i-1].charAt(0)) {
                        res = rem.substring(0, rem.length()-1) + v[i] + v[i-2];
                    } else {
                        res = rem + v[i] + v[i-1];
                    }
                }
            }
        }
        return res;
    }
}

# 13. 罗马数字转整数

class Solution {
    public int romanToInt(String s) {
        char[] k = new char[]{'M', 'D', 'C', 'L', 'X', 'V', 'I'};
        int[] v = new int[]{1000, 500, 100, 50, 10, 5, 1};
        
        int i = 0;
        int res = 0;
        while (i < s.length()) {
            int ki = 0;
            while (ki < 7) {
                if (i < s.length() && s.charAt(i) == k[ki]) {
                    if (i+1 < s.length() && (ki == 2 || ki == 4 || ki == 6)) {
                        if (s.charAt(i+1) == k[ki-1]) {
                            res = res + v[ki-1] - v[ki];
                            i+=2;
                            break;
                        } else if (s.charAt(i+1) == k[ki-2]) {
                            res = res + v[ki-2] - v[ki];
                            i+=2;
                            break;
                        } 
                        // else 非大于他的罗马数字
                    }
                    res += v[ki];
                    i++;
                }
                ki++;
            }
        }
        return res;
    }
}

# 421. 数组中两个数的最大异或值

使用前缀树Trie

class Solution {
    public int findMaximumXOR(int[] nums) {
        Trie t = new Trie();
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            t.insert(nums[i]);
            res = Math.max(res, t.searchMax(nums[i]));
        }
        return res;
    }
    
    class Trie {
        Trie[] next = new Trie[2];
        int val = -1;
        
        public void insert(int num) {
            int a = num;
            int cnt = 32;
            Trie t = this;
            Trie[] nx = next;
            while (cnt != 0) {
                int cur = num >>> 31;
                cur = cur & 1;
                num = num << 1;
                
                if (nx[cur] == null) {
                    nx[cur] = new Trie();
                }
                t = nx[cur];
                nx = t.next;
                
                cnt--;
            }
            t.val = a;
        }
        
        public int searchMax(int num) {
            int a = num;
            int cnt = 32;
            Trie t = this;
            Trie[] nx = next;
            while (cnt != 0) {
                int cur = num >>> 31;
                cur = cur & 1;
                num = num << 1;
                if (nx[cur^1] != null) {
                    t = nx[cur^1];
                    nx = t.next;
                } else {
                    t = nx[cur];
                    nx = t.next;
                }
                cnt--;
            }
            // System.out.println("a:"+a+"; val:"+t.val);
            return a^t.val;
        }
    }
}

# 993. 二叉树的堂兄弟节点

DFS后序遍历二叉树，用了很多变量来定义条件限制，整体代码看起来繁冗：

class Solution {
    int depth = -1;
    int x;
    int y;
    int res = 0;
    int parent = -1;
    int res_p = 0;
    public boolean isCousins(TreeNode root, int _x, int _y) {
        x = _x;
        y = _y;
        dfs(root, 0);
        return res == 1 && res_p == 1;
    }

    private boolean dfs(TreeNode node, int d) {
        if (node == null) return false;
        if (res != 0 || res_p != 0) return false;

        boolean l = dfs(node.left, d+1);
        boolean r = dfs(node.right, d+1);

        if (l || r) {
            if (parent == -1) {
                parent = node.val;
            } else if (parent != node.val) {
                res_p = 1;
            } else {
                res_p = -1;
            }
        }

        if (node.val == x || node.val == y) {
            if (depth == -1) {
                depth = d;
            } else if (depth == d){
                res = 1;
            } else {
                res = -1;
            }
            return true;
        }

        return false;
    }
}

# 1442. 形成两个异或相等数组的三元组数目

class Solution {
    public int countTriplets(int[] arr) {
        int[] prexor = new int[arr.length];
        prexor[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            prexor[i] = prexor[i-1]^arr[i];
        }
        
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int k = i+1; k < arr.length; k++) {
                if ((prexor[i] ^ prexor[k] ^ arr[i]) == 0) {
                    res += (k-i);
                }
            }
        }
        return res;
    }
}

# 1738. 找出第 K 大的异或坐标值

前缀异或+小顶堆：

class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);
        int n = matrix[0].length;
        
        int[] pre = new int[n+1];
        for (int i = 0; i < matrix.length; i++) {
            int[] cur = new int[n+1];
            for (int j = 0; j < matrix[0].length; j++) {
                cur[j+1] = matrix[i][j] ^ cur[j];
                int now = pre[j+1] ^ cur[j+1];
                pre[j+1] = now;
                
                if (pq.size() < k) {
                    pq.offer(now);
                } else if (now > pq.peek()) {
                    pq.poll();
                    pq.offer(now);
                }
            }
        }
        return pq.peek();
    }
}

# 692. 前K个高频单词

哈希表+小顶推：

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String w : words) {
            map.put(w, map.getOrDefault(w, 0)+1);
        }

        // Object[] 0:String, 1:cnt
        PriorityQueue<Object[]> pq = new PriorityQueue<>(new Comparator<Object[]>() {
            public int compare(Object[] a, Object[] b) {
                return Solution.compare(a, b);
            }
        });

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (pq.size() >= k) {
                int res = Solution.compare(pq.peek(), new Object[]{entry.getKey(), entry.getValue()});
                // System.out.println("res:"+res+"; peek:"+(String)pq.peek()[0]+"; key:"+entry.getKey());
                if (res < 0) {
                    pq.poll();
                    pq.offer(new Object[]{entry.getKey(), entry.getValue()});
                }
            } else {
                pq.offer(new Object[]{entry.getKey(), entry.getValue()});
            }
        }

        List<String> list = new ArrayList<>();
        while (pq.size() != 0) {
            list.add((String)pq.poll()[0]);
        }
        Collections.reverse(list);
        return list;
    }

    public static int compare(Object[] a, Object[] b) {
        int res = (int)a[1]-(int)b[1];
        if (res == 0) {
            String bt = (String)b[0];
            return bt.compareTo((String)a[0]);
        } else {
            return res;
        }
    }
}

# 726. 原子的数量

哈希表：

class Solution {
    public String countOfAtoms(String formula) {
        TreeMap<String, Integer> tree = new TreeMap<>();
        HashMap<String, Integer> next = new HashMap<>();
        recursive(formula, 0, next);
        for (Map.Entry<String, Integer> e : next.entrySet()) {
            tree.put(e.getKey(), e.getValue());
        }
        
        String res = "";

        for (Map.Entry<String, Integer> e : tree.entrySet()) {
            res = res + e.getKey() + (e.getValue()==1?"":e.getValue());
        }
        
        return res;
    }
    
    private int recursive(String f, int start, HashMap<String, Integer> cur) {
        
        for (int i = start; i < f.length(); ) {
            if (f.charAt(i) == 41) {
                return i+1;
            }
            
            if (f.charAt(i) == 40) {
                HashMap<String, Integer> next = new HashMap<>();
                i = recursive(f, i+1, next);
                
                // 处理数字
                int l = i;
                while (i < f.length() && isNum(f.charAt(i))) {
                    i++;
                }
                String cnt = "1";
                if (l != i) cnt = f.substring(l, i);
                
                for (Map.Entry<String, Integer> e : next.entrySet()) {
                    cur.put(e.getKey(), cur.getOrDefault(e.getKey(), 0)+(e.getValue()*Integer.valueOf(cnt)));
                }
            }
            
            // System.out.println("i:"+i+";");
            // for (Map.Entry<String, Integer> e : cur.entrySet()) {
            //     System.out.println("e.getKey():"+e.getKey()+"; e.getValue():"+e.getValue());
            // }
            
            if (i >= f.length()) return 0;
            
            // 处理大写字母
            String sc = "";
            
            int l = i;
            if (isMax(f.charAt(i))) {
                i++;
            }
            
            // 处理小写字母
            while (i < f.length() && isLittle(f.charAt(i))) {
                i++;
            }
            if (l != i) sc = f.substring(l, i);
            
            
            // 处理数字
            int cnt = 1;
            l = i;
            while (i < f.length() && isNum(f.charAt(i))) {
                i++;
            }
            if (l != i) cnt = Integer.valueOf(f.substring(l, i));
            
            if (!sc.equals("")) {
                cur.put(sc, cur.getOrDefault(sc, 0)+cnt);
            }
            // System.out.println("sc:"+sc+";"+"i:"+i);
        }
        
        return 0;
        
    }
    
    private boolean isNum(char c) {
        return c >= 48 && c <= 57;
    }
    
    private boolean isLittle(char c) {
        return c >= 97 && c <= 122;
    }
    
    private boolean isMax(char c) {
        return c >= 65 && c <= 90;
    }
}

# 1035. 不相交的线

题目同1143. 最长公共子序列 一模一样，只需要对题目进行转换即可。

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        int[][] dp = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (nums1[i-1] == nums2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }
}

# 810. 黑板异或游戏

class Solution {
    public boolean xorGame(int[] nums) {
        int xor = 0;
        for (int n : nums) {
            xor ^= n;
        }
        if (xor == 0) return true;
        
        return nums.length % 2 == 0;
    }
}

# 1707. 与数组中元素的最大异或值

使用trie树：

class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        int[][] qs = queries;
        Arrays.sort(nums);
        int[][] nq = new int[qs.length][3];
        for (int i = 0; i < qs.length; i++) {
            nq[i][0] = qs[i][0];
            nq[i][1] = qs[i][1];
            nq[i][2] = i;
        }
        Arrays.sort(nq, (a, b) ->{
            return a[1] - b[1];
        });
        
        // System.out.println(Arrays.deepToString(nq));
        Trie t = new Trie();
        
        int[] res = new int[nq.length];
        int i = 0;
        int im = 0;
        for (int[] q : nq) {
            while (im < nums.length && nums[im] <= q[1]) {
                t.insert(nums[im++]);
            }
            res[q[2]] = t.search(q[0], q[1]);
        }
        return res;
    }
    
    class Trie {
        Trie[] next = new Trie[2];
        int val = -1;
        
        public void insert(int num) {
            int a = num;
            int cnt = 32;
            Trie t = this;
            Trie[] nx = next;
            while (cnt != 0) {
                int cur = num >>> 31;
                cur = cur & 1;
                num = num << 1;
                if (nx[cur] == null) {
                    nx[cur] = new Trie();
                }
                t = nx[cur];
                nx = t.next;
                cnt--;
            }
            t.val = a;
        }
        
        public int search(int x, int m) {
            int cnt = 32;
            Trie t = this;
            Trie[] nx = next;
            int a = x;
            boolean ok = false;
            while (cnt != 0) {
                
                int cur = m >>> 31;
                cur = cur & 1;
                m = m << 1;
                
                int curx = x >>> 31;
                curx = curx & 1;
                x = x << 1;
                if (!ok) {
                    if (cur == 1) {
                        if (nx[curx^1] != null) {
                            if ((curx^1) == 0) {
                                ok = true;
                            } else {
                                // == 1
                                t = nx[curx^1];
                                nx = t.next;
                            }
                        } else {
                            if (curx == 0) {
                                ok = true;
                            } else {
                                // == 1
                                t = nx[curx];
                                nx = t.next;
                            }
                        }
                        
                    } else {
                        if (nx[cur] == null) {
                            return -1;
                        }
                        t = nx[cur];
                        nx = t.next;
                    }
                }
                
                if (ok) {
                    if (nx[curx^1] != null) {
                        t = nx[curx^1];
                    } else {
                        t = nx[curx];
                    }
                    if (t != null) {
                        nx = t.next;
                    }
                }
                
                cnt--;
            }
            return a^t.val;
        }
    }
}

另一种方法，在每个节点存储该节点的子树的最小值，这样在选择时可以及早判断。

# 5763. 哪种连续子字符串更长（第 242 场周赛）

class Solution {
    public boolean checkZeroOnes(String s) {
        int zero = 0;
        int one = 0;
        
        int cntz = 0;
        int cnto = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
                cntz++;
                cnto = 0;
            } else {
                cnto++;
                cntz = 0;
            }
            zero = Math.max(zero, cntz);
            one = Math.max(one, cnto);
        }
        return one > zero;
    }
}

# 5764. 准时到达的列车最小时速（第 242 场周赛）

二分法，比赛时想出来了，但没写出来：

class Solution {
    public int minSpeedOnTime(int[] dist, double hour) {
        if (dist.length > Math.ceil(hour)) return -1;
        int l = 1;
        int r = (int)Math.pow(10, 7);
        
        while (l < r) {
            int mid = l + (r - l)/2;
            
            double sum = 0;
            for (int i = 0; i < dist.length-1; i++) {
                sum += (dist[i] + mid - 1) / mid;
            }
            sum += (double)dist[dist.length-1] / mid;
            
            if (sum <= hour) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

# 1190. 反转每对括号间的子串

使用栈：

class Solution {
    public String reverseParentheses(String s) {
        Stack<Character> st = new Stack<>();
        int n = s.length();
        int i = 0;
        while (i < n) {
            if (s.charAt(i) == ')') {
                String ts = "";
                while (!st.isEmpty()) {
                    char tc;
                    if ((tc = st.pop()) == '(') {
                        break;
                    }
                    ts = ts + String.valueOf(tc);
                }
                int tn = ts.length();
                int ti = 0;
                while (ti < tn) {
                    st.push(ts.charAt(ti));
                    ti++;
                }
            } else {
                st.push(s.charAt(i));
            }
            i++;
        }
        
        StringBuilder res = new StringBuilder();
        while (!st.isEmpty()) {
            res = res.append(String.valueOf(st.pop()));
        }
        
        return res.reverse().toString();
    }
}

# 1787. 使所有区间的异或结果为零

class Solution {
    int INF = 0x3f3f3f3f;
    // 2^10
    int max = 1024;

    public int minChanges(int[] nums, int k) {
        int n = nums.length;
        int[][] dp = new int[k][max];
        
        // 初始化第0列
        // i = 0时：当前列总数-当前列为j的个数
        int a = 0;
        int b = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        while (a < n) {
            map.put(nums[a], map.getOrDefault(nums[a], 0)+1);
            a += k;
            b++;
        }
        int[] pre_min = new int[k];
        Arrays.fill(pre_min, INF);
        for (int j = 0; j < max; j++) {
            dp[0][j] = b - map.getOrDefault(j, 0);
            pre_min[0] = Math.min(pre_min[0], dp[0][j]);
        }
        
        // 遍历k列
        int min = INF;
        for (int i = 1; i < k; i++) {
            int ti = i;
            int size = 0;
            map = new HashMap<>();
            while (ti < n) {
                map.put(nums[ti], map.getOrDefault(nums[ti], 0)+1);
                ti += k;
                size++;
            }
            
            // 获取当前列，需要修改成j的次数
            for (int j = 0; j < max; j++) {
                // i != 0：dp[i][j] = min(dp[i-1][j^i]+当前修改为j的次数)
                min = pre_min[i-1] + size;
                for (int key : map.keySet()) {
                    min = Math.min(min, dp[i-1][j^key] + (size-map.get(key)));
                    pre_min[i] = Math.min(pre_min[i], min);
                }
                dp[i][j] = min;
            }
        }
        
        return dp[k-1][0];
    }
}

# 477. 汉明距离总和

class Solution {
    public int totalHammingDistance(int[] nums) {
        int[] bits = new int[32];
        
        for (int n : nums) {
            int i = 0;
            while (i < 32) {
                bits[i] += (n & 1);
                n = n >>> 1;
                i++;
            }
        }
        
        int res = 0;
        int n = nums.length;
        for (int b : bits) {
            res += (b * (n-b));
        }
        return res;
    }
}

# 56. 合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        int[][] it = intervals;
        Arrays.sort(it, (a, b) -> a[0]-b[0]);
        int i = 1, end = 0;
        while (i < it.length) {
            if (it[end][1] >= it[i][0]) {
                it[end][1] = it[end][1] > it[i][1] ? it[end][1] : it[i][1];
            } else {
                end++;
                it[end] = it[i];
            }
            i++;
        }
        return Arrays.copyOf(it, end+1);
    }
}

# 231. 2的幂

位运算，向右移位，计数二进制1的个数，如果只有一个表示为2的幂次方：

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        int cnt = 0;
        while (n != 0) {
            if ((n & 1) == 1) cnt++;
            n = n >>> 1;
        }
        return cnt == 1;
    }
}

增强型移位方式，直接执行移位快速消除最近的1，如果n不等于0则不是2的幂次方：

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n-1)) == 0;
    }
}

官方提供的反码解法：

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & -n) == n;
    }
}

# 5754. 长度为三且各字符不同的子字符串（第 53 场双周赛）

简单的题做得超复杂，周赛最后只做了这一道题，我好菜：

class Solution {
    public int countGoodSubstrings(String s) {
        int l = 0, r = 1;
        int[] map = new int[26];
        Arrays.fill(map, -1);
        map[s.charAt(l)-'a'] = l;
        int res = 0;
        while (r < s.length()) {
            if (map[s.charAt(r)-'a'] != -1) {
                // System.out.println("r:"+r+"; map[s.charAt(r)-'a']:"+map[s.charAt(r)-'a']);
                if (r - map[s.charAt(r)-'a'] < 3) {
                    int cnt = r - l - 2;
                    // System.out.println(cnt);
                    if (cnt > 0) res += cnt;
                    l = map[s.charAt(r)-'a']+1;
                    r = l;
                    // System.out.println(l);
                    map = new int[26];
                    Arrays.fill(map, -1);
                    map[s.charAt(l)-'a'] = l;
                } else {
                    map[s.charAt(r)-'a'] = r;
                }
            } else {
                map[s.charAt(r)-'a'] = r;
            }
            r++;
        }
        int cnt = r - l - 2;
        // System.out.println(cnt);
        if (cnt > 0) res += cnt;
        return res;
    }
}

# 5772. 检查某单词是否等于两单词之和（第 243 场周赛）

比赛时写得比较繁冗，赛后优化代码结构，逻辑不变：

class Solution {
    public boolean isSumEqual(String firstWord, String secondWord, String targetWord) {
        return Integer.valueOf(convert(firstWord)) + Integer.valueOf(convert(secondWord)) == Integer.valueOf(convert(targetWord));
    }
    
    private String convert(String s) {
        String res = "";
        for (char c : s.toCharArray()) {
            res =  res + (c-'a');
        }
        return res;
    }
}

# 5773. 插入后的最大值（第 243 场周赛）

先是纯暴力思路，超时，以后要先判断是否存在超时可能，如果优化思路的代码复杂度相差不大，直接上优化思路：

class Solution {
    public String maxValue(String n, int x) {
        boolean neg = false;
        if (n.charAt(0) == '-') neg = true;
        String res = null;
        if (neg) {
            for (int i = 0; i < n.length(); i++) {
                if (n.charAt(i) == '-') {
                    continue;
                }
                int nx = n.charAt(i)-'0';
                if (nx > x) {
                    // insert
                    res = insert(n, i, x);
                    x = -1;
                    break;
                }
                if (x != -1) {
                    res = insert(n, n.length(), x);
                }
            }
        } else {
            for (int i = 0; i < n.length(); i++) {
                int nx = n.charAt(i)-'0';
                // System.out.println(nx);
                if (nx < x) {
                    // insert
                    res = insert(n, i, x);
                    x = -1;
                    break;
                }
            }
            if (x != -1) {
                res = insert(n, n.length(), x);
            }
            
        }
        
        return res;
    }
    
    private String insert(String s, int index, int x) {
        // System.out.println("index:" + index);
        char[] cs = new char[s.length()+1];
        int i = 0, it = 0;
        boolean ok = false;
        if (index >= s.length()) {
            // 要放到最后了
            cs[s.length()] = String.valueOf(x).charAt(0);
            // System.out.println(cs[s.length()]);
        } else if (index < 0) {
            // 放最前面
            cs[0] = String.valueOf(x).charAt(0);
            // System.out.println(cs[it]);
            it++;
        }
        for (; i < s.length(); ) {
            if (it == index) {
                cs[it] = String.valueOf(x).charAt(0);
                it++;
                continue;
            }
            cs[it] = s.charAt(i);
            i++;
            it++;
        }
        
        return new String(cs);
    }
}

优化成一遍循环，边遍历边复制到新char数组中：

class Solution {
    public String maxValue(String n, int x) {
        char[] cs = new char[n.length()+1];
        boolean neg = false;
        if (n.charAt(0) == '-') neg = true;
        for (int i = 0; i < n.length(); i++) {
            cs[i] = n.charAt(i);
            if (n.charAt(i) == '-') continue;
            int nx = n.charAt(i)-'0';
            if (neg && nx > x) {
                // insert
                insert(n, cs, i, x);
                x = -1;
                break;
            } else if (!neg && nx < x) {
                // insert
                insert(n, cs, i, x);
                x = -1;
                break;
            }
        }
        if (x != -1) {
            insert(n, cs, n.length(), x);
        }
        return new String(cs);
    }
    
    private void insert(String s, char[] cs, int index, int x) {
        int i = index, it = index;
        boolean ok = false;
        if (index >= s.length()) {
            // 要放到最后了
            cs[s.length()] = String.valueOf(x).charAt(0);
            return;
        } else if (index < 0) {
            // 放最前面
            cs[0] = String.valueOf(x).charAt(0);
            i = 0;
            it = 1;
        }
        for (; i < s.length(); ) {
            if (it == index) {
                cs[it] = String.valueOf(x).charAt(0);
                it++;
                continue;
            }
            cs[it] = s.charAt(i);
            i++;
            it++;
        }
    }
}

# 1074. 元素和为目标值的子矩阵数量

同363题，为它的简化版，使用二维前缀和+哈希表：

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int[][] ma = matrix;
        int n = ma.length, m = ma[0].length;
        int[][] pre = new int[n+1][m+1];
        for (int r = 1; r <= n; r++) {
            for (int c = 1; c <= m; c++) {
                pre[r][c] = pre[r-1][c] + pre[r][c-1] - pre[r-1][c-1] + ma[r-1][c-1];
            }
        }
        // System.out.println(Arrays.deepToString(pre));
        int cnt = 0;
        for (int top = 1; top <= n; top++) {
            for (int bot = top; bot <= n; bot++) {
                Map<Integer, Integer> map = new HashMap<>();
                for (int c = 1; c <= m; c++) {
                    int right = pre[bot][c] - pre[top-1][c];
                    if (right == target) cnt++;
                    if (map.containsKey(right-target)) cnt += map.get(right-target);
                    map.put(right, map.getOrDefault(right, 0)+1);
                }
            }
        }
        return cnt;
    }
}

# 342. 4的幂

class Solution {
    public boolean isPowerOfFour(int n) {
        return n > 0 && (n & (n-1)) == 0 && (n & 0x55555555) == n;
    }
}

# 664. 奇怪的打印机

动态规划：

class Solution {
    public int strangePrinter(String s) {
        int INF = Integer.MAX_VALUE;
        int n = s.length();
        int[][] dp = new int[n][n];
        
        for (int i = n-1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i+1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i][j-1];
                } else {
                    dp[i][j] = INF;
                    for (int k = i; k < j; k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j]);
                    }
                }
            }
        }
        return dp[0][n-1];
    }
}

# 1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？

class Solution {
    public boolean[] canEat(int[] candiesCount, int[][] queries) {
        int[][] q = queries;
        int[] cd = candiesCount;
        int n = q.length;
        boolean[] res = new boolean[n];
        
        long[] pre = new long[cd.length+1];
        for (int i = 1; i <= cd.length; i++) {
            pre[i] = pre[i-1] + cd[i-1];
        }
        // System.out.println(Arrays.toString(pre));
        for (int i = 0; i < q.length; i++) {
            long curSum = pre[q[i][0]+1];
            long preSum = pre[q[i][0]];
            long min = q[i][1];
            long cap = q[i][2];
            long max = (min+1)*cap;
            // System.out.println("curSum:"+curSum+"; preSum:"+preSum+"; min:"+min+"; max:"+max);
            if (min < curSum && max >= preSum+1) {
                res[i] = true;
            } else {
                res[i] = false;
            }
        }
        return res;
    }
}

# 525. 连续数组

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n+1];
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i-1] + (nums[i-1] == 0 ? -1 : nums[i-1]);
        }
        // System.out.println(Arrays.toString(pre));
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        int res = 0;
        for (int i = 1; i <= n; i++) {
            // System.out.println(map.keySet().toString());
            Integer preIndex = map.get(pre[i]);
            if (preIndex != null) {
                res = Math.max(res, i - preIndex);
            } else {
                map.put(pre[i], i);
            }
        }
        return res;
    }
}

# 203. 移除链表元素

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode h =  new ListNode(0, head);
        ListNode pre = h;
        
        while (head != null) {
            if (head.val == val) {
                pre.next = head.next;
                head = head.next;
            } else {
                pre = head;
                head = head.next;
            }
        }
        return h.next;
    }
}

# 151. 翻转字符串里的单词

效率不高的go写法：

func reverseWords(s string) string {
    arr := strings.Fields(s)
    res := ""
    for i := len(arr)-1; i >= 0; i-- {
        res = res + arr[i] + " "
    }
    return strings.TrimRight(res, " ")
}

超100%的go写法：

func reverseWords(s string) string {
    arr := strings.Fields(s)
    for l := 0; l < len(arr)/2; l++ {
        r := len(arr)-1-l
        arr[l], arr[r] = arr[r], arr[l]
    }
    return strings.Join(arr, " ")
}

# 1049. 最后一块石头的重量 II

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int s : stones) {
            sum += s;
        }
        int sum2 = sum/2;
        int n = stones.length;
        boolean[][] dp = new boolean[n+1][sum2+1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= sum2; j++) {
                if (stones[i-1] > j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-stones[i-1]];
                }
            }
        }
        for (int j = sum2; j >= 0; j--) {
            if (dp[n][j]) {
                return sum - 2*j;
            }
        }
        return 0;
    }
}

func lastStoneWeightII(stones []int) int {
    st := stones
    n := len(st)
    sum := 0
    for i := range st {
        sum += st[i]
    }
    m := sum>>1
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, m+1)
    }
    
    for i := 1; i <= n; i++ {
        x := st[i-1]
        for j := 0; j <= m; j++ {
            dp[i][j] = dp[i-1][j]
            if j >= x {
                tt := dp[i-1][j-x]+x
                if tt > dp[i][j] {
                    dp[i][j] = tt
                }
            }
        }
    }
    
    res := sum - 2*dp[n][m]
    if res < 0 {
        return -res
    }
    return res
}

# 879. 盈利计划

func profitableSchemes(n int, minProfit int, group []int, profit []int) (sum int) {
    // i 前几个group
    // j >= 0  j <= n
    // k profit
    const mod int = 1e9 + 7
    len := len(group)
    mp := minProfit
    
    dp := make([][][]int, len+1)
    for i := range dp {
        dp[i] = make([][]int, n+1)
        for j := range dp[i] {
            dp[i][j] = make([]int, mp+1)
        }
    }
    dp[0][0][0] = 1
    
    for i, gval := range group {
        earn := profit[i]
        for j := 0; j <= n; j++ {
            for k := 0; k <= mp; k++ {
                if j < gval {
                    dp[i+1][j][k] = dp[i][j][k]
                } else {
                    dp[i+1][j][k] = (dp[i][j][k] + dp[i][j-gval][max(0, k-earn)]) % mod
                }
            }
        }
    }
    
    for _, d := range dp[len] {
        sum = (sum + d[mp]) % mod
    }
    return 
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

# 589. N 叉树的前序遍历

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        f(root);
        return res;
    }
    
    private void f(Node node) {
        if (node == null) return;
        res.add(node.val);
        List<Node> list = node.children;
        for (Node n : list) {
            f(n);
        }
    }
}

func preorder(root *Node) []int {
    res := []int{}
    recursive(root, &res)
    return res
}

func recursive(node *Node, res *[]int) {
    if node == nil {
        return
    }
    *res = append(*res, node.Val)
    for _, n := range node.Children {
        recursive(n, res)
    }
}

# 279. 完全平方数

动规：

class Solution {
    public int numSquares(int n) {
        int INF = 0x3f3f3f3f;
        int[] dp = new int[n+1];
        for (int i = 1; i <= n; i++) {
            dp[i] = INF;
            for (int j = 1; j*j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i-j*j]);
            }
            dp[i]++;
        }
        // System.out.println(Arrays.toString(dp));
        return dp[n];
    }
}

go：

func numSquares(n int) int {
    dp := make([]int, n+1)
    INF := 0x3f3f3f3f
    for i := 1; i <= n; i++ {
        dp[i] = INF
        for j := 1; j*j <= i; j++ {
            dp[i] = min(dp[i], dp[i-j*j])
        }
        dp[i]++
    }
    return dp[n]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 1893. 检查是否区域内所有整数都被覆盖（第 54 场双周赛）

暴力解：

class Solution {
    public boolean isCovered(int[][] ranges, int left, int right) {
        for (int x = left; x <= right; x++) {
            boolean ok = false;
            for (int[] r : ranges) {
                if (x >= r[0] && x <= r[1]) {
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                return false;
            }
        }
        return true;
    }
}

差分数组，go：

func isCovered(ranges [][]int, left int, right int) bool {
    // diff := make([]int, 52)
    diff := [52]int{}
    for _, r := range ranges {
        diff[r[0]]++
        diff[r[1]+1]--
    }
    
    pre := 0
    for i, d := range diff {
        // 前缀条件可以直接写入if中
        if pre += d; i >= left && i <= right && pre == 0 {
            return false;
        }
    }
    return true;
}

# 1894. 找到需要补充粉笔的学生编号（第 54 场双周赛）

基本属于暴力模拟+前缀和：

class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long[] pre = new long[n];
        pre[0] = chalk[0];
        for (int i = 1; i < chalk.length; i++) {
            pre[i] = pre[i-1] + chalk[i];
        }
        
        while (k >= pre[n-1]) {
            k -= pre[n-1];
        }
        if (k == 0) {
            return 0;
        }
        
        int i = n-2;
        while (i >= 0 && k >= 0) {
            // System.out.println("k:"+k+"; pre[i]:"+pre[i]);
            if (k >= pre[i]) {
                k -= pre[i];
                break;
            } else {
                i--;
            }
        }
        return i+1;
    }
}

取模+前缀和：

func chalkReplacer(chalk []int, k int) int {
    sum := 0
    for _, c := range chalk {
        sum += c
    }
    k %= sum
    
    pre := 0
    for i, c := range chalk {
        pre += c
        if pre > k {
            return i
        }
    }
    return -1
}

做个小优化，不需要记录前缀和，只需要将k减去当前chalk[i]：

func chalkReplacer(chalk []int, k int) int {
    sum := 0
    for _, c := range chalk {
        sum += c
    }
    k %= sum
    
    for i, c := range chalk {
        if k < c {
            return i
        }
        k -= c
    }
    // 必有结果，不会执行此步，随意返回一个数即可
    return -1
}

# 1449. 数位成本和为目标值的最大数字

动规+贪心：

class Solution {
    public String largestNumber(int[] cost, int target) {
        int t = target;
        int[] dp = new int[t+1];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= 9; i++) {
            int c = cost[i-1];
            for (int j = c; j <= t; j++) {
                dp[j] = Math.max(dp[j], dp[j-c]+1);
            }
        }
        
        if (dp[t] < 0) {
            return "0";
        }

        String res = "";
        for (int i = 9, j = t; i >= 1; i--) {
            int c = cost[i-1];
            while (j >= c && dp[j] == dp[j-c]+1) {
                res += String.valueOf(i);
                j -= c;
            }
        }
        return res;
    }
}

# 374. 猜数字大小

二分法，go解法：

func guessNumber(n int) int {
    l, r := 1, n
    for l < r {
        mid := l + ((r-l)>>1)
        res := guess(mid)
        if res == 0 {
            return mid
        } else if res == -1 {
            r = mid
        } else {
            l = mid+1
        }
    }
    return r
}

# 221. 最大正方形

动态规划：

class Solution {
    public int maximalSquare(char[][] matrix) {
        char[][] ma = matrix;
        int max = 0;
        int n = ma.length;
        int m = ma[0].length;
        int[][] dp = new int[n][m];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (ma[i][j] == '0') {
                    dp[i][j] = 0;
                } else {
                    // up/left/upleft(ul)
                    int up = 0, left = 0, ul = 0;
                    if (i>=1) up = dp[i-1][j];
                    if (j>=1) left = dp[i][j-1];
                    if (i>=1 && j>=1) ul = dp[i-1][j-1];
                    
                    dp[i][j] = 1;
                    if (up != 0 && left != 0 && ul !=0) {
                        dp[i][j] = Math.min(up, Math.min(left, ul)) + 1;
                    }
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        // System.out.println(Arrays.deepToString(dp));
        return max*max;
    }
}

# 64. 最小路径和

动态规划：

class Solution {
    public int minPathSum(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] dp = new int[n][m];
        
        // init
        dp[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        
        for (int j = 1; j < m; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                int up = dp[i-1][j];
                int left = dp[i][j-1];
                dp[i][j] = Math.min(up, left) + grid[i][j];
            }
        }
        // System.out.println(Arrays.deepToString(dp));
        return dp[n-1][m-1];
    }
}

# 1109. 航班预订统计

差分数组：

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] diff = new int[n+1];
        for (int[] b : bookings) {
            diff[b[0]-1] += b[2];
            diff[b[1]] -= b[2]; 
        }

        int[] res = new int[n];
        int cur = 0;
        for (int i = 0; i < n; i++) {
            cur += diff[i];
            res[i] = cur;
        }
        return res;
    }
}

# 852. 山脉数组的峰顶索引

二分法：

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 0, r = n-1;
        
        while (l < r) {
            int mid = l + ((r-l)>>1)+1;
            // System.out.println(arr[mid]);
            if (arr[mid-1] < arr[mid] && arr[mid] > arr[mid+1]) {
                return mid;
            } else if (arr[mid-1] < arr[mid]) {
                l = mid;
            } else {
                r = mid-1;
            }
        }
        return l;
    }
}

# 877. 石子游戏

动态规划：

class Solution {
    public boolean stoneGame(int[] piles) {
        int[] p = piles;
        int n = p.length;
        int[][] dp = new int[n][n];
        // init
        for (int i = 0; i < n; i++) {
            dp[i][i] = p[i];
        }
        for (int i = n-1; i >= 0; i--) {
            for (int j = i+1; j < n; j++) {
                dp[i][j] = Math.max(p[i]-dp[i+1][j], p[j]-dp[i][j-1]);
            }
        }
        return dp[0][n-1] > 0;
    }
}

博弈论：

class Solution {
    public boolean stoneGame(int[] piles) {
        return true;
    }
}

# 486. 预测赢家

动态规划：

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int[] p = nums;
        int n = nums.length;
        int[][] dp = new int[n][n];
        // init
        for (int i = 0; i < n; i++) {
            dp[i][i] = p[i];
        }
        for (int i = n-1; i >= 0; i--) {
            for (int j = i+1; j < n; j++) {
                dp[i][j] = Math.max(p[i]-dp[i+1][j], p[j]-dp[i][j-1]);
            }
        }
        return dp[0][n-1] >= 0;
    }
}

# 65. 有效数字

有效自动机：

class Solution {
    public boolean isNumber(String s) {
        tt state = tt.init;
        for (int i = 0; i < s.length(); i++) {
            ct charType = check(s.charAt(i));
            // System.out.println("state:"+state+"; charType:"+charType);
            if (transfer.get(state).containsKey(charType)) {
                state = transfer.get(state).get(charType);
            } else {
                return false;
            }
        }
        
        return state == tt.integer || state == tt.point_number 
            || state == tt.exponent_number || state == tt.point_int;
    }
    
    public static ct check(char ch) {
        if (ch >= '0' && ch <= '9') {
            return ct.number;
        } else if (ch == 'e' || ch == 'E') {
            return ct.echar;
        } else if (ch == '.') {
            return ct.point;
        } else if (ch == '+' || ch == '-') {
            return ct.sign;
        } else {
            return ct.illegal;
        }
    }
    
    // pre state get curr state collections
    // loop string, get per postion's char
    // example: get initState Map<charType, initState -> transferType>
    public static final Map<tt, Map<ct, tt>> transfer = new HashMap<>();
    static {
        Map<ct, tt> initMap = new HashMap<>();
        initMap.put(ct.sign, tt.sign);
        initMap.put(ct.point, tt.point_w_int);
        initMap.put(ct.number, tt.integer);
        transfer.put(tt.init, initMap);

        Map<ct, tt> signMap = new HashMap<>();
        signMap.put(ct.number, tt.integer);
        signMap.put(ct.point, tt.point_w_int);
        transfer.put(tt.sign, signMap);
        
        Map<ct, tt> intMap = new HashMap<>();
        intMap.put(ct.number, tt.integer);
        intMap.put(ct.point, tt.point_int);
        intMap.put(ct.echar, tt.echar);
        transfer.put(tt.integer, intMap);
        
        Map<ct, tt> pointMap = new HashMap<>();
        pointMap.put(ct.number, tt.point_number);
        pointMap.put(ct.echar, tt.echar);
        transfer.put(tt.point_int, pointMap);
        
        Map<ct, tt> wPointMap = new HashMap<>();
        wPointMap.put(ct.number, tt.point_number);
        transfer.put(tt.point_w_int, wPointMap);
        
        Map<ct, tt> pointNumberMap = new HashMap<>();
        pointNumberMap.put(ct.number, tt.point_number);
        pointNumberMap.put(ct.echar, tt.echar);
        transfer.put(tt.point_number, pointNumberMap);
        
        Map<ct, tt> echarMap = new HashMap<>();
        echarMap.put(ct.sign, tt.exponent_sign);
        echarMap.put(ct.number, tt.exponent_number);
        transfer.put(tt.echar, echarMap);
        
        Map<ct, tt> expSignMap = new HashMap<>();
        expSignMap.put(ct.number, tt.exponent_number);
        transfer.put(tt.exponent_sign, expSignMap);
        
        Map<ct, tt> expNumMap = new HashMap<>();
        expNumMap.put(ct.number, tt.exponent_number);
        transfer.put(tt.exponent_number, expNumMap);
    }
    
    // CharType
    public enum ct {
        sign,
        number,
        point,
        echar,
        illegal,
        ;
    }
    
    // TransferType
    public enum tt {
        init,
        sign,
        integer,
        point_w_int,
        point_int,
        point_number,
        echar,
        exponent_sign,
        exponent_number,
        ;
    }
}

# 1239. 串联字符串的最大长度

回溯+位运算：

class Solution {
    int res = 0;
    public int maxLength(List<String> arr) {
        List<Integer> ms = new ArrayList<>();
        
        for (String s : arr) {
            int mask = 0;
            for (char c : s.toCharArray()) {
                int ci = c - 'a';
                int t = mask;
                t |= 1 << ci;
                if (mask == t) {
                    mask = 0;
                    break;
                }
                mask = t;
            }
            if (mask > 0) {
                ms.add(mask);
            }
        }
        
        for (int i = 0; i < ms.size(); i++) {
            recursive(ms, i, ms.get(i));
        }
        
        return res;
    }
    
    private void recursive(List<Integer> ms, int i, int mask) {
        if (i == ms.size()-1) {
            res = Math.max(res, Integer.bitCount(mask));
            return;
        }
        
        // select current
        if ((mask & ms.get(i+1)) == 0) {
            recursive(ms, i+1, mask | ms.get(i+1));
        }
        
        // skip current
        recursive(ms, i+1, mask);
    }
}

# LCS 01. 下载插件（微软专场竞赛）

求极限的平方数次数，很简单的题，这里做的复杂了：

class Solution {
    public int leastMinutes(int n) {
        int cnt = 0;
        int INF = 10_00_00;
        int init = 1;
        
        while (init < n) {
            cnt++;
            init += init;
        }
        if (init >= n) {
            cnt++;
        }
        return cnt;
    }
}

# LCS 02. 完成一半题目（微软专场竞赛）

统计每个数字出现的次数，再排序：

class Solution {
    public int halfQuestions(int[] q) {
        int[] r = new int[1001];
        
        for (int i : q) {
            r[i]++;
        }
        
        int n = q.length / 2;
        
        Arrays.sort(r);
        
        int cnt = 0;
        for  (int i = r.length-1; i >= 0 && n > 0; i--) {
            cnt++;
            n -= r[i];
        }
        
        return cnt;
    }
}

# 5788. 字符串中的最大奇数（第 246 场周赛）

class Solution {
    public String largestOddNumber(String num) {
        String res = "";
        int n = num.length();
        for (int i = n-1; i >= 0; i--) {
            char c = num.charAt(i);
            if (c == '1' || c == '3' || c == '5' || c == '7' || c == '9') {
                return num.substring(0, i+1);
            }
        }
        return res;
    }
}

# 5789. 你完成的完整对局数（第 246 场周赛）

分析所有场景，但是有很多细节又都没考虑到，导致比赛时间内没有完成。。。太菜了。

class Solution {
    public int numberOfRounds(String startTime, String finishTime) {
        String[] _s = startTime.split(":");
        String[] _f = finishTime.split(":");
        int[] s = new int[]{Integer.parseInt(_s[0]), Integer.parseInt(_s[1])};
        int[] f = new int[]{Integer.parseInt(_f[0]), Integer.parseInt(_f[1])};
        
        int res = 0;
        int b1 = f[0] - s[0];
        int b2 = f[1] - s[1];
        
        boolean neg = false;
        if (b1 < 0 || (b1 == 0 && b2 < 0)) {
            res += (24-s[0])*4;
            b1 = f[0];
            neg = true;
        }
        
        res += (b1*4);
        
        if (b2 <= 0) {
            neg = true;
        }
        
        // System.out.println("a:"+res);
        // System.out.println("b2:"+b2);
        // System.out.println("s1:"+s[1]);
        // System.out.println("f1:"+f[1]);
        int ff = (f[1] / 15) * 15;
        int ss = (s[1] % 15) == 0? s[1] : (s[1]/15+1)*15;
        if (ss > ff) {
            neg = true;
        }
        
        if (neg) {
            f[1]+=60;
            ff = (f[1] / 15) * 15;
            // int ss = (s[1] % 15) == 0? s[1] : (s[1]/15+1)*15;
            // System.out.println("ss:"+ss);
            // System.out.println("ff:"+ff);
            int cnt = 0;
            while (ff - ss >= 15) {
                cnt++;
                ss += 15;
            }
            res -= (4-cnt);
            // System.out.println("cnt:"+cnt);
        } else {
            int cnt = 0;
            while (ff - ss >= 15) {
                cnt++;
                ss += 15;
            }
            res += cnt;
            // System.out.println("ss:"+ss);
            // System.out.println("ff:"+ff);
            // System.out.println("cnt:"+cnt);
        }
        
        return res;
    }
}

# 1600. 皇位继承顺序

纯模拟，多叉树：

class ThroneInheritance {
    Node root;
    Map<String, Node> map = new HashMap<>();

    public ThroneInheritance(String kingName) {
        root = new Node(kingName);
        map.put(kingName, root);
    }
    
    public void birth(String parentName, String childName) {
        Node n = map.get(parentName).addChild(childName);
        map.put(childName, n);
    }
    
    public void death(String name) {
        map.get(name).live = false;
    }
    
    public List<String> getInheritanceOrder() {
        return root.getInherit();
    }
    
    class Node {
        boolean live;
        String name;
        ArrayList<Node> next;
        public Node(String name) {
            next = new ArrayList<>();
            this.name = name;
            this.live = true;
        }
        
        public Node addChild(String name) {
            Node n = new Node(name);
            next.add(n);
            return n;
        }
        
        public List<String> getInherit() {
            List<String> res = new ArrayList<>();
            recursive(this, res);
            return res;
        }
        
        private void recursive(Node node, List<String> res) {
            if (node == null) {
                return;
            }
            if (node.live) {
                res.add(node.name);
            }
            
            for (Node n : node.next) {
                recursive(n, res);
            }
        }
    }
}

# 641. 设计循环双端队列

使用双向链表实现：

class MyCircularDeque {
    LinkedList<Node> list = new LinkedList<>();
    int max;
    int size;
    
    class Node {
        int val;
        public Node(int val) {
            this.val = val;
        }
    }
    
    public MyCircularDeque(int k) {
        max = k;
        size = 0;
    }
    
    public boolean insertFront(int value) {
        if (size >= max) return false;
        
        list.addFirst(new Node(value));
        size++;
        return true;
    }
    
    public boolean insertLast(int value) {
        if (size >= max) return false;
        
        list.addLast(new Node(value));
        size++;
        return true;
    }
    
    public boolean deleteFront() {
        if (size <= 0) return false;
        
        list.removeFirst();
        size--;
        return true;
    }
    
    public boolean deleteLast() {
        if (size <= 0) return false;
        
        list.removeLast();
        size--;
        return true;
    }
    
    public int getFront() {
        if (size <= 0) return -1;
        
        return list.peekFirst().val;
    }
    
    public int getRear() {
        if (size <= 0) return -1;
        
        return list.peekLast().val;
    }
    
    public boolean isEmpty() {
        return size <= 0;
    }
    
    public boolean isFull() {
        return size >= max;
    }
}

数组实现，利用指针移动，完成双端循环。

class MyCircularDeque {
    int[] data;
    int front = 0, last = 0;
    int size = 0;
    int len = 0;

    public MyCircularDeque(int k) {
        data = new int[k];
        len = k;
        last = k - 1;
    }
    
    public boolean insertFront(int value) {
        if (isFull()) return false;
        front = front == 0 ? len - 1 : front - 1;
        size++;
        data[front] = value;
        return true;
    }
    
    public boolean insertLast(int value) {
        if (isFull()) return false;
        last = last == len - 1 ? 0 : last + 1;
        size++;
        data[last] = value;
        return true;
    }
    
    public boolean deleteFront() {
        if (isEmpty()) return false;
        front = front == len - 1 ? 0 : front + 1;
        size--;
        return true;
    }
    
    public boolean deleteLast() {
        if (isEmpty()) return false;
        last = last == 0 ? len - 1 : last - 1;
        size--;
        return true;
    }
    
    public int getFront() {
        if (isEmpty()) return -1;
        return data[front];
    }
    
    public int getRear() {
        if (isEmpty()) return -1;
        return data[last];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == len;
    }
}

# 401. 二进制手表

反向枚举时间，如果位数等于入参个数，记录即可：

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        int h = 12;
        int m = 60;
        List<String> res = new ArrayList<>();
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < m; j++) {
                int cnt = Integer.bitCount(i) + Integer.bitCount(j);
                if (cnt == turnedOn) {
                    res.add(i + ":" + (j < 10 ? "0"+j : j));
                }
            }
        }
        return res;
    }
}

# 剑指 Offer 38. 字符串的排列

全排列去重，相当于是固定某个字符在同一个位置上：

class Solution {
    private List<String> res = new ArrayList<>();
    public String[] permutation(String s) {
        char[] cs = s.toCharArray();
        Arrays.sort(cs);
        
        f(new String(cs), 0, new boolean[s.length()], new StringBuilder());
        
        String[] result = new String[res.size()];
        int i = 0;
        for (String str : res) {
            result[i++] = str;
        }
        
        return result;
    }
    
    private void f(String s, int pos, boolean[] record, StringBuilder sb) {
        if (s.length() == sb.length()) {
            res.add(sb.toString());
            return;
        }
        
        char pre = 0;
        for (int i = 0; i < s.length(); i++) {
            if (record[i] || pre == s.charAt(i)) continue;
            record[i] = true;
            pre = s.charAt(i);
            sb.append(s.charAt(i));
            
            f(s, pos+1, record, sb);
            
            // restore
            record[i] = false;
            sb.delete(sb.length()-1, sb.length());
        }
    }
}

# 剑指 Offer 15. 二进制中1的个数

同191题 消除二进制最后的一位1，记录消除的次数：

public class Solution {
    public int hammingWeight(int n) {
        int cnt = 0;
        while (n != 0) {
            n = n & (n-1);
            cnt++;
        }
        return cnt;
    }
}

go解法：

func hammingWeight(num uint32) int {
    var cnt int
    for num != 0 {
        num = num & (num-1)
        cnt++
    }
    return cnt
}

// 优化写法：
func hammingWeight(num uint32) (cnt int) {
    for ; num != 0 ; num = num & (num-1) {
        cnt++
    }
    return
}

# 149. 直线上最多的点数

求三点之间的斜率，但由于除法存在精度问题，所以将公式化为乘法，判断三个点是否相等即可：

class Solution {
    public int maxPoints(int[][] points) {
        int[][] ps = points;
        int n = ps.length;
        int res = 1;
        for (int i = 0; i < n; i++) {
            int[] x = ps[i];
            
            for (int j = i+1; j < n; j++) {
                int[] y = ps[j];
                int cnt = 2;
                for (int k = j+1; k < n; k++) {
                    int[] p = ps[k];
                    int r1 = (y[0]-x[0])*(p[1]-y[1]);
                    int r2 = (y[1]-x[1])*(p[0]-y[0]);
                    if (r1 == r2) cnt++;
                }
                res = Math.max(res, cnt);
            }
        }
        
        return res;
    }
}

go解法：

func maxPoints(points [][]int) int {
    ps := points
    n := len(ps)
    res := 1
    for i := 0; i < n; i++ {
        x := ps[i]
        
        for j := i+1; j < n; j++ {
            y := ps[j]
            cnt := 2
            for k := j+1; k < n; k++ {
                p := ps[k]
                r1 := (y[0]-x[0])*(p[1]-y[1])
                r2 := (y[1]-x[1])*(p[0]-y[0])
                if r1 == r2 {
                    cnt++
                }
            }
            res = max(res, cnt)
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

可以再用哈希函数优化，不会做了。。。

# 909. 蛇梯棋

题目很简单，但对于坐标的转化，用了很长时间：

class Solution {
    int n;
    int mod;
    public int snakesAndLadders(int[][] board) {
        n = board.length * board.length;
        mod = board.length;
        Queue<Integer> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>(36);
        q.offer(1);
        visited.add(1);
        int cnt = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            
            for (int i = 0; i < sz; i++) {
                int cur = q.poll();
                if (cur == n) {
                    return cnt;
                }
                if (cur > n) {
                    continue;
                }
                for (int j = 1; j <= 6; j++) {
                    if (cur+j>n) continue;
                    int res = go(board, cur+j);
                    if (res != 0 && !visited.contains(res)) {
                        q.offer(res);
                        visited.add(res);
                    }
                }
            }
            cnt++;
        }
        return -1;
    }
    
    private int go(int[][] board, int i) {
        int x = (mod-1)-((i-1)/mod);
        int y = (i-1)%mod;
        
        if (((i-1)/mod) % 2 != 0) {
            y = (mod-1)-y;
        }
        int res = i;
        int tmp = board[x][y];
        if (tmp != -1) {
            res = tmp;
        }
        return res;
    }
}

# 168. Excel表列名称

class Solution {
    public String convertToTitle(int n) {
        StringBuilder res = new StringBuilder();
        while (n > 0) {
            int cur = ((n-1) % 26)+1;
            res.append((char) (cur - 1 + 'A'));
            n = (n-cur)/26;
        }
        return res.reverse().toString();
    }
}

go解法：

func convertToTitle(n int) string {
    res := ""
    for n > 0 {
        cur := (n-1) % 26 + 1
        res = res + string(cur-1+int('A'))
        n = (n-cur)/26
    }
    return Reverse(res)
}

func Reverse(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

# 剑指 Offer 59 - II. 队列的最大值

class MaxQueue {
    Queue<Integer> q;
    LinkedList<Integer> list;

    public MaxQueue() {
        q = new LinkedList<>();
        list = new LinkedList<>();
        list.add(-1);
    }
    
    public int max_value() {
        if (q.isEmpty()) return -1;
        return list.peekFirst();
    }
    
    public void push_back(int value) {
        while (!list.isEmpty() && value > list.peekLast()) {
            list.pollLast();
        }
        list.addLast(value);
        q.offer(value);
    }
    
    public int pop_front() {
        if (q.isEmpty()) return -1;
        // 调用max_value要先执行，否则下一步q.poll()会改变队列
        int max = max_value();
        int res = q.poll();
        if (res == max) {
            list.pollFirst();
        }
        return res;
    }
}

go解法：

type MaxQueue struct {
    q, l []int
}

func Constructor() MaxQueue {
    max := MaxQueue{make([]int, 0), make([]int, 0)}
    max.l = append(max.l, -1)
    return max
}

func (this *MaxQueue) Max_value() int {
    if len(this.l) == 0 {
        return -1
    }
    return this.l[0]
}

func (this *MaxQueue) Push_back(value int)  {
    for i := len(this.l)-1; i >= 0 && value > this.l[i]; i-- {
        this.l = this.l[:i]
    }
    this.l = append(this.l, value)
    this.q = append(this.q, value)
}

func (this *MaxQueue) Pop_front() int {
    if len(this.q) == 0 {
        return -1
    }
    max := this.Max_value()
    res := this.q[0]
    this.q = this.q[1:]
    if max == res {
        this.l = this.l[1:]
    }
    return res
}

# LCP 07. 传递信息

bfs：

class Solution {
    public int numWays(int n, int[][] relation, int k) {
        List<Integer>[] map = new List[n];
        for (int[] r : relation) {
            List<Integer> list = map[r[0]];
            if (list == null) {
                list = new ArrayList<>();
            }
            list.add(r[1]);
            map[r[0]] = list;
        }
        
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        int cnt = 0;
        int res = 0;
        while (!q.isEmpty() && cnt <= k) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int cur = q.poll();
                if (cnt == k && cur == n-1) {
                    res++;
                }
                
                List<Integer> list = map[cur];
                if (list != null) {
                    for (int t : list) {
                        q.offer(t);
                    }
                }
            }
            
            cnt++;
        }
        return res;
    }
}

# 451. 根据字符出现频率排序

哈希+优先队列：

class Solution {
    public String frequencySort(String s) {
        PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });
        int[] map = new int[128];
        for (char c : s.toCharArray()) {
            map[(int)c]++;
        }
        
        for (int i = 0; i < 128; i++) {
            q.offer(new int[]{i, map[i]});
        }
        
        StringBuilder res = new StringBuilder();
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int i = 0; i < cur[1]; i++) {
                res.append((char)cur[0]);
            }
        }
        return res.toString();
    }
}

# 146. LRU 缓存机制

使用哈希表+双向链表实现：

class LRUCache {
    int size = 0;
    int capacity;
    Map<Integer, Node> map = new HashMap<>();
    Node first;
    Node last;

    private class Node {
        Node pre;
        Node next;
        int val;
        int key;
        Node() {}
        Node(int key, int value) {
            this.key = key;
            this.val = value;
        }
        public String toString() {
            return "key:"+key+"; val:"+val;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        first = new Node(-1, -1);
        last = new Node(-99, -99);
        first.next = last;
        last.pre = first;
    }

    public int get(int key) {
        Node res = map.get(key);
        if (res != null) {
            Node old_pre = res.pre;
            Node old_next = res.next;
            connect(old_pre, old_next);
            
            Node old_first = first.next;
            connect(first, res);
            connect(res, old_first);
            
            // printFirst();
            // printLast();
            return res.val;
        }
        return -1;
    }

    public void put(int key, int value) {
        Node n = map.get(key);
        if (n == null) {
            n = new Node(key, value);
            Node old = first.next;
            connect(first, n);
            connect(n, old);
            if (size >= capacity) {
                Node delete = last.pre;
                Node end = last.pre.pre;
                connect(end, last);
                map.remove(delete.key);
            } else {
                size++;
            }
        } else {
            int rundent = get(key);
            n.val = value;
        }
        // printFirst();
        // printLast();
        map.put(key, n);
    }
    
    public void connect(Node a, Node b) {
        a.next = b;
        b.pre = a;
    }
    
    public void printFirst() {
        Node tmp = first.next;
        while (tmp != null) {
            System.out.print(tmp.val+", ");
            tmp = tmp.next;
        }
        System.out.println("first end");
    }
    
    public void printLast() {
        Node tmp = last.pre;
        while (tmp != null) {
            System.out.print(tmp.val+", ");
            tmp = tmp.pre;
        }
        System.out.println("last end");
    }
}

# 811. 子域名访问计数

哈希表：

class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        String[] cd = cpdomains;
        HashMap<String, Integer> map = new HashMap<>();
        
        for (String s : cd) {
            String[] arr = s.split(" ");
            String[] dm = arr[1].split("\\.");

            String dd = dm[dm.length-1];
            map.put(dd, map.getOrDefault(dd, 0)+Integer.valueOf(arr[0]));
            for (int i = dm.length-2; i >= 0; i--) {
                dd = dm[i] + "." + dd;
                map.put(dd, map.getOrDefault(dd, 0)+Integer.valueOf(arr[0]));
            }
        }
        List<String> res = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            res.add(entry.getValue() + " " + entry.getKey());
        }
        
        return res;
    }
}

# 645. 错误的集合

看数据范围知道复杂度可以控制，建一个大小相同的数组，做哈希计数，再遍历一遍计数等于0或者2的数位位置即可。

class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] cnt = new int[nums.length+1];
        
        for (int n : nums) {
            cnt[n]++;
        }
        
        int[] res = new int[2];
        for (int i = 1; i < cnt.length; i++) {
            if (cnt[i] == 0) {
                res[1] = i;
            } 
            if (cnt[i] == 2) {
                res[0] = i;
            }
        }
        return res;
    }
}

# 142. 环形链表 II

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        
        while (slow != null && slow.next != null
              && fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // System.out.println(slow.val + ";" + fast.val);
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

# 1418. 点菜展示表

模拟题：

class Solution {
    public List<List<String>> displayTable(List<List<String>> orders) {
        // map<table, map<caiming, cnt>>
        Map<Integer, Map<String, Integer>> map = new TreeMap<>();
        Set<String> set = new TreeSet<>();
        for (List<String> list : orders) {
            Map<String, Integer> desk = map.get(Integer.valueOf(list.get(1)));
            if (desk == null) {
                desk = new HashMap<>();
            }
            set.add(list.get(2));
            desk.put(list.get(2), desk.getOrDefault(list.get(2), 0)+1);
            map.put(Integer.valueOf(list.get(1)), desk);
        }
        List<List<String>> res = new ArrayList<>();
        List<String> table = new ArrayList<>();
        table.add("Table");
        for (String s : set) {
            table.add(s);
        }
        res.add(table);

        for (Map.Entry<Integer, Map<String, Integer>> entry : map.entrySet()) {
            List<String> row = new ArrayList<>();
            row.add(String.valueOf(entry.getKey()));
            for (String s : set) {
                row.add(String.valueOf(entry.getValue().getOrDefault(s, 0)));
            }
            res.add(row);
        }

        return res;
    }
}

# 167. 两数之和 II - 输入有序数组

双指针：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        int[] num = numbers;
        int l = 0, r = n-1;

        while (l < r) {
            int sum = num[l]+num[r];
            if (sum == target) return new int[]{l+1, r+1};

            if (sum > target) r--;
            if (sum < target) l++;
        }

        return null;
    }
}

二分法：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] nums = numbers;
        int n = nums.length;
        for (int i = 0; i < n-1; i++) {
            int res = Arrays.binarySearch(nums, i+1, n, target-nums[i]);
            if (res >= 0) return new int[]{i+1, res+1};
        }
        return null;
    }
}

# 84. 柱状图中最大的矩形

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] hs = new int[heights.length+1];
        hs[hs.length-1] = 0;
        for (int i = 0; i < heights.length; i++) {
            hs[i] = heights[i];
        }
        Stack<Integer> stack = new Stack<>();
        int max = 0;
        for (int i = 0; i < hs.length; i++) {
            while (!stack.empty() && hs[stack.peek()] > hs[i]) {
                int top = stack.pop();
                int s = hs[top]*(i-(stack.empty()?0:stack.peek()+1));
                max = Math.max(max, s);
            }
            stack.push(i);
        }
        return max;
    }
}

重刷，还是没做出来，主要原因还是没有分析出如何枚举计算矩形面积，下面用两次单调栈，计算出一个位置的左右最近小于它的位置，然后计算出矩形面积

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!s.empty() && heights[i] <= heights[s.peek()]) {
                s.pop();
            }
            if (s.empty()) {
                s.push(i);
                left[i] = -1;
            } else if (heights[i] > heights[s.peek()]) {
                left[i] = s.peek();
                s.push(i);
            }
        }
        // System.out.println(Arrays.toString(left));

        s = new Stack<>();
        int[] right = new int[n];
        for (int i = n-1; i >= 0; i--) {
            while (!s.empty() && heights[i] <= heights[s.peek()]) {
                s.pop();
            }
            if (s.empty()) {
                s.push(i);
                right[i] = n;
            } else if (heights[i] > heights[s.peek()]) {
                right[i] = s.peek();
                s.push(i);
            }
        }

        // System.out.println(Arrays.toString(right));

        int res = 0;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, (right[i]-left[i]-1)*heights[i]);
        }
        return res;
    }
}

# 42. 接雨水

单调栈

class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        int[] hg = height;
        for (int i = 0; i < hg.length; i++) {
            while (!stack.empty() && hg[i]>hg[stack.peek()]) {
                int top = stack.pop();
                if (!stack.empty()) {
                    int toptop = stack.peek();
                    int h = Math.min(hg[toptop]-hg[top], hg[i]-hg[top]);
                    int w = i-toptop-1;
                    res += h*w;
                }
            }
            stack.push(i);
        }
        return res;
    }
}

重刷，还是写的比较复杂

class Solution {
    public int trap(int[] height) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < height.length; i++) {
            if (stack.empty() || height[i] <= height[stack.peek()]) {
                stack.push(i);
            } else {
                while (!stack.empty() && height[i] > height[stack.peek()]) {
                    int bot = stack.pop();
                    while (!stack.empty() && height[stack.peek()] == height[bot]) {
                        stack.pop();
                    }
                    if (!stack.empty()) {
                        res += (Math.min(height[stack.peek()], height[i])-height[bot])*(i-stack.peek()-1);
                    }
                }
                stack.push(i);
            }
        }
        return res;
    }
}

# 25. K 个一组翻转链表

模拟：

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode sentinel = new ListNode();
        sentinel.next = head;
        ListNode tail = head;

        ListNode pre = sentinel;
        while (tail != null) {
            
            for (int i = 0; i < k; i++) {
                if (tail == null) return sentinel.next;
                tail = tail.next;
            }

            ListNode[] res = reverse(head, k);
            pre.next = res[0];
            res[1].next = tail;

            head = tail;
            pre = res[1];
        }

        return sentinel.next;
    }

    private ListNode[] reverse(ListNode head, int k) {
        ListNode tail = head;
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null && k > 0) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
            k--;
        }

        return new ListNode[]{pre, tail};
    }
}

# 1711. 大餐计数

哈希+模拟：

class Solution {
    public int countPairs(int[] deliciousness) {
        int[] ds = deliciousness;
        int max = -1;
        for (int d : ds) {
            max = Math.max(max, d);
        }
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        int mod = (int)1e9 + 7;
        for (int i = 0; i < ds.length; i++) {
            for (int sum = 1; sum <= max*2; sum<<=1) {
                int cnt = map.getOrDefault(sum-ds[i], 0);
                res = (res+cnt) % mod;
            }
            map.put(ds[i], map.getOrDefault(ds[i], 0)+1);
        }
        return res;
    }
}

# 30. 串联所有单词的子串

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int ws_len = words.length;
        int word_len = words[0].length();
        int all_len = ws_len*word_len; 
        List<Integer> res = new ArrayList<>();
        Map<String, Integer> wmap = new HashMap<>();
        for (String w : words) {
            wmap.put(w, wmap.getOrDefault(w, 0)+1);
        }
        for (int i = 0; i < s.length()-all_len+1; i++) {
            String tmp = s.substring(i, i+all_len);

            Map<String, Integer> tmap = new HashMap<>();
            for (int j = 0; j < tmp.length(); j+=word_len) {
                String tt = tmp.substring(j, j+word_len);
                tmap.put(tt, tmap.getOrDefault(tt, 0)+1);
            }
            if (wmap.equals(tmap)) res.add(i);
        }
        return res;
    }
}

# 面试题 17.10. 主要元素

class Solution {
    public int majorityElement(int[] nums) {
        int candi = 0;
        int cnt = 0;
        for (int n : nums) {
            if (cnt == 0) {
                candi = n;
                cnt++;
            } else {
                if (candi == n) {
                    cnt++;
                } else {
                    cnt--;
                }
            }
        }
        
        if (cnt==0) return -1;
        cnt = 0;
        for (int n : nums) {
            if (candi == n) cnt++;
        }
        return (cnt*2 <= nums.length)?-1:candi;
    }
}

# 207. 课程表

拓扑排序 但是思路比较乱，其实套模板即可：

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int nc = numCourses;
        int[][] pres = prerequisites;

        Set<Integer> set = new HashSet<>();
        Map<Integer, List<Integer>> pres_map = new HashMap<>();
        Map<Integer, Integer> degree = new HashMap<>();
        for (int[] pre : pres) {
            if (pre[0] >= 0 && pre[0] < nc) {
                if (pre[1] >= 0 && pre[1] < nc) {
                    List<Integer> list = pres_map.getOrDefault(pre[0], new ArrayList<>());
                    list.add(pre[1]);
                    pres_map.put(pre[0], list);
                    set.add(pre[1]);
                    set.add(pre[0]);
                    degree.put(pre[0], degree.getOrDefault(pre[0], 0));
                    degree.put(pre[1], degree.getOrDefault(pre[1], 0)+1);
                } else {
                    return false;
                }
            }
        }
        LinkedList<Integer> q = new LinkedList<>();
        for (Map.Entry<Integer, Integer> entry : degree.entrySet()) {
            if (entry.getValue() == 0) {
                q.add(entry.getKey());
            }
        }

        int cnt = 0;
        while (!q.isEmpty()) {
            int k = q.remove();
            cnt++;
            List<Integer> list = pres_map.getOrDefault(k, new ArrayList<>());
            for (int i : list) {
                int count = degree.get(i);
                count--;
                if (count == 0) q.add(i);
                degree.put(i, count);
            }
        }

        return cnt == set.size();
    }
}

# 210. 课程表 II

拓扑排序：

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int nc = numCourses;
        int[][] pres = prerequisites;

        HashSet<Integer>[] relate = new HashSet[nc];
        for (int i = 0; i < nc; i++) {
            relate[i] = new HashSet<>();
        }

        int[] degree = new int[nc];
        for (int[] pre : pres) {
            degree[pre[0]]++;
            relate[pre[1]].add(pre[0]);
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < nc; i++) {
            if (degree[i] == 0) q.offer(i);
        }

        int[] res = new int[nc];
        int cnt = 0;
        while (!q.isEmpty()) {
            int k = q.poll();
            res[cnt++] = k;
            HashSet<Integer> set = relate[k];

            for (int n : set) {
                degree[n]--;
                if (degree[n] == 0) q.offer(n);
            }
        }

        if (cnt == nc) {
            return res;
        }
        return new int[]{};
    }
}

# 874. 模拟行走机器人

模拟题：

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        int x = 0;
        int y = 0;

        // direction 0,1,2,3 上，右，下，左
        int dir = 0;
        int max = 0;

        Set<String> set = new HashSet<>();
        for (int[] ob : obstacles) {
            set.add(ob[0]+","+ob[1]);
        }

        for (int i = 0; i < commands.length; i++) {
            int cmd = commands[i];

            if (cmd == -2) {
                dir += 3;
            } else if (cmd == -1) {
                dir += 1;
            } else {
                for (int j = 1; j <= cmd; j++) {
                    int sx = x + dx[dir%4];
                    int sy = y + dy[dir%4];
                    if (set.contains(sx+","+sy)) {
                        break;
                    } else {
                        x = sx;
                        y = sy;
                        max = Math.max(max, x*x+y*y);
                    }
                }
            }
        }
        return max;
    }
}

# 981. 基于时间的键值存储

数据结构题，利用有序map即可：

class TimeMap {
    Map<String, TreeMap<Integer, String>> map;
    /** Initialize your data structure here. */
    public TimeMap() {
        map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        TreeMap<Integer, String> tree = map.getOrDefault(key, new TreeMap<Integer, String>(
            new Comparator<Integer>() {
                public int compare(Integer t1, Integer t2) {
                    return t1.compareTo(t2);
                }
            }
        ));
        tree.put(timestamp, value);
        map.put(key, tree);
    }
    
    public String get(String key, int timestamp) {
        TreeMap<Integer, String> tree = map.get(key);
        if (tree == null) return "";
        Map.Entry<Integer, String> entry = tree.floorEntry(timestamp);
        if (entry == null) return "";
        return entry.getValue();
    }
}

# 547. 省份数量

并查集：

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }
        return uf.count;
    }


    class UnionFind {
        public int count = 0;
        private int[] parent;

        public UnionFind(int n) {
            count = n;
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int p) {
            while (p != parent[p]) {
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }

        public void union(int p, int q) {
            int rp = find(p);
            int rq = find(q);
            if (rp == rq) return;
            parent[rp] = rq;
            count--;
        }
    }
}

# 5808. 数组串联（第 249 场周赛）

数组直接拼接就行。 取模：

class Solution {
    public int[] getConcatenation(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n*2];
        for (int i = 0; i < n*2; i++) {
            ans[i] = nums[i%n];
        }
        return ans;
    }
}

# 5809. 长度为 3 的不同回文子序列（第 249 场周赛）

找相同的字符作为回文开头和结尾，再找中间不同字符的个数：

class Solution {
    public int countPalindromicSubsequence(String s) {
        Map<Character, List<Integer>> map = new HashMap<>();
        char[] cs = s.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            List<Integer> list = map.getOrDefault(cs[i], new ArrayList<Integer>());
            list.add(i);
            map.put(cs[i], list);
        }
        
        int res = 0;
        for (Map.Entry<Character, List<Integer>> entry : map.entrySet()) {
            List<Integer> list = entry.getValue();
            if (list.size() <= 1) continue;
            
            int start = list.get(0);
            int end = list.get(list.size()-1);
            
            Set<Character> set = new HashSet<>();
            for (int i = start+1; i < end; i++) {
                set.add(cs[i]);
            }
            int len = set.size();
            res += len;
        }
        
        return res;
    }
}

# 5811. 用三种不同颜色为网格涂色（第 249 场周赛）

dp，做不出

# 1411. 给 N x 3 网格图涂色的方案数

class Solution {
    public int numOfWays(int n) {
        long abc = 6, aba = 6, mod = (long)1e9 + 7;
        for (int i = 1; i < n; i++) {
            long t_abc = (2*(abc+aba)) % mod;
            long t_aba = (3*aba+2*abc) % mod;
            abc = t_abc;
            aba = t_aba;
        }
        return (int) ((abc+aba)%mod);
    }
}

# 274. H 指数

排序，再从大到小统计：

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length;
        int h = 0;
        for (int i = n-1; i >= 0; i--) {
            if (citations[i] > h) {
                h++;
            } else {
                return h;
            }
        }
        return h;
    }
}

计数排序：

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] count = new int[n+1];

        for (int c : citations) {
            if (c > n) {
                count[n]++;
            } else {
                count[c]++;
            }
        }

        int h = 0;
        for (int i = n; i >= 0; i--) {
            h += count[i];
            if (h >= i) return i;
        }
        return h;
    }
}

# 684. 冗余连接

并查集：

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n);
        int[] res = new int[2];
        for (int i = 0; i < n; i++) {
            int[] e = edges[i];
            if (uf.connected(e[0]-1, e[1]-1)) {
                res = e;
            }
            uf.union(e[0]-1, e[1]-1);
        }
        return res;
    }
    class UnionFind {
        private int count = 0;
        private int[] parent;

        public UnionFind(int n) {
            count = n;
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int p) {
            while (p != parent[p]) {
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }

        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }

        public void union(int p, int q) {
            int rp = find(p);
            int rq = find(q);
            if (rp == rq) return;
            parent[rp] = rq;
            count--;
        }
    }
}

# 433. 最小基因变化

bfs:

class Solution {
    public int minMutation(String start, String end, String[] bank) {
        char[] seq = new char[]{'A', 'C', 'G', 'T'};
        Set<String> bankset = new HashSet<>();
        for (String s : bank) {
            bankset.add(s);
        }

        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        q.offer(start);
        visited.add(start);

        int cnt = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            
            for (int i = 0; i < sz; i++) {
                String cur = q.poll();
                if (cur.equals(end)) return cnt;

                for (int j = 0; j < cur.length(); j++) {
                    for (char c : seq) {
                        String newStr = cur.substring(0, j) + String.valueOf(c) + cur.substring(j+1, cur.length());
                        if (bankset.contains(newStr) && !visited.contains(newStr)) {
                            q.offer(newStr);
                            visited.add(newStr);
                        }
                    }
                }
            }
            cnt++;
        }
        return -1;
    }
}

# 275. H 指数 II

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        for (int i = 0; i < n; i++) {
            if (citations[i] >= n-i) return n-i;
        }
        return 0;
    }
}

二分法：

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int l = 0, r = n-1;

        while (l < r) {
            int mid = l + ((r-l)>>1);
            if (citations[mid] >= n-mid) {
                r = mid;
            } else {
                l = mid+1;
            }
        }
        if (citations[r] >= n-r) return n-r;
        return 0;
    }
}

# 329. 矩阵中的最长递增路径

class Solution {
    int[][] memo;
    int[][] ma;
    public int longestIncreasingPath(int[][] matrix) {
        ma = matrix;
        int row = matrix.length, col = matrix[0].length;
        memo = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                memo[i][j] = -1;
            }
        }
        int max = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                max = Math.max(max, dfs(row, col, i, j)+1);
            }
        }
        return max;
    }

    private int dfs(int row, int col, int i, int j) {
        if (memo[i][j] != -1) return memo[i][j];

        int r1 = 0, r2 = 0, r3 = 0, r4 = 0;
        if (i+1 < row && ma[i+1][j] > ma[i][j]) 
            r1 = dfs(row, col, i+1, j)+1;
        
        if (i-1 >= 0 && ma[i-1][j] > ma[i][j]) 
            r2 = dfs(row, col, i-1, j)+1;

        if (j+1 < col && ma[i][j+1] > ma[i][j]) 
            r3 = dfs(row, col, i, j+1)+1;

        if (j-1 >= 0 && ma[i][j-1] > ma[i][j]) 
            r4 = dfs(row, col, i, j-1)+1;

        int res = Math.max(r1, Math.max(r2, Math.max(r3, r4)));

        memo[i][j] = res;

        return res;
    }
}

# 218. 天际线问题

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        TreeSet<int[]> set = new TreeSet<>(
            (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]
        );

        for (int[] b : buildings) {
            set.add(new int[]{b[0], -b[2]});
            set.add(new int[]{b[1], b[2]});
        }

        TreeSet<Integer> height = new TreeSet<>();
        Map<Integer, Integer> hmap = new HashMap<>();
        
        height.add(0);
        hmap.put(0, 1);
        
        List<List<Integer>> res = new ArrayList<>();
        int[] last = new int[]{0, 0};
        for (int[] t : set) {
            if (t[1] < 0) {
                hmap.put(-t[1], hmap.getOrDefault(-t[1], 0)+1);
                height.add(new Integer(-t[1]));
            } else {
                int h = hmap.get(t[1]);
                if (h == 1) {
                    height.remove(new Integer(t[1]));
                }
                hmap.put(t[1], h-1);
            }

            int maxH = height.last();
            // System.out.println("maxh:"+maxH+"; t:"+Arrays.toString(t));

            if (last[1] != maxH) {
                last[0] = t[0];
                last[1] = maxH;
                res.add(Arrays.asList(t[0], maxH));
            }
            
        }
        
        return res;
    }
}

# 977. 有序数组的平方

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int l = 0, r = n-1;
        int[] res = new int[n];
        int index = n-1;
        while (l <= r) {
            if (pow2(nums[l]) > pow2(nums[r])) {
                res[index] = pow2(nums[l++]);
            } else {
                res[index] = pow2(nums[r--]);
            }
            index--;
        }
        return res;
    }

    private int pow2(int a) {
        return a*a;
    }
}

# 355. 设计推特

利用哈希表+优先队列：

class Twitter {
    int order = 0;
    Map<Integer, Set<Integer>> likeMap;
    Map<Integer, List<int[]>> tweetMap;

    /** Initialize your data structure here. */
    public Twitter() {
        likeMap = new HashMap<>();
        tweetMap = new HashMap<>();
    }
    
    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        List<int[]> list = tweetMap.getOrDefault(userId, new ArrayList<int[]>());
        list.add(new int[]{tweetId, userId, order, -1});
        order++;
        tweetMap.put(userId, list);
    }
    
    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> set = likeMap.getOrDefault(userId, new HashSet<Integer>());
        Set<Integer> users = new HashSet<>(set);
        users.add(userId);
        List<Integer> res = new ArrayList<>();
        // System.out.println(userId + ": users: "+ users);
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o2[2] - o1[2]);

        for (int u : users) {
            List<int[]> list = tweetMap.get(u);
            if (list != null && list.size() > 0) {
                int index = list.size()-1;
                int[] tmp = list.get(index);
                tmp[3] = index;
                q.offer(tmp);
            }
        }

        for (int i = 0; i < 10; i++) {
            if (!q.isEmpty()) {
                int[] t1 = q.poll();
                int index = t1[3]-1;
                res.add(t1[0]);
                List<int[]> list = tweetMap.get(t1[1]);
                if (list != null && list.size() > 0 && index >= 0) {
                    int[] t2 = list.get(index);
                    t2[3] = index;
                    q.offer(t2);
                }
            }
        }
        // Collections.reverse(res);
        return res;
    }
    
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        Set<Integer> set = likeMap.getOrDefault(followerId, new HashSet<Integer>());
        set.add(followeeId);
        likeMap.put(followerId, set);
    }
    
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        Set<Integer> set = likeMap.getOrDefault(followerId, new HashSet<Integer>());
        set.remove(followeeId);
        likeMap.put(followerId, set);

    }
}

# 295. 数据流的中位数

大顶堆+小顶堆：

class MedianFinder {
    PriorityQueue<Integer> right = new PriorityQueue<>((o1, o2) -> o1 - o2);
    PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> o2 - o1);

    public MedianFinder() {

    }
    
    public void addNum(int num) {
        int len = left.size();
        int rlen = right.size();

        if (len == rlen) {
            if (len == 0) {
                left.offer(num);
            } else {
                int rmin = right.peek();
                if (num > rmin) {
                    right.poll();
                    left.offer(rmin);
                    right.offer(num);
                } else {
                    left.offer(num);
                }
            }
        } else {
            // len != rlen
            int mid = left.peek();
            if (num >= mid) {
                right.offer(num);
            } else {
                left.poll();
                right.offer(mid);
                left.offer(num);
            }
        }
    }
    
    public double findMedian() {
        // System.out.println("left:"+left);
        // System.out.println("right:"+right);
        int len = left.size();
        int rlen = right.size();

        if (len == rlen) {
            return (double) (left.peek() + right.peek()) / 2;
        }

        return left.peek();
    }
}

# 1818. 绝对差值和

class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        TreeSet<Integer> tree = new TreeSet<>();
        for (int n : nums1) {
            tree.add(n);
        }

        int INF = 0x3f3f3f3f;
        int mod = (int)1e9+7;
        int subMax = 0;
        long sum = 0;

        for (int i = 0; i < nums1.length; i++) {
            int origin = Math.abs(nums1[i]-nums2[i]);
            Integer floor = tree.floor(nums2[i]);
            Integer ceiling = tree.ceiling(nums2[i]);
            int min = Math.min(floor==null?INF:Math.abs(floor-nums2[i]), ceiling==null?INF:Math.abs(ceiling-nums2[i]));
            if (min < origin) {
                subMax = Math.max(subMax, origin-min);
            }

            sum = sum + origin;
        }
        return (int)((sum - subMax) % mod);
    }
}

# 450. 删除二叉搜索树中的节点

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        return recursive(root, key);
    }

    private TreeNode recursive(TreeNode node, int key) {
        if (node == null) return null;
        
        if (key == node.val) {
            // delete
            if (node.left == null && node.right == null) {
                return null;
            } else if (node.left == null || node.right == null) {
                if (node.left != null) return node.left;
                return node.right;
            } else if (node.left != null && node.right != null) {
                TreeNode right = searchMin(node.right);
                if (right != node.right) {
                    right.right = node.right;
                }
                right.left = node.left;
                return right;
            }
        } else if (key < node.val) {
            node.left = recursive(node.left, key);
        } else if (key > node.val) {
            node.right = recursive(node.right, key);
        }
        return node;
    }

    private TreeNode searchMin(TreeNode node) {
        if (node.left == null) {
            return node;
        }

        TreeNode min = searchMin(node.left);
        if (node.left == min) node.left = min.right;
        return min;
    }
}

# 701. 二叉搜索树中的插入操作

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);

        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } else if (val > root.val) {
            root.right = insertIntoBST(root.right, val);
        }

        return root;
    }
}

# 面试题 04.06. 后继者

class Solution {
    boolean isNext = false;
    TreeNode res = null;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        recursive(root, p);   
        return res;
    }

    private void recursive(TreeNode n, TreeNode p) {
        if (n == null || res != null) return;

        recursive(n.left, p);

        if (res == null && isNext) res = n;
        if (n == p) isNext = true;

        recursive(n.right, p);
    }
}

# 410. 分割数组的最大值

二分法：

class Solution {
    public int splitArray(int[] nums, int m) {
        long l = 0, r = 0;
        for (int n : nums) {
            r += n;
            l = Math.max(l, n);
        }

        while (l < r) {
            long mid = l + ((r-l)>>1);

            int sum = 0;
            int cnt = 1;
            for (int n : nums) {
                sum += n;

                if (sum > mid) {
                    sum = n;
                    cnt++;
                }
            }

            if (cnt > m) {
                l = mid+1;
            } else {
                r = mid;
            }

        }
        return (int)r;
    }
}

# 876. 链表的中间结点

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        if (fast.next == null) {
            return slow;
        } 
        return slow.next;
    }
}

# 剑指 Offer 53 - I. 在排序数组中查找数字 I

二分法：

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return 0;
        int l = 0, r = n-1;

        while (l < r) {
            int mid = l + ((r-l)>>1);
            if (target <= nums[mid]) {
                r = mid;
            } else {
                l = mid+1;
            }
        }
        
        if (nums[r] != target) return 0;
        
        int index_l = r;
        l = r;
        r = n-1;
        
        while (l < r) {
            int mid = l + ((r-l+1)>>1);
            if (target >= nums[mid]) {
                l = mid;
            } else {
                r = mid-1;
            }
        }

        int index_r = l;
        
        // System.out.println(index_l +"--"+ index_r);
        return index_r - index_l + 1;
    }
}

重写，两次二分法，更之前写法没区别：

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length, l = 0, r = n-1;
        if (n == 0) return 0;

        while (l < r) {
            int mid = l + ((r-l) >> 1);
            if (target > nums[mid]) {
                l = mid + 1;
            } else if (target <= nums[mid]) {
                r = mid;
            }
        }
        if (nums[l] != target) return 0;
        
        int left = l;
        l = 0;
        r = n-1;
        while (l < r) {
            int mid = l + ((r - l + 1) >> 1);
            if (target >= nums[mid]) {
                l = mid;
            } else if (target < nums[mid]) {
                r = mid - 1;
            }
        }

        return r - left + 1;
    }
}

# 911. 在线选举

class TopVotedCandidate {
    TreeMap<Integer, Integer> tree = new TreeMap<>();

    public TopVotedCandidate(int[] persons, int[] times) {
        int n = persons.length;
        Map<Integer, Integer> cntMap = new HashMap<>();
        int maxCnt = 0;
        int maxP = -1;
        for (int i = 0; i < n; i++) {
            int p = persons[i];
            int c = cntMap.getOrDefault(p, 0)+1;
            cntMap.put(p, c);

            if (c >= maxCnt) {
                maxP = p;
                maxCnt = c;
            }

            tree.put(times[i], maxP);
        }
    }
    
    public int q(int t) {
        return tree.floorEntry(t).getValue();
    }
}

不用map计数，直接使用数组

class TopVotedCandidate {
    TreeMap<Integer, Integer> tree;
    public TopVotedCandidate(int[] persons, int[] times) {
        tree = new TreeMap<>();
        int n = persons.length;
        int[] cnt = new int[n];
        int maxCnt = 0, maxIndex = 0;
        for (int i = 0; i < n; i++) {
            cnt[persons[i]]++;
            if (cnt[persons[i]] >= maxCnt) {
                maxIndex = persons[i];
                maxCnt = cnt[persons[i]];
            }
            tree.put(times[i], maxIndex);
        }
    }
    
    public int q(int t) {
        return tree.floorEntry(t).getValue();
    }
}

# 875. 爱吃香蕉的珂珂

二分法：

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int l = 0, r = 0;
        for (int p : piles) {
            r = Math.max(r, p);
        }

        while (l < r) {
            int mid = l + ((r-l)>>1);
            // System.out.println("l:"+l +"r:"+r+"mid:"+mid);
            int hh = 0;
            for (int p : piles) {
                double div = ((double)p)/mid;
                if (div >= 1d) {
                    hh += (int) Math.ceil(div);
                } else {
                    hh++;
                }
                // System.out.println("div:"+Math.ceil(div)+"; hh:"+hh);
            }
            // System.out.println("hh:"+hh);
            if (hh <= h) {
                r = mid;
            } else {
                l = mid+1;
            }
        }

        return r;
    }
}

# 912. 排序数组

class Solution {
    public int[] sortArray(int[] nums) {
        Arrays.sort(nums);
        return nums;
    }
}

# 1122. 数组的相对排序

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> map = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        List<Integer> unuse = new ArrayList<>();
        for (int n : arr2) {
            set.add(n);
        }

        for (int n : arr1) {
            map.put(n, map.getOrDefault(n, 0)+1);
            if (!set.contains(n)) {
                unuse.add(n);
            }
        }
        
        int i = 0;
        for (int n : arr2) {
            int cnt = map.get(n);
            while (cnt > 0) {
                arr1[i++] = n;
                cnt--;
            }
        }

        Collections.sort(unuse);
        for (int n : unuse) {
            arr1[i++] = n;
        }

        return arr1;
        
    }
}

# 860. 柠檬水找零

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;

        for (int b : bills) {
            if (b == 10) ten++;
            if (b == 5) five++;
            int rem = b-5;
            if (rem > 0) {
                if (rem == 5) {
                    if (five > 0) {
                        five--;
                    } else {
                        return false;
                    }
                } else if (rem == 15) {
                    if (five >= 3 || (ten >= 1 && five >= 1)) {
                        if (ten >= 1 && five >= 1) {
                            ten--;
                            five--;
                        } else if (five >= 3) {
                            five-=3;
                        } else {
                            return false;
                        }
                    } else {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

# 45. 跳跃游戏 II

暴力解：

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            int m = 1;
            while (m <= nums[i] && i+m < n) {
                dp[i+m] = Math.min(dp[i+m], dp[i]+1);
                m++;
            }
        }
        return dp[n-1];
    }
}

动态规划，代码逻辑很乱，记录一下，以此为戒：

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n-1;) {
            int m = i+nums[i];
            if (m >= n-1) return res+1;
            int next = i+1;
            int max = 0;
            int j = i+1;
            while (j <= m) {
                if (j+nums[j] >= max) {
                    max = j+nums[j];
                    next = j;
                }
                j++;
            }
            i = next;
            res++;
        }
        return res;
    }
}

最优解，代码清晰，类似于滑动窗口的贪心算法：

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int end = 0;
        int step = 0;
        int max = 0;
        for (int i = 0; i <= end; i++) {
            if (end >= n-1) return step;
            max = Math.max(max, i+nums[i]);
            if (i == end) {
                step++;
                end = max;
            }
        }
        return -1;
    }
}

重刷时，也能写出比较简洁的代码了

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int i = 1, end = nums[0], cnt = 1;
        if (n == 1) return 0;
        if (end >= n-1) return cnt;
        while (i <= end) {
            int max = 0;
            while (i <= end) {
                max = Math.max(max, i+nums[i]);
                i++;
            }
            end = Math.max(end, max);
            cnt++;
            if (end >= n-1) return cnt;
        }
        return cnt;
    }
}

# 455. 分发饼干

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int cnt = 0;
        int gi = 0;
        int si = 0;
        while (si < s.length && gi < g.length) {
            if (s[si] >= g[gi]) {
                si++;
                gi++;
                cnt++;
            } else {
                si++;
            }
        }
        return cnt;
    }
}

# 1877. 数组中最大数对和的最小值

class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        for (int l = 0, r = nums.length-1; l < nums.length; l++, r--) {
            res = Math.max(res, nums[l]+nums[r]);
        }
        return res;
    }
}

# 1743. 从相邻元素对还原数组

class Solution {
    int INF = 0x3f3f3f3f;
    public int[] restoreArray(int[][] adjacentPairs) {
        int[][] adj = adjacentPairs;
        Map<Integer, int[]> map = new HashMap<>();

        for (int[] t : adj) {
            int[] t0 = map.getOrDefault(t[0], new int[]{INF, INF});
            int[] t1 = map.getOrDefault(t[1], new int[]{INF, INF});
            if (t0[0] == INF) {
                t0[0] = t[1];
            } else {
                t0[1] = t[1];
            }

            if (t1[0] == INF) {
                t1[0] = t[0];
            } else {
                t1[1] = t[0];
            }
            map.put(t[0], t0);
            map.put(t[1], t1);
        }

        int start = 0;
        for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
            if (entry.getValue()[1] == INF) start = entry.getKey();
        }

        int n = adj.length+1;
        int[] res = new int[n];
        int index = 2;
        res[0] = start;
        res[1] = map.get(start)[0];
        start = res[1];
        for (; index < n; index++) {
            int[] cur = map.get(start);
            start = cur[0] == res[index-2] ? cur[1] : cur[0];
            res[index] = start;
        }

        return res;
    }
}

# 1736. 替换隐藏数字得到的最晚时间

class Solution {
    public String maximumTime(String time) {
        char[] cs = time.toCharArray();
        // 0,1
        if (cs[0] == '?') {
            if (cs[1] == '?') {
                cs[0] = '2';
                cs[1] = '3';
            } else if (cs[1] > '3') {
                cs[0] = '1';
            } else {
                cs[0] = '2';
            }
        } else if (cs[1] == '?') {
            if (cs[0] == '2') {
                cs[1] = '3';
            } else {
                cs[1] = '9';
            }
        }

        // 2,3
        if (cs[3] == '?') {
            cs[3] = '5';
        } 
        if (cs[4] == '?') {
            cs[4] = '9';
        }
        
        return new String(cs);
    }
}

# 面试题 10.02. 变位词组

计数构造哈希key：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        int n = 26;
        for (String s : strs) {
            String ss = "";
            int[] cnt = new int[n];
            for (char c : s.toCharArray()) {
                cnt[c-'a']++;
            }
            for (int i = 0; i < n; i++) {
                if (cnt[i] > 0) {
                    ss = ss + String.valueOf(cnt[i]) + String.valueOf((char)(i+'a'));
                }
            }
            List<String> list = map.getOrDefault(ss, new ArrayList<>());
            list.add(s);
            map.put(ss, list);
        }
        List<List<String>> res = new ArrayList<>();
        for (List<String> list : map.values()) {
            res.add(list);
        }
        return res;
    }
}

排序：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] cs = s.toCharArray();
            Arrays.sort(cs);
            String key = String.valueOf(cs);
            List<String> list = map.getOrDefault(key,new ArrayList<>());
            list.add(s);
            map.put(key, list);
        }

        List<List<String>> res = new ArrayList<>();
        for (List<String> list : map.values()) {
            res.add(list);
        }
        return res;
    }
}

最优解法，利用质数分解的唯一性：

class Solution {
    static int[] nums = new int[26];
    static {
        for (int i = 2, idx = 0; idx != 26; i++) {
            boolean ok = true;
            for (int j = 2; j <= i / j; j++) {
                if (i % j == 0) {
                    ok = false;
                    break;
                } 
            }
            if (ok) nums[idx++] = i;
        }
    }
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<Long, List<String>> map = new HashMap<>();
        for (String s : strs) {
            Long cur = 1L;
            for (char c : s.toCharArray()) {
                cur *= nums[c-'a'];
            }
            List<String> list = map.getOrDefault(cur, new ArrayList<>());
            list.add(s);
            map.put(cur, list);
        }
        List<List<String>> res = new ArrayList<>();
        for (List<String> list : map.values()) {
            res.add(list);
        }
        return res;
    }
}

# 1713. 得到子序列的最少操作次数

二叉树的二分+哈希表，超时：

class Solution {
    public int minOperations(int[] target, int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < target.length; i++) {
            map.put(target[i], i);
        }

        // int[0]下标 int[1]右边计数+1
        TreeSet<int[]> tree = new TreeSet<>((t1, t2) -> t1[0]-t2[0]);
        Map<Integer, int[]> cnt = new HashMap<>();
        int max = 0;
        for (int i = arr.length-1; i >= 0; i--) {
            Integer index = map.get(arr[i]);
            if (index == null) continue;

            int[] cur;
            boolean create = true;
            if (cnt.containsKey(index)) {
                create = false;
                cur = cnt.get(index);
            } else {
                cur = new int[]{index, 1};
            }
            Set<int[]> tailSet = tree.tailSet(cur, false);
            if (tailSet != null) {
                int m = 0;
                for (int[] s : tailSet) {
                    m = Math.max(m, s[1]);
                }
                cur[1] = m + 1;
            }

            if (create) tree.add(cur);
            cnt.put(index, cur);
            max = Math.max(max, cur[1]);
        }
        return target.length - max;
    }
}

先转换为最长递增子序列，再用贪心+二分：

class Solution {
    public int minOperations(int[] target, int[] arr) {
        Map<Integer, Integer> tmap = new HashMap<>();
        for (int i = 0; i < target.length; i++) {
            tmap.put(target[i], i);
        }
        int n = arr.length;
        int[] iarr = new int[n];
        for (int i = 0; i < n; i++) {
            iarr[i] = tmap.getOrDefault(arr[i], -1);
        }

        int[] dp = new int[n];
        int len = 0;
        dp[len] = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (iarr[i] == -1) continue;
            if (iarr[i] > dp[len]) {
                len++;
                dp[len] = iarr[i];
            } else if (iarr[i] < dp[len]) {
                int index = search(dp, len, iarr[i]);
                dp[index] = iarr[i];
            }
        }
        return target.length-len;
    }

    private int search(int[] nums, int right, int target) {
        int left = 0;
        while (left < right) {
            int mid = left + ((right-left)>>1);
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid+1;
            }
        }
        return right;
    }

}

# 671. 二叉树中第二小的节点

dfs:

class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        int min = recursive(root, root.val);
        return min == root.val ? -1 : min;
    }
    
    private int recursive(TreeNode node, int rootVal) {
        if (node == null) return rootVal;
        if (node.val != rootVal) {
            return node.val;
        }

        int left = recursive(node.left, rootVal);
        int right = recursive(node.right, rootVal);
        
        if (left == rootVal || right == rootVal) {
            return Math.max(left, right);
        }
        return Math.min(left, right);
    }
}

# 863. 二叉树中所有距离为 K 的结点

建图+BFS：

class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        Graph graph = new Graph();
        recursive(root, root.left, graph);
        recursive(root, root.right, graph);
        
        List<Integer> res = new ArrayList<>();

        Queue<Integer> q = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        q.offer(target.val);
        set.add(target.val);

        while (!q.isEmpty() && k >= 0) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int cur = q.poll();

                if (k == 0) {
                    res.add(cur);
                }

                List<Integer> list = graph.adj.get(cur);
                if (list == null) continue;
                for (int t : list) {
                    if (!set.contains(t)) {
                        set.add(t);
                        q.offer(t);
                    }
                }
            }
            k--;
        }

        return res;
    }

    private void recursive(TreeNode parent, TreeNode node, Graph graph) {
        if (node == null) return;

        graph.addEdge(parent.val, node.val);
        
        recursive(node, node.left, graph);
        recursive(node, node.right, graph);
    }

    class Graph {
        public Map<Integer, List<Integer>> adj;

        public Graph() {
            adj = new HashMap<>();
        }

        public void addEdge(int from, int to) {
            List<Integer> f = adj.get(from);
            if (f == null) f = new ArrayList<>();
            f.add(to);
            adj.put(from, f);

            List<Integer> t = adj.get(to);
            if (t == null) t = new ArrayList<>();
            t.add(from);
            adj.put(to, t);
        }
    }

}

# 1104. 二叉树寻路

满二叉树节点的计算：

class Solution {
    public List<Integer> pathInZigZagTree(int label) {
        List<Integer> res = new ArrayList<>();
        if (label == 1) {
            res.add(1);
            return res;
        }
        int rownum = 0;
        int index = 1;
        int p = 0;
        while (index < label) {
            p++;
            index = (int)Math.pow(2, p) - 1;
        }

        int[] ans = new int[p];
        int target = label;
        if (p % 2 == 0) {
            int lineEnd = (int)Math.pow(2, p)-1;
            target = lineEnd-target+(int)Math.pow(2, p-1);
        }

        ans[p-1] = target;
        for (int i = p-2; i >= 0; i--) {
            ans[i] = ans[i+1] / 2;
        }

        // System.out.println(Arrays.toString(ans));

        for (int i = 0; i < ans.length; i++) {
            if (i % 2 != 0) {
                int lineNum = i+1;
                int lineStart = (int)Math.pow(2, lineNum-1);
                int lineEnd = (int)Math.pow(2, lineNum)-1;
                ans[i] = lineEnd-(ans[i]-lineStart);
            }
        }
        
        for (int n : ans) {
            res.add(n);
        }
        return res;
    }
}

# 987. 二叉树的垂序遍历

class Solution {
    Map<Integer, PriorityQueue<int[]>> map = new HashMap<>();
    TreeSet<Integer> treeSet = new TreeSet<>();
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        recursive(0, 0, root);
        List<List<Integer>> res = new ArrayList<>();
        for (int t : treeSet) {
            List<Integer> list = new ArrayList<>();
            PriorityQueue<int[]> pq = map.get(t);
            while (!pq.isEmpty()) {
                list.add(pq.poll()[1]);
            }
            res.add(list);
        }
        return res;
    }

    private void recursive(int row, int col, TreeNode node) {
        if (node == null) return;
        recursive(row+1, col-1, node.left);

        PriorityQueue<int[]> pq = map.getOrDefault(col, new PriorityQueue<int[]>((a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            }
            return a[0] - b[0];
        }));
        pq.offer(new int[]{row, node.val});
        map.put(col, pq);
        treeSet.add(col);

        recursive(row+1, col+1, node.right);
    }
}

# 557. 反转字符串中的单词 III

class Solution {
    public String reverseWords(String s) {
        int start = 0;
        char[] cs = s.toCharArray();
        for (int i = 0; i <= s.length(); i++) {
            if (i == s.length() || cs[i] == ' ') {
                reverse(cs, start, i-1);
                start = i+1;
            }
        }
        return String.valueOf(cs);
    }
    
    private void reverse(char[] cs, int left, int right) {
        while (left < right) {
            char tmp = cs[left];
            cs[left] = cs[right];
            cs[right] = tmp;
            left++;
            right--;
        }
    }
}

# 733. 图像渲染

dfs：

class Solution {
    int[] dirx = new int[]{0, 1, 0, -1};
    int[] diry = new int[]{1, 0, -1, 0};
    int row;
    int col;
    Set<String> set = new HashSet<>();
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        row = image.length;
        col = image[0].length;
        int original = image[sr][sc];
        dfs(image, sr, sc, original, newColor);
        return image;
    }

    private void dfs(int[][] image, int r, int c, int original, int newColor) {
        if (set.contains(r+","+c)) return;
        if (r < 0 || r >= row || c < 0 || c >= col) {
            return;
        }

        if (image[r][c] == original) {
            image[r][c] = newColor; 
            set.add(r+","+c);

            for (int i = 0; i < 4; i++) {
                dfs(image, r+diry[i], c+dirx[i], original, newColor);
            }

        }
    }  

}

使用字符串去重效率低，优化掉：

class Solution {
    int[] dirx = new int[]{0, 1, 0, -1};
    int[] diry = new int[]{1, 0, -1, 0};
    int row;
    int col;
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        row = image.length;
        col = image[0].length;
        int original = image[sr][sc];
        dfs(image, sr, sc, original, newColor);
        return image;
    }

    private void dfs(int[][] image, int r, int c, int original, int newColor) {
        if (r < 0 || r >= row || c < 0 || c >= col || image[r][c] != original || original == newColor) {
            return;
        }
        image[r][c] = newColor;
        for (int i = 0; i < 4; i++) {
            dfs(image, r+diry[i], c+dirx[i], original, newColor);
        }
    }

}

# 695. 岛屿的最大面积

dfs：

class Solution {
    int[] dirx = new int[]{0, 1, 0, -1};
    int[] diry = new int[]{1, 0, -1, 0};
    int max = 0;
    int row;
    int col;
    boolean[][] visited;
    public int maxAreaOfIsland(int[][] grid) {
        row = grid.length;
        col = grid[0].length;
        visited = new boolean[row][col];

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int res = dfs(grid, i, j);
                max = Math.max(max, res);
            }
        }
        return max;
    }

    private int dfs(int[][] grid, int r, int c) {
        if (r < 0 || r >= row || c < 0 || c >= col || visited[r][c] || grid[r][c] == 0) return 0;

        visited[r][c] = true;
        int res = 1;
        for (int i = 0; i < 4; i++) {
            res += dfs(grid, r+diry[i], c+dirx[i]);
        }
        return res;
    }
}

# 617. 合并二叉树

dfs+模拟：

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        return recursive(root1, root2);
    }

    private TreeNode recursive(TreeNode a, TreeNode b) {
        if (a == null && b == null) return null;
        int aval = 0, bval = 0;
        if (a != null) aval = a.val;
        if (b != null) bval = b.val;
        TreeNode n = new TreeNode(aval+bval);

        n.left = recursive(a==null?a:a.left, b==null?b:b.left);
        n.right = recursive(a==null?a:a.right, b==null?b:b.right);

        return n;
    }
}

优化：

class Solution {
    public TreeNode mergeTrees(TreeNode r1, TreeNode r2) {
        if (r1 == null) return r2;
        if (r2 == null) return r1;
        TreeNode n = new TreeNode(r1.val + r2.val);
        n.left = mergeTrees(r1.left, r2.left);
        n.right = mergeTrees(r1.right, r2.right);
        return n;
    }
}

# 542. 01 矩阵

bfs：

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int[] dr = new int[]{1, 0, -1, 0};
        int[] dc = new int[]{0, 1, 0, -1};
        int row = mat.length;
        int col = mat[0].length;
        Queue<int[]> q = new LinkedList<>();
        
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (mat[i][j] == 0) {
                    q.offer(new int[]{i, j});
                } else {
                    mat[i][j] = -1;
                }
            }

        }

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0];
            int c = cur[1];
            for (int i = 0; i < 4; i++) {
                int newr = r+dr[i];
                int newc = c+dc[i];
                if (newr >= 0 && newr < row 
                    && newc >= 0 && newc < col 
                    && mat[newr][newc] == -1) {
                    mat[newr][newc] = mat[r][c] + 1;
                    q.offer(new int[]{newr, newc});
                }
            }
        }

        return mat;
    }
}

# 994. 腐烂的橘子

bfs：

class Solution {
    public int orangesRotting(int[][] grid) {
        int[] dr = new int[]{1, 0, -1, 0};
        int[] dc = new int[]{0, 1, 0, -1};
        int row = grid.length;
        int col = grid[0].length;

        Queue<int[]> q = new LinkedList<>();
        int fresh = 0;
        for (int i = 0; i < row; i++) {
             for (int j = 0; j < col; j++) {
                if (grid[i][j] == 2) {
                    q.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }

        int minute = 0;
        while (!q.isEmpty() && fresh != 0) {
            int sz = q.size();
            for (int k = 0; k < sz; k++) {
                int[] cur = q.poll();
                int r = cur[0];
                int c = cur[1];
                for (int i = 0; i < 4; i++) {
                    int newr = r + dr[i];
                    int newc = c + dc[i];
                    if (newr >= 0 && newr < row && newc >= 0 && newc < col
                            && grid[newr][newc] == 1) {

                        grid[newr][newc] = 2;
                        q.offer(new int[]{newr, newc});
                        fresh--;
                    }

                }
            }
            minute++;
        }
        return fresh == 0 ? minute : -1;
    }
}

# 784. 字母大小写全排列

递归：

class Solution {
    List<String> res;
    public List<String> letterCasePermutation(String s) {
        res = new ArrayList<>();
        char[] original = s.toCharArray();
        List<Integer> letters = new ArrayList<>();
        for (int i = 0; i < original.length; i++) {
            if (original[i] >= 65 && original[i] <= 122) {
                letters.add(i);
            }
        }
        recursive(original, letters, 0);
        return res;
    }

    private void recursive(char[] original, List<Integer> letters, int index) {
        if (index >= letters.size()) {
            res.add(String.valueOf(original));
            return;
        }

        int li = letters.get(index);
        char letter = original[li];
        
        recursive(original, letters, index+1);

        char newLetter = reverse(letter);
        original[li] = newLetter;
        recursive(original, letters, index+1);
        original[li] = letter;
    }

    private char reverse(char letter) {
        if (letter >= 65 && letter <= 90) {
            return (char) (letter + 32);
        } else {
            return (char) (letter - 32);
        }
    }

}

# 120. 三角形最小路径和

递归：

class Solution {
    Map<String, Integer> cache = new HashMap<>();
    public int minimumTotal(List<List<Integer>> triangle) {
        return recursive(triangle, 0, 0);
    }

    private int recursive(List<List<Integer>> triangle, int row, int col) {
        if (row >= triangle.size() || col >= triangle.get(row).size()) return 0;
        Integer cval = cache.get(row+";"+col);
        if (cval != null) return cval;
        List<Integer> rows = triangle.get(row);
        int sum = rows.get(col);

        int a = recursive(triangle, row+1, col);
        int b = recursive(triangle, row+1, col+1);

        sum += Math.min(a, b);
        cache.put(row+";"+col, sum);
        return sum;
    }
}

动态规划：

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        // 多出的一行加在最下面
        int[][] dp = new int[n+1][n+1];
        for (int r = n-1; r >= 0; r--) {
            for (int c = r; c >= 0; c--) {
                dp[r][c] = triangle.get(r).get(c) 
                    + Math.min(dp[r+1][c], dp[r+1][c+1]);
            }
        }
        return dp[0][0];
    }
}

# 815. 公交路线

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        Map<Integer, List<Integer>> station = new HashMap<>();
        for (int i = 0; i < routes.length; i++) {
            int[] stats = routes[i];
            for (int j = 0; j < stats.length; j++) {
                List<Integer> cars = station.getOrDefault(stats[j], new ArrayList<>());
                cars.add(i);
                station.put(stats[j], cars);
            }
        }

        // 车站队列
        Queue<Integer> q = new LinkedList<>();
        Set<Integer> visStat = new HashSet<>();        
        Set<Integer> visCar = new HashSet<>();        
        q.offer(source);
        visStat.add(source);
        int res = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int cur = q.poll();
                if (cur == target) return res;
                // 车站队列出列，通过station找到能上的公交车
                List<Integer> cars = station.get(cur);
                // 查出 这些公交车 能一站到哪些车站去
                for (int car : cars) {
                    if (visCar.contains(car)) continue;
                    visCar.add(car);
                    int[] stats = routes[car];
                    for (int stat : stats) {
                        if (visStat.contains(stat)) continue;
                        visStat.add(stat);
                        q.offer(stat);
                    }
                }
            }
            res++;
        }

        return -1;
    }
}

# LCS 03. 主题空间（微软专场竞赛）

class Solution {
    int[] dr = new int[]{1, 0, -1, 0};
    int[] dc = new int[]{0, 1, 0, -1};
    int row;
    int col;
    int max = 0;
    Set<String> set = new HashSet<>();
    public int largestArea(String[] grid) {
        row = grid.length;
        col = grid[0].length();
        char[][] gg = new char[row][col];
        for (int i = 0; i < row; i++) {
            String g = grid[i];
            gg[i] = g.toCharArray();
        }

        // clean bounds
        // clean 0 end-1 row
        for (int i = 0; i < col; i++) {
            dfs0(gg, 0, i, gg[0][i], '0');
            dfs0(gg, row-1, i, gg[row-1][i], '0');
        }
        // clean 0 end-1 col
        for (int i = 0; i < row; i++) {
            dfs0(gg, i, 0, gg[i][0], '0');
            dfs0(gg, i, col-1, gg[i][col-1], '0');
        }

        for (int i = 1; i < row-1; i++) {
            for (int j = 1; j < col-1; j++) {
                if (gg[i][j] == '0') {
                    dfs0(gg, i, j, gg[i][j], '0');
                }
            }
        }

        // System.out.println(Arrays.deepToString(gg));

        for (int i = 1; i < row-1; i++) {
            for (int j = 1; j < col-1; j++) {
                max = Math.max(max, dfs(gg, i, j, gg[i][j], gg[i][j]));
            }
        }
        return max;
    }

    private void dfs0(char[][] gg, int r, int c, char original, char target) {
        if (r < 0 || r >= row || c < 0 || c >= col) return;
        if (gg[r][c] == 'A' || gg[r][c] == 'B') return;
        
        if (gg[r][c] != '0') {
            dfs(gg, r, c, gg[r][c], target);
            return;
        }

        gg[r][c] = 'A';
        for (int i = 0; i < 4; i++) {
            dfs0(gg, r+dr[i], c+dc[i], original, target);
        }
    }

    private int dfs(char[][] gg, int r, int c, char original, char target) {
        if (r < 0 || r >= row || c < 0 || c >= col) return 0;
        if (gg[r][c] == '0' || gg[r][c] == 'A' || gg[r][c] == 'B' || gg[r][c] != original) {
            return 0;
        }
        gg[r][c] = 'B';
        int res = 1;
        for (int i = 0; i < 4; i++) {
            res += dfs(gg, r+dr[i], c+dc[i], original, target);
        }
        return res;
    }
}

# 1905. 统计子岛屿（第 246 场周赛）

class Solution {
    int[] dr = new int[]{1, 0, -1, 0};
    int[] dc = new int[]{0, 1, 0, -1};
    int row;
    int col;
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int[][] g1 = grid1;
        int[][] g2 = grid2;
        row = g1.length;
        col = g1[0].length;
        List<int[]> neg = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (g1[i][j] == 0 && g2[i][j] == 1) {
                    g2[i][j] = -1;
                    neg.add(new int[]{i, j});
                } else {
                    g2[i][j] = g2[i][j] + g1[i][j];
                }
            }
        }
        
        for (int[] t : neg) {
            dfs_1(g2, t[0], t[1]);
        }
        
        // System.out.println(Arrays.deepToString(g2));
        
        int cnt = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (dfs(g2, i, j) > 0) cnt++;
            }
        }
        
        // System.out.println(Arrays.deepToString(g2));
        
        return cnt;
    }

    private int dfs_1(int[][] g, int r, int c) {
        if (g[r][c] != 2 && g[r][c] != -1) return 0;
        g[r][c] = 4;
        int res = 1;
        for (int i = 0; i < 4; i++) {
            int nr = r+dr[i];
            int nc = c+dc[i];
            if (nr < 0 || nr >= row || nc < 0 || nc >= col) continue;
            dfs(g, nr, nc);
        }
        return res;
    }

    private int dfs(int[][] g, int r, int c) {
        if (r < 0 || r >= row || c < 0 || c >= col) return 0;
        if (g[r][c] != 2) return 0;
        // visited marked to 3
        g[r][c] = 3;
        int res = 1;
        for (int i = 0; i < 4; i++) {
            res += dfs(g, r+dr[i], c+dc[i]);
        }
        return res;
    }

}

# 1575. 统计所有可行路径

暴力，超时：

class Solution {
    int cnt = 0;
    Set<String> set = new HashSet<>();
    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        recursive(locations, "", start, finish, fuel);
        return cnt;
    }

    private void recursive(int[] locations, String path, int cur, int finish, int fuel) {
        if (fuel < 0) return;
        path = path + ":" + cur;
        if (cur == finish && !set.contains(path)) {
            // System.out.println(path);
            set.add(path);
            cnt++;
        }
        for (int i = 0; i < locations.length; i++) {
            if (i == cur) continue;
            recursive(locations, path, i, finish, fuel-Math.abs(locations[cur]-locations[i]));
        }
    }
}

记忆化优化，能过，但比较慢：

class Solution {
    Set<String> set = new HashSet<>();
    Map<String, Long> cache = new HashMap<>();
    int mod = (int)1e9+7;
    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        return (int)recursive(locations, "", start, finish, fuel);
    }

    private long recursive(int[] locations, String path, int cur, int finish, int fuel) {
        if (fuel < 0) return 0;
        String key = cur+":"+fuel;
        Long ans = cache.get(key);
        if (ans != null) return ans;
        path = path + ":" + cur;
        long res = 0;
        if (cur == finish && !set.contains(path)) {
            // System.out.println(path);
            set.add(path);
            res++;
        }
        for (int i = 0; i < locations.length; i++) {
            if (i == cur) continue;
            res = (res + recursive(locations, path, i, finish, fuel-Math.abs(locations[cur]-locations[i]))) % mod;
        }
        
        cache.put(key, res);
        return res;
    }
}

# 72. 编辑距离

动态规划：

class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        char[] cs1 = word1.toCharArray();
        char[] cs2 = word2.toCharArray();

        int[][] dp = new int[n1+1][n2+1];
        for (int i = 0; i <= n1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= n2; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (cs1[i-1] == cs2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j-1], 
                            Math.min(dp[i][j-1], dp[i-1][j])) + 1;
                }
            }
        }
        return dp[n1][n2];
    }
}

# 63. 不同路径 II

动态规划：

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[][] dp = new int[n+1][m+1];
        dp[1][1] = obstacleGrid[0][0] == 1 ? 0 : 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 && j == 0) continue;
                if (obstacleGrid[i][j] == 1) continue;
                dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j];
            }
        }

        return dp[n][m];
    }
}

# 10. 正则表达式匹配

动态规划：

class Solution {
    public boolean isMatch(String _s, String _p) {
        char[] s = _s.toCharArray();
        char[] p = _p.toCharArray();
        int sn = s.length;
        int pn = p.length;

        boolean[][] dp = new boolean[sn+1][pn+1];
        // init
        dp[0][0] = true;
        // 从p串的第二个字符开始
        for (int j = 2; j < pn+1; j++) {
            dp[0][j] = p[j-1] == '*' && dp[0][j-2];
        }
        for (int i = 0; i < sn; i++) {
            for (int j = 0; j < pn; j++) {
                if (p[j] == '*') {
                    dp[i+1][j+1] = dp[i+1][j-1] || (firstMath(s, p, i, j-1) && dp[i][j+1]);
                } else {
                    dp[i+1][j+1] = firstMath(s, p, i, j) && dp[i][j];
                }
            }
        }
        return dp[sn][pn];
    }

    private boolean firstMath(char[] s, char[] p, int i, int j) {
        return s[i] == p[j] || p[j] == '.';
    }
}

# 337. 打家劫舍 III

暴力，递归，超时：

class Solution {
    public int rob(TreeNode root) {
        return recursive(root, false);
    }

    private int recursive(TreeNode node, boolean preSteal) {
        int res = 0;
        if (node == null) return res;
        if (preSteal) {
            res += recursive(node.left, false);
            res += recursive(node.right, false);
        } else {
            // 偷或不偷，选最大的
            int steal = node.val;
            steal += recursive(node.left, true);
            steal += recursive(node.right, true);

            int noSteal = 0;
            noSteal += recursive(node.left, false);
            noSteal += recursive(node.right, false);

            res = Math.max(steal, noSteal);
        }

        return res;
    }

}

记忆化递归，通过，速度一般，需要注意，递归方式与之前的暴力递归不一样了：

class Solution {
    Map<TreeNode, Integer> cache = new HashMap<>();
    public int rob(TreeNode root) {
        return dfs(root);
    }
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        Integer ans = cache.get(node);
        if (ans != null) return ans;
        int steal = node.val;
        if (node.left != null) {
            steal += (dfs(node.left.left) + dfs(node.left.right));
        }
        if (node.right != null) {
            steal += (dfs(node.right.left) + dfs(node.right.right));
        }
        
        int noSteal = dfs(node.left) + dfs(node.right);
        int res = Math.max(steal, noSteal);
        cache.put(node, res);
        return res;
    }

}

重刷，写法更简洁

class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }

    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] l = dfs(node.left);
        int[] r = dfs(node.right);
        int[] res = new int[2];
        res[0] = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        res[1] = l[0]+r[0]+node.val;
        return res;
    }
}

# 483. 最小好进制

数学...

# 327. 区间和的个数

不会。。先放弃

# 493. 翻转对

又一道不会的

修改于: 8/15/2022, 5:02:01 PM

← LeetCode 5 →