22.组合总和 Ⅳ
题目链接：377. 组合总和 Ⅳ
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3
输出：0
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000
题解：
方法：递归 记忆化搜索 动态规划
class Solution { public int combinationSum4(int[] nums, int target) { int[] memo = new int[target + 1]; Arrays.fill(memo, -1); // -1 表示没有计算过 return dfs(target, nums, memo); } private int dfs(int i, int[] nums, int[] memo) { if (i == 0) { // 爬完了 return 1; } if (memo[i] != -1) { // 之前计算过 return memo[i]; } int res = 0; for (int x : nums) { // 枚举所有可以爬的台阶数 if (x <= i) { res += dfs(i - x, nums, memo); } } return memo[i] = res; // 记忆化 } }
23.爱生气的书店老板
题目链接：1052. 爱生气的书店老板
有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。
当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。
请你返回 这一天营业下来，最多有多少客户能够感到满意 。
示例 1：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes
= 3
输出：16
解释：书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
示例 2：
输入：customers = [1], grumpy = [0], minutes = 1
输出：1
提示：
n == customers.length == grumpy.length
1 <= minutes <= n <= 2 * 104
0 <= customers[i] <= 1000
grumpy[i] == 0 or 1
题解：
方法：滑动窗口
本题可以拆分成两个问题：
- 老板不生气时的顾客数量之和 s0。这些顾客可以感到满意。
- 长度为 minutes 的连续子数组中，老板生气时的顾客数量之和 s1的最大值 maxS1。这些顾客可以感到满意。
最终答案为 s0+maxS1。
class Solution { public int maxSatisfied(int[] customers, int[] grumpy, int minutes) { int[] s = new int[2]; int maxS1 = 0; for (int i = 0; i < customers.length; i++) { s[grumpy[i]] += customers[i]; if (i < minutes - 1) { // 窗口长度不足 minutes continue; } maxS1 = Math.max(maxS1, s[1]); // 窗口最左边元素离开窗口 s[1] -= grumpy[i - minutes + 1] > 0 ? customers[i - minutes + 1] : 0; } return s[0] + maxS1; } }
24.感染二叉树需要的总时间
题目链接：2385. 感染二叉树需要的总时间
给你一棵二叉树的根节点 root ，二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟，感染 将会从值为 start 的节点开始爆发。
每分钟，如果节点满足以下全部条件，就会被感染：
节点此前还没有感染。
节点与一个已感染节点相邻。
返回感染整棵树需要的分钟数。
示例 1：
输入：root = [1,5,3,null,4,10,6,9,2], start = 3
输出：4
解释：节点按以下过程被感染：
- 第 0 分钟：节点 3
- 第 1 分钟：节点 1、10、6
- 第 2 分钟：节点5
- 第 3 分钟：节点 4
- 第 4 分钟：节点 9 和 2
感染整棵树需要 4 分钟，所以返回 4 。
示例 2：
输入：root = [1], start = 1
输出：0
解释：第 0 分钟，树中唯一一个节点处于感染状态，返回 0 。
提示：
树中节点的数目在范围 [1, 105] 内
1 <= Node.val <= 105
每个节点的值 互不相同
树中必定存在值为 start 的节点
题解：
方法：DFS
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { private TreeNode startNode; private final Map<TreeNode, TreeNode> fa = new HashMap<>(); public int amountOfTime(TreeNode root, int start) { dfs(root, null, start); return maxDepth(startNode, startNode); } private void dfs(TreeNode node, TreeNode from, int start) { if (node == null) { return; } fa.put(node, from); // 记录每个节点的父节点 if (node.val == start) { startNode = node; // 找到 start } dfs(node.left, node, start); dfs(node.right, node, start); } private int maxDepth(TreeNode node, TreeNode from) { if (node == null) { return -1; // 注意这里是 -1，因为 start 的深度为 0 } int res = -1; if (node.left != from) { res = Math.max(res, maxDepth(node.left, node)); } if (node.right != from) { res = Math.max(res, maxDepth(node.right, node)); } if (fa.get(node) != from) { res = Math.max(res, maxDepth(fa.get(node), node)); } return res + 1; } }
25.总行驶距离
题目链接：2739. 总行驶距离
卡车有两个油箱。给你两个整数，mainTank 表示主油箱中的燃料（以升为单位），additionalTank 表示副油箱中的燃料（以升为单位）。
该卡车每耗费 1 升燃料都可以行驶 10 km。每当主油箱使用了 5 升燃料时，如果副油箱至少有 1 升燃料，则会将 1 升燃料从副油箱转移到主油箱。
返回卡车可以行驶的最大距离。
注意：从副油箱向主油箱注入燃料不是连续行为。这一事件会在每消耗 5 升燃料时突然且立即发生。
示例 1：
输入：mainTank = 5, additionalTank = 10
输出：60
解释：
在用掉 5 升燃料后，主油箱中燃料还剩下 (5 - 5 + 1) = 1 升，行驶距离为 50km 。
在用掉剩下的 1 升燃料后，没有新的燃料注入到主油箱中，主油箱变为空。
总行驶距离为 60km 。
示例 2：
输入：mainTank = 1, additionalTank = 2
输出：10
解释：
在用掉 1 升燃料后，主油箱变为空。
总行驶距离为 10km 。
提示：
1 <= mainTank, additionalTank <= 100
题解：
方法：模拟
class Solution { public int distanceTraveled(int mainTank, int additionalTank) { int ans = 0; while (mainTank >= 5) { mainTank -= 5; ans += 50; if (additionalTank > 0) { additionalTank--; mainTank++; } } return ans + mainTank * 10; } }
方法：快速模拟
class Solution { public int distanceTraveled(int mainTank, int additionalTank) { int ans = 0; while (mainTank >= 5) { int t = mainTank / 5; ans += t * 50; mainTank %= 5; t = Math.min(t, additionalTank); additionalTank -= t; mainTank += t; } return ans + mainTank * 10; } }
26.快照数组
题目链接：1146. 快照数组
实现支持下列接口的「快照数组」- SnapshotArray：
SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。
void set(index, val) - 会将指定索引 index 处的元素设置为 val。
int snap() - 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。
int get(index, snap_id) - 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。
示例：
输入：[“SnapshotArray”,“set”,“snap”,“set”,“get”]
[[3],[0,5],[],[0,6],[0,0]]
输出：[null,null,0,null,5]
解释：
SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组
snapshotArr.set(0,5); // 令 array[0] = 5
snapshotArr.snap(); // 获取快照，返回 snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0); // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5
提示：
1 <= length <= 50000
题目最多进行50000 次set，snap，和 get的调用 。
0 <= index < length
0 <= snap_id < 我们调用 snap() 的总次数
0 <= val <= 10^9
题解：
方法：哈希表 二分查找
class SnapshotArray { // 当前快照编号，初始值为 0 private int curSnapId; // 每个 index 的历史修改记录 private final Map<Integer, List<int[]>> history = new HashMap<>(); public SnapshotArray(int length) { } public void set(int index, int val) { history.computeIfAbsent(index, k -> new ArrayList<>()).add(new int[]{curSnapId, val}); } public int snap() { return curSnapId++; } public int get(int index, int snapId) { if (!history.containsKey(index)) { return 0; } List<int[]> h = history.get(index); int j = search(h, snapId); return j < 0 ? 0 : h.get(j)[1]; } // 返回最大的下标 i，满足 h[i][0] <= x // 如果不存在则返回 -1 private int search(List<int[]> h, int x) { // 开区间 (left, right) int left = -1; int right = h.size(); while (left + 1 < right) { // 区间不为空 // 循环不变量： // h[left][0] <= x // h[right][1] > x int mid = left + (right - left) / 2; if (h.get(mid)[0] <= x) { left = mid; // 区间缩小为 (mid, right) } else { right = mid; // 区间缩小为 (left, mid) } } // 根据循环不变量，此时 h[left][0] <= x 且 h[left+1][0] = h[right][0] > x // 所以 left 是最大的满足 h[left][0] <= x 的下标 // 如果不存在，则 left 为其初始值 -1 return left; } } /** * Your SnapshotArray object will be instantiated and called as such: * SnapshotArray* obj = new SnapshotArray(length); * obj->set(index,val); * int param_2 = obj->snap(); * int param_3 = obj->get(index,snap_id); */
27.查询网格图中每一列的宽度
题目链接：2639. 查询网格图中每一列的宽度
给你一个下标从 0 开始的 m x n 整数矩阵 grid 。矩阵中某一列的宽度是这一列数字的最大 字符串长度 。
比方说，如果 grid = [[-10], [3], [12]] ，那么唯一一列的宽度是 3 ，因为 -10 的字符串长度为 3 。
请你返回一个大小为 n 的整数数组 ans ，其中 ans[i] 是第 i 列的宽度。
一个有 len 个数位的整数 x ，如果是非负数，那么 字符串长度 为 len ，否则为 len + 1 。
示例 1：
输入：grid = [[1],[22],[333]]
输出：[3]
解释：第 0 列中，333 字符串长度为 3 。
示例 2：
输入：grid = [[-15,1,3],[15,7,12],[5,6,-2]]
输出：[3,1,2]
解释：
第 0 列中，只有 -15 字符串长度为 3 。
第 1 列中，所有整数的字符串长度都是 1 。
第 2 列中，12 和 -2 的字符串长度都为 2 。
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 100
-109 <= grid[r][c] <= 109
题解：
方法：数学
遍历每一列，求出数字转成字符串后的最大长度。
class Solution { public int[] findColumnWidth(int[][] grid) { int n = grid[0].length; int[] ans = new int[n]; for (int j = 0; j < n; j++) { for (int[] row : grid) { ans[j] = Math.max(ans[j], Integer.toString(row[j]).length()); } } return ans; } }
也可以手动计算长度。
class Solution { public int[] findColumnWidth(int[][] grid) { int n = grid[0].length; int[] ans = new int[n]; for (int j = 0; j < n; j++) { for (int[] row : grid) { int len = row[j] <= 0 ? 1 : 0; for (int x = row[j]; x != 0; x /= 10) { len++; } ans[j] = Math.max(ans[j], len); } } return ans; } }
优化
class Solution { public int[] findColumnWidth(int[][] grid) { int n = grid[0].length; int[] ans = new int[n]; for (int j = 0; j < n; j++) { int mn = 0; int mx = 0; for (int[] row : grid) { mn = Math.min(mn, row[j]); mx = Math.max(mx, row[j]); } int len = 1; for (int x = Math.max(mx / 10, -mn); x > 0; x /= 10) { len++; } ans[j] = len; } return ans; } }
28.负二进制转换
题目链接：1017. 负二进制转换
给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（base -2）表示。
注意，除非字符串就是 “0”，否则返回的字符串中不能含有前导零。
示例 1：
输入：n = 2
输出：“110”
解释：(-2)2 + (-2)1 = 2
示例 2：
输入：n = 3
输出：“111”
解释：(-2)2 + (-2)1 + (-2)0 = 3
示例 3：
输入：n = 4
输出：“100”
解释：(-2)2 = 4
提示：
0 <= n <= 109
题解：
方法：模拟 数学
进制转换取余必须为正数
class Solution { public String baseNeg2(int n) { if(n == 0)return "0"; // 0直接返回 StringBuilder res = new StringBuilder(); // 类似十进制转二进制的方法，只是余数如果为负数需要修正 while(n != 0){ int mod = n % (-2); n = n / (-2); if(mod == -1){ // 修正余数为-1->1，对应商也要加1 n++; mod = 1; } res.append(mod); } return res.reverse().toString(); // 生成的二进制是逆序的，需要反转 } }
