【LeetCode每日一题合集】2023.8.14-2023.8.20（⭐切披萨3n块披萨）

617. 合并二叉树

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

提示：
两棵树中的节点数目在范围 [0, 2000] 内
-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. 找出转圈游戏输家（模拟）

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;}
}

为方便取模运算，循环中的下标可以从 0 开始，在返回时再加一。

1444. 切披萨的方案数（⭐⭐⭐⭐⭐）

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' 和 '.' 。

解法——从递归到递推到优化（二维前缀和+记忆化搜索）

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 刀，每块都至少包含一个苹果的方案数。

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 块披萨（⭐⭐⭐⭐⭐脑筋急转弯：转换问题）

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

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

解法——将问题转化为：选择n个披萨，且任意两个数不能相邻，求这n个数的最大值（环形打家劫舍 + 最多买卖k次的股票）

有点像 环形打家劫舍 + 最多买卖k次的股票 的结合。

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. 两整数相加（真·梦开始的地方）

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

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

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

2236. 判断根结点是否等于子结点之和（真·梦开始的地方2）

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

提示：
树只包含根结点、左子结点和右子结点
-100 <= Node.val <= 100

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