6.摘樱桃
题目链接：741. 摘樱桃
给你一个 n x n 的网格 grid ，代表一块樱桃地，每个格子由以下三种数字的一种来表示：
0 表示这个格子是空的，所以你可以穿过它。
1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
-1 表示这个格子里有荆棘，挡着你的路。
请你统计并返回：在遵守下列规则的情况下，能摘到的最多樱桃数：
从位置 (0, 0) 出发，最后到达 (n - 1, n - 1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为 0 或者 1 的格子）；
当到达 (n - 1, n - 1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为 0 ）；
如果在 (0, 0) 和 (n - 1, n - 1) 之间不存在一条可经过的路径，则无法摘到任何一个樱桃。
示例 1：
输入：grid = [[0,1,-1],[1,0,-1],[1,1,1]]
输出：5
解释：玩家从 (0, 0) 出发：向下、向下、向右、向右移动至 (2, 2) 。
在这一次行程中捡到 4 个樱桃，矩阵变成 [[0,1,-1],[0,0,-1],[0,0,0]] 。
然后，玩家向左、向上、向上、向左返回起点，再捡到 1 个樱桃。
总共捡到 5 个樱桃，这是最大可能值。
示例 2：
输入：grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
输出：0
提示：
n == grid.length
n == grid[i].length
1 <= n <= 50
grid[i][j] 为 -1、0 或 1
grid[0][0] != -1
grid[n - 1][n - 1] != -1
题解：
方法：记忆化搜索 动态规划
class Solution { public int cherryPickup(int[][] grid) { int n = grid.length; int[][][] memo = new int[n * 2 - 1][n][n]; for (int[][] m : memo) { for (int[] r : m) { Arrays.fill(r, -1); // -1 表示没有计算过 } } return Math.max(dfs(n * 2 - 2, n - 1, n - 1, grid, memo), 0); } private int dfs(int t, int j, int k, int[][] grid, int[][][] memo) { // 不能出界，不能访问 -1 格子 if (j < 0 || k < 0 || t < j || t < k || grid[t - j][j] < 0 || grid[t - k][k] < 0) { return Integer.MIN_VALUE; } if (t == 0) { // 此时 j = k = 0 return grid[0][0]; } if (memo[t][j][k] != -1) { // 之前计算过 return memo[t][j][k]; } int res = Math.max( Math.max(dfs(t - 1, j, k, grid, memo), dfs(t - 1, j, k - 1, grid, memo)), Math.max(dfs(t - 1, j - 1, k, grid, memo), dfs(t - 1, j - 1, k - 1, grid, memo))) + grid[t - j][j] + (k != j ? grid[t - k][k] : 0); memo[t][j][k] = res; // 记忆化 return res; } }
7.摘樱桃 II
题目链接：1463. 摘樱桃 II
给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。
你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 (0,0) 出发，机器人 2 从右上角格子 (0, cols-1) 出发。
请你按照如下规则，返回两个机器人能收集的最多樱桃数目：
从格子 (i,j) 出发，机器人可以移动到格子 (i+1, j-1)，(i+1, j) 或者 (i+1, j+1) 。
当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。
当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。
两个机器人在任意时刻都不能移动到 grid 外面。
两个机器人最后都要到达 grid 最底下一行。
示例 1：
输入：grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
输出：24
解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (3 + 2 + 5 + 2) = 12 。
机器人 2 摘的樱桃数目为 (1 + 5 + 5 + 1) = 12 。
樱桃总数为： 12 + 12 = 24 。
示例 2：
输入：grid =
[[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
输出：28
解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (1 + 9 + 5 + 2) = 17 。
机器人 2 摘的樱桃数目为 (1 + 3 + 4 + 3) = 11 。
樱桃总数为： 17 + 11 = 28 。
示例 3：
输入：grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
输出：22
示例 4：
输入：grid = [[1,1],[1,1]]
输出：4
提示：
rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100
题解：
方法：动态规划
class Solution { public int cherryPickup(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][][] memo = new int[m][n][n]; for (int[][] me : memo) { for (int[] r : me) { Arrays.fill(r, -1); // -1 表示没有计算过 } } return dfs(0, 0, n - 1, grid, memo); } private int dfs(int i, int j, int k, int[][] grid, int[][][] memo) { int m = grid.length; int n = grid[0].length; if (i == m || j < 0 || j >= n || k < 0 || k >= n) { return 0; } if (memo[i][j][k] != -1) { // 之前计算过 return memo[i][j][k]; } int res = 0; for (int j2 = j - 1; j2 <= j + 1; j2++) { for (int k2 = k - 1; k2 <= k + 1; k2++) { res = Math.max(res, dfs(i + 1, j2, k2, grid, memo)); } } res += grid[i][j] + (k != j ? grid[i][k] : 0); memo[i][j][k] = res; // 记忆化 return res; } }
8.给植物浇水
题目链接：2079. 给植物浇水
你打算用一个水罐给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。x = -1 处有一条河，你可以在那里重新灌满你的水罐。
每一株植物都需要浇特定量的水。你将会按下面描述的方式完成浇水：
按从左到右的顺序给植物浇水。
在给当前植物浇完水之后，如果你没有足够的水 完全 浇灌下一株植物，那么你就需要返回河边重新装满水罐。
你 不能 提前重新灌满水罐。
最初，你在河边（也就是，x = -1），在 x 轴上每移动 一个单位 都需要 一步 。
给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。另有一个整数 capacity 表示水罐的容量，返回浇灌所有植物需要的 步数 。
示例 1：
输入：plants = [2,2,3,3], capacity = 5
输出：14
解释：从河边开始，此时水罐是装满的：
- 走到植物 0 (1 步) ，浇水。水罐中还有 3 单位的水。
- 走到植物 1 (1 步) ，浇水。水罐中还有 1 单位的水。
- 由于不能完全浇灌植物 2 ，回到河边取水 (2 步)。
- 走到植物 2 (3 步) ，浇水。水罐中还有 2 单位的水。
- 由于不能完全浇灌植物 3 ，回到河边取水 (3 步)。
- 走到植物 3 (4 步) ，浇水。
需要的步数是 = 1 + 1 + 2 + 3 + 3 + 4 = 14 。
示例 2：
输入：plants = [1,1,1,4,2,3], capacity = 4
输出：30
解释：从河边开始，此时水罐是装满的：
- 走到植物 0，1，2 (3 步) ，浇水。回到河边取水 (3 步)。
- 走到植物 3 (4 步) ，浇水。回到河边取水 (4 步)。
- 走到植物 4 (5 步) ，浇水。回到河边取水 (5 步)。
- 走到植物 5 (6 步) ，浇水。
需要的步数是 = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30 。
示例 3：
输入：plants = [7,7,7,7,7,7,7], capacity = 8
输出：49
解释：每次浇水都需要重新灌满水罐。
需要的步数是 = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49 。
提示：
n == plants.length
1 <= n <= 1000
1 <= plants[i] <= 106
max(plants[i]) <= capacity <= 109
题解：
方法：模拟
class Solution { public int wateringPlants(int[] plants, int capacity) { int ans = 0, water = capacity; for (int i = 0; i < plants.length; ++i) { if (water >= plants[i]) { water -= plants[i]; ans += 1; } else { water = capacity - plants[i]; ans += i * 2 + 1; } } return ans; } }
9.给植物浇水 II
题目链接：2105. 给植物浇水 II
Alice 和 Bob 打算给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。
每一株植物都需要浇特定量的水。Alice 和 Bob 每人有一个水罐，最初是满的 。他们按下面描述的方式完成浇水：
Alice 按 从左到右 的顺序给植物浇水，从植物 0 开始。Bob 按 从右到左 的顺序给植物浇水，从植物 n - 1 开始。他们 同时 给植物浇水。
无论需要多少水，为每株植物浇水所需的时间都是相同的。
如果 Alice/Bob 水罐中的水足以 完全 灌溉植物，他们 必须 给植物浇水。否则，他们 首先（立即）重新装满罐子，然后给植物浇水。
如果 Alice 和 Bob 到达同一株植物，那么当前水罐中水 更多 的人会给这株植物浇水。如果他俩水量相同，那么 Alice 会给这株植物浇水。
给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。另有两个整数 capacityA 和 capacityB 分别表示 Alice 和 Bob 水罐的容量。返回两人浇灌所有植物过程中重新灌满水罐的 次数 。
示例 1：
输入：plants = [2,2,3,3], capacityA = 5, capacityB = 5
输出：1
解释：
- 最初，Alice 和 Bob 的水罐中各有 5 单元水。
- Alice 给植物 0 浇水，Bob 给植物 3 浇水。
- Alice 和 Bob 现在分别剩下 3 单元和 2 单元水。
- Alice 有足够的水给植物 1 ，所以她直接浇水。Bob 的水不够给植物 2 ，所以他先重新装满水，再浇水。
所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 0 + 1 + 0 = 1 。
示例 2：
输入：plants = [2,2,3,3], capacityA = 3, capacityB = 4
输出：2
解释：
- 最初，Alice 的水罐中有 3 单元水，Bob 的水罐中有 4 单元水。
- Alice 给植物 0 浇水，Bob 给植物 3 浇水。
- Alice 和 Bob 现在都只有 1 单元水，并分别需要给植物 1 和植物 2 浇水。
- 由于他们的水量均不足以浇水，所以他们重新灌满水罐再进行浇水。
所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 1 + 1 + 0 = 2 。
示例 3：
输入：plants = [5], capacityA = 10, capacityB = 8
输出：0
解释：
- 只有一株植物
- Alice 的水罐有 10 单元水，Bob 的水罐有 8 单元水。因此 Alice 的水罐中水更多，她会给这株植物浇水。
所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 。
提示：
n == plants.length
1 <= n <= 105
1 <= plants[i] <= 106
max(plants[i]) <= capacityA, capacityB <= 109
题解：
方法：模拟
class Solution { public int minimumRefill(int[] plants, int capacityA, int capacityB) { int ans = 0; int a = capacityA; int b = capacityB; int i = 0; int j = plants.length - 1; while (i < j) { // Alice 给植物 i 浇水 if (a < plants[i]) { // 没有足够的水，重新灌满水罐 ans++; a = capacityA; } a -= plants[i++]; // Bob 给植物 j 浇水 if (b < plants[j]) { // 没有足够的水，重新灌满水罐 ans++; b = capacityB; } b -= plants[j--]; } // Alice 和 Bob 到达同一株植物，那么当前水罐中水更多的人会给这株植物浇水 if (i == j && Math.max(a, b) < plants[i]) { // 没有足够的水，重新灌满水罐 ans++; } return ans; } }
10.统计已测试设备
题目链接：2960. 统计已测试设备
给你一个长度为 n 、下标从 0 开始的整数数组 batteryPercentages ，表示 n 个设备的电池百分比。
你的任务是按照顺序测试每个设备 i，执行以下测试操作：
如果 batteryPercentages[i] 大于 0：
增加 已测试设备的计数。
将下标在 [i + 1, n - 1] 的所有设备的电池百分比减少 1，确保它们的电池百分比 不会低于 0 ，即 batteryPercentages[j] = max(0, batteryPercentages[j] - 1)。
移动到下一个设备。
否则，移动到下一个设备而不执行任何测试。
返回一个整数，表示按顺序执行测试操作后 已测试设备 的数量。
示例 1：
输入：batteryPercentages = [1,1,2,1,3]
输出：3
解释：按顺序从设备 0 开始执行测试操作：
在设备 0 上，batteryPercentages[0] > 0 ，现在有 1 个已测试设备，batteryPercentages 变为
[1,0,1,0,2] 。
在设备 1 上，batteryPercentages[1] == 0 ，移动到下一个设备而不进行测试。
在设备 2 上，batteryPercentages[2] > 0 ，现在有 2 个已测试设备，batteryPercentages 变为
[1,0,1,0,1] 。
在设备 3 上，batteryPercentages[3] == 0 ，移动到下一个设备而不进行测试。
在设备 4 上，batteryPercentages[4] > 0 ，现在有 3 个已测试设备，batteryPercentages
保持不变。
因此，答案是 3 。
示例 2：
输入：batteryPercentages = [0,1,2]
输出：2
解释：按顺序从设备 0 开始执行测试操作：
在设备 0 上，batteryPercentages[0] == 0 ，移动到下一个设备而不进行测试。
在设备 1 上，batteryPercentages[1] > 0 ，现在有 1 个已测试设备，batteryPercentages 变为
[0,1,1] 。
在设备 2 上，batteryPercentages[2] > 0 ，现在有 2 个已测试设备，batteryPercentages
保持不变。
因此，答案是 2 。
提示：
1 <= n == batteryPercentages.length <= 100
0 <= batteryPercentages[i] <= 100
题解：
方法：模拟
class Solution { public int countTestedDevices(int[] batteryPercentages) { int dec = 0; for (int x : batteryPercentages) { if (x > dec) { dec++; } } return dec; } }
11.收集垃圾的最少总时间
题目链接：2391. 收集垃圾的最少总时间
给你一个下标从 0 开始的字符串数组 garbage ，其中 garbage[i] 表示第 i 个房子的垃圾集合。garbage[i] 只包含字符 ‘M’ ，‘P’ 和 ‘G’ ，但可能包含多个相同字符，每个字符分别表示一单位的金属、纸和玻璃。垃圾车收拾 一 单位的任何一种垃圾都需要花费 1 分钟。
同时给你一个下标从 0 开始的整数数组 travel ，其中 travel[i] 是垃圾车从房子 i 行驶到房子 i + 1 需要的分钟数。
城市里总共有三辆垃圾车，分别收拾三种垃圾。每辆垃圾车都从房子 0 出发，按顺序 到达每一栋房子。但它们 不是必须 到达所有的房子。
任何时刻只有 一辆 垃圾车处在使用状态。当一辆垃圾车在行驶或者收拾垃圾的时候，另外两辆车 不能 做任何事情。
请你返回收拾完所有垃圾需要花费的 最少 总分钟数。
示例 1：
输入：garbage = [“G”,“P”,“GP”,“GG”], travel = [2,4,3]
输出：21
解释：
收拾纸的垃圾车：
- 从房子 0 行驶到房子 1
- 收拾房子 1 的纸垃圾
- 从房子 1 行驶到房子 2
- 收拾房子 2 的纸垃圾
收拾纸的垃圾车总共花费 8 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车：
- 收拾房子 0 的玻璃垃圾
- 从房子 0 行驶到房子 1
- 从房子 1 行驶到房子 2
- 收拾房子 2 的玻璃垃圾
- 从房子 2 行驶到房子 3
- 收拾房子 3 的玻璃垃圾
收拾玻璃的垃圾车总共花费 13 分钟收拾完所有的玻璃垃圾。
由于没有金属垃圾，收拾金属的垃圾车不需要花费任何时间。
所以总共花费 8 + 13 = 21 分钟收拾完所有垃圾。
示例 2：
输入：garbage = [“MMM”,“PGM”,“GP”], travel = [3,10]
输出：37
解释：
收拾金属的垃圾车花费 7 分钟收拾完所有的金属垃圾。
收拾纸的垃圾车花费 15 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车花费 15 分钟收拾完所有的玻璃垃圾。
总共花费 7 + 15 + 15 = 37 分钟收拾完所有的垃圾。
提示：
2 <= garbage.length <= 105
garbage[i] 只包含字母 ‘M’ ，‘P’ 和 ‘G’ 。
1 <= garbage[i].length <= 10
travel.length == garbage.length - 1
1 <= travel[i] <= 100
题解：
方法：多次遍历
class Solution { public int garbageCollection(String[] garbage, int[] travel) { int ans = 0; for (String g : garbage) { ans += g.length(); } for (int t : travel) { ans += t * 3; } for (char c : new char[]{'M', 'P', 'G'}) { for (int i = garbage.length - 1; i > 0 && garbage[i].indexOf(c) < 0; i--) { ans -= travel[i - 1]; // 没有垃圾 c，多跑了 } } return ans; } }
方法：正序一次遍历
class Solution { public int garbageCollection(String[] garbage, int[] travel) { int ans = garbage[0].length(); int sumT = 0; int[] tMap = new int[4]; // 如果垃圾种类更多，可以改成哈希表 for (int i = 1; i < garbage.length; i++) { char[] s = garbage[i].toCharArray(); ans += s.length; sumT += travel[i - 1]; for (char c : s) { tMap[c & 3] = sumT; // MPG 的 ASCII 值的低两位互不相同 } } for (int t : tMap) { ans += t; } return ans; } }
方法：倒序一次遍历（贡献法）
class Solution { public int garbageCollection(String[] garbage, int[] travel) { int ans = garbage[0].length(); HashSet<Character> seen = new HashSet<>(); for (int i = garbage.length - 1; i > 0; i--) { char[] g = garbage[i].toCharArray(); for (char c : g) { seen.add(c); } ans += g.length + travel[i - 1] * seen.size(); } return ans; } }
12.吃掉 N 个橘子的最少天数
题目链接：1553. 吃掉 N 个橘子的最少天数
厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：
吃掉一个橘子。
如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。
如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。
每天你只能从以上 3 种方案中选择一种方案。
请你返回吃掉所有 n 个橘子的最少天数。
示例 1：
输入：n = 10
输出：4
解释：你总共有 10 个橘子。
第 1 天：吃 1 个橘子，剩余橘子数 10 - 1 = 9。
第 2 天：吃 6 个橘子，剩余橘子数 9 - 2*(9/3) = 9 - 6 = 3。（9 可以被 3 整除）
第 3 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。
第 4 天：吃掉最后 1 个橘子，剩余橘子数 1 - 1 = 0。
你需要至少 4 天吃掉 10 个橘子。
示例 2：
输入：n = 6
输出：3
解释：你总共有 6 个橘子。
第 1 天：吃 3 个橘子，剩余橘子数 6 - 6/2 = 6 - 3 = 3。（6 可以被 2 整除）
第 2 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。（3 可以被 3 整除）
第 3 天：吃掉剩余 1 个橘子，剩余橘子数 1 - 1 = 0。
你至少需要 3 天吃掉 6 个橘子。
示例 3：
输入：n = 1
输出：1
示例 4：
输入：n = 56
输出：6
提示：
1 <= n <= 2*10^9
题解：
方法：Dijkstra求最短路
class Solution { public int minDays(int n) { Map<Integer, Integer> dis = new HashMap<>(); dis.put(n, 0); PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); pq.offer(new int[]{0, n}); while (true) { int[] p = pq.poll(); int dx = p[0]; int x = p[1]; if (x <= 1) { return dx + x; } if (dx > dis.get(x)) { continue; } for (int d = 2; d <= 3; d++) { int y = x / d; int dy = dx + x % d + 1; if (dy < dis.getOrDefault(y, Integer.MAX_VALUE)) { dis.put(y, dy); pq.offer(new int[]{dy, y}); } } } } }
