617. 合并二叉樹

https://leetcode.cn/problems/merge-two-binary-trees/

提示：
兩棵樹中的節(jié)點數(shù)目在范圍 [0, 2000] 內(nèi)
-10^4 <= Node.val <= 10^4

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 == null) return root2;else if (root2 == null) return root1;root1.val += root2.val;root1.left = mergeTrees(root1.left, root2.left);root1.right = mergeTrees(root1.right, root2.right);return root1;}
}

833. 字符串中的查找與替換（模擬）

https://leetcode.cn/problems/find-and-replace-in-string/

只看題面比較難以理解題目意思，得看一個示例：

提示：
1 <= s.length <= 1000
k == indices.length == sources.length == targets.length
1 <= k <= 100
0 <= indexes[i] < s.length
1 <= sources[i].length, targets[i].length <= 50
s 僅由小寫英文字母組成
sources[i] 和 targets[i] 僅由小寫英文字母組成

class Solution {public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {int n = s.length();String[] ans = new String[n];   // 存儲每個位置被換成了什么for (int i = 0; i < indices.length; ++i) {// 檢查是否需要替換if (indices[i] + sources[i].length() <= n && sources[i].equals(s.substring(indices[i], indices[i] + sources[i].length()))) {ans[indices[i]] = targets[i];for (int j = indices[i] + 1; j < indices[i] + sources[i].length(); ++j) ans[j] = "";}}// 沒有被替換的位置還是保持原樣for (int i = 0; i < n; ++i) {if (ans[i] == null) ans[i] = s.substring(i, i + 1);}return String.join("", ans);}
}

2682. 找出轉(zhuǎn)圈游戲輸家（模擬）

https://leetcode.cn/problems/find-the-losers-of-the-circular-game/

提示：
1 <= k <= n <= 50

class Solution {public int[] circularGameLosers(int n, int k) {int[] cnt = new int[n];int l = n;for (int i = 0, s = k; cnt[i] == 0; i = (i + s) % n, s += k) {l--;cnt[i]++;}int[] ans = new int[l];for (int i = 0, j = 0; i < n; ++i) {if (cnt[i] == 0) ans[j++] = i + 1;}return ans;}
}

為方便取模運算，循環(huán)中的下標可以從 0 開始，在返回時再加一。

1444. 切披薩的方案數(shù)（?????）

https://leetcode.cn/problems/number-of-ways-of-cutting-a-pizza/

提示：
1 <= rows, cols <= 50
rows == pizza.length
cols == pizza[i].length
1 <= k <= 10
pizza 只包含字符 'A' 和 '.' 。

解法——從遞歸到遞推到優(yōu)化（二維前綴和+記憶化搜索）

https://leetcode.cn/problems/number-of-ways-of-cutting-a-pizza/solutions/2392051/ji-bai-100cong-di-gui-dao-di-tui-dao-you-dxz5/

定義 dfs(c, i, j) 表示把左上角在 (i, j)，右下角在 (m - 1, n - 1) 的子矩陣切 c 刀，每塊都至少包含一個蘋果的方案數(shù)。

class Solution {static final int MOD = (int)1e9 + 7;int[][][] memo;public int ways(String[] pizza, int k) {MatrixSum ms = new MatrixSum(pizza);int m = pizza.length, n = pizza[0].length();memo = new int[k][m][n];for (int i = 0; i < k; ++i) {for (int j = 0; j < m; ++j) {Arrays.fill(memo[i][j], -1);}}return dfs(k - 1, 0, 0, ms, m, n);}public int dfs(int c, int i, int j, MatrixSum ms, int m, int n) {if (c == 0) {       // 不能再切了，檢查是否還剩下蘋果return ms.query(i, j, m, n) > 0? 1: 0;} if (memo[c][i][j] != -1) return memo[c][i][j];int res = 0;// 枚舉豎直切for (int j2 = j + 1; j2 < n; ++j2) {if (ms.query(i, j, m, j2) > 0) {res = (res + dfs(c - 1, i, j2, ms, m, n)) % MOD;}}// 枚舉水平切for (int i2 = i + 1; i2 < m; ++i2) {if (ms.query(i, j, i2, n) > 0) {res = (res + dfs(c - 1, i2, j, ms, m, n)) % MOD;}}return memo[c][i][j] = res;}
}// 二維前綴和模板（'A'的ASCII碼最低位為1，'.'的ASCII碼的最低位為0）
class MatrixSum {private final int[][] sum;public MatrixSum (String[] matrix) {int m = matrix.length, n = matrix[0].length();sum = new int[m + 1][n + 1];for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {sum[i + 1][j + 1] = (matrix[i].charAt(j) & 1) + sum[i + 1][j] + sum[i][j + 1] - sum[i][j];}}}// 返回左上角為(r1,c1)，右下角為(r2-1,c2-1)的子矩陣的元素和public int query(int r1, int c1, int r2, int c2) {return sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1];}
}

1388. 3n 塊披薩（?????腦筋急轉(zhuǎn)彎：轉(zhuǎn)換問題）

https://leetcode.cn/problems/pizza-with-3n-slices/

提示：
1 <= slices.length <= 500
slices.length % 3 == 0
1 <= slices[i] <= 1000

解法——將問題轉(zhuǎn)化為：選擇n個披薩，且任意兩個數(shù)不能相鄰，求這n個數(shù)的最大值（環(huán)形打家劫舍 + 最多買賣k次的股票）

有點像 環(huán)形打家劫舍 + 最多買賣k次的股票 的結(jié)合。

dp[i][j] 表示考慮 0 ~ i 下標的 slices，購買 j 個最大價值。

class Solution {public int maxSizeSlices(int[] slices) {int n = slices.length;int a = op(slices, 0, n - 2), b = op(slices, 1, n - 1);return Math.max(a, b);}public int op(int[] slices, int start, int end) {int n = end - start + 1, m = (n + 1) / 3;int[][] dp = new int[n][m + 1];for (int i = 0; i < n; ++i) Arrays.fill(dp[i], Integer.MIN_VALUE);dp[0][0] = 0;dp[0][1] = slices[start];dp[1][0] = 0;dp[1][1] = Math.max(slices[start], slices[start + 1]);for (int i = 2; i < n; ++i) {dp[i][0] = 0;for (int j = 1; j <= m; ++j) {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 2][j - 1] + slices[i + start]);}}return dp[n - 1][m];}
}

2235. 兩整數(shù)相加（真·夢開始的地方）

https://leetcode.cn/problems/add-two-integers/

提示：
-100 <= num1, num2 <= 100

class Solution {public int sum(int num1, int num2) {return num1 + num2;}
}

2236. 判斷根結(jié)點是否等于子結(jié)點之和（真·夢開始的地方2）

https://leetcode.cn/problems/root-equals-sum-of-children/description/

提示：
樹只包含根結(jié)點、左子結(jié)點和右子結(jié)點
-100 <= Node.val <= 100

class Solution {public boolean checkTree(TreeNode root) {return root.left.val + root.right.val == root.val;}
}