做淘宝网站代理,wordpress+简书+比较,深圳二维码网站建设,crm系统官网文章目录 617. 合并二叉树833. 字符串中的查找与替换#xff08;模拟#xff09;2682. 找出转圈游戏输家#xff08;模拟#xff09;1444. 切披萨的方案数#xff08;⭐⭐⭐⭐⭐#xff09;解法——从递归到递推到优化#xff08;二维前缀和记忆化搜索#xff09; 1388… 文章目录 617. 合并二叉树833. 字符串中的查找与替换模拟2682. 找出转圈游戏输家模拟1444. 切披萨的方案数⭐⭐⭐⭐⭐解法——从递归到递推到优化二维前缀和记忆化搜索 1388. 3n 块披萨⭐⭐⭐⭐⭐脑筋急转弯转换问题解法——将问题转化为选择n个披萨且任意两个数不能相邻求这n个数的最大值环形打家劫舍 最多买卖k次的股票 2235. 两整数相加真·梦开始的地方2236. 判断根结点是否等于子结点之和真·梦开始的地方2 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;}
}
