t3导致心态出了一点微妙的变化，然后t4疯狂wrong
t3怎么都不过了，第二天早上才找出bug，自定义排序的时候因为待排元素为Integer类型，并不是int类型，所以不能直接比较是否相等，而是得调用函数Integer.compare()，吃一堑长一智！！！
5971. 打折购买糖果的最小开销
一家商店正在打折销售糖果。每购买 两个 糖果，商店会 免费 送一个糖果。
免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的 较小值 。
- 比方说，总共有 4 个糖果，价格分别为 1 ，2 ，3 和 4 ，一位顾客买了价格为 2 和 3 的糖果，那么他可以免费获得价格为 1 的糖果，但不能获得价格为 4 的糖果。
给你一个下标从 0 开始的整数数组 cost ，其中 cost[i] 表示第 i 个糖果的价格，请你返回获得 所有 糖果的 最小 总开销。
示例 1：
输入：cost = [1,2,3] 输出：5 解释：我们购买价格为 2 和 3 的糖果，然后免费获得价格为 1 的糖果。 总开销为 2 + 3 = 5 。这是开销最小的 唯一 方案。 注意，我们不能购买价格为 1 和 3 的糖果，并免费获得价格为 2 的糖果。 这是因为免费糖果的价格必须小于等于购买的 2 个糖果价格的较小值。
示例 2：
输入：cost = [6,5,7,9,2,2] 输出：23 解释：最小总开销购买糖果方案为： - 购买价格为 9 和 7 的糖果 - 免费获得价格为 6 的糖果 - 购买价格为 5 和 2 的糖果 - 免费获得价格为 2 的最后一个糖果 因此，最小总开销为 9 + 7 + 5 + 2 = 23 。
示例 3：
输入：cost = [5,5] 输出：10 解释：由于只有 2 个糖果，我们需要将它们都购买，而且没有免费糖果。 所以总最小开销为 5 + 5 = 10 。
提示：
- 1 <= cost.length <= 100
- 1 <= cost[i] <= 100
思路：
贪心， 从大到小排序吗，没三个买前两个
class Solution {public int minimumCost(int[] cost) {Arrays.sort(cost);int sum = 0;for (int i = cost.length - 1; i >= 0; ) {sum += cost[i];if (i - 1 >= 0)sum += cost[i - 1];i -= 3;}return sum;}}
5972. 统计隐藏数组数目
给你一个下标从 0 开始且长度为 n 的整数数组 differences ，它表示一个长度为 n + 1 的 隐藏 数组 相邻 元素之间的 差值 。更正式的表述为：我们将隐藏数组记作 hidden ，那么 differences[i] = hidden[i + 1] - hidden[i] 。
同时给你两个整数 lower 和 upper ，它们表示隐藏数组中所有数字的值都在 闭 区间 [lower, upper] 之间。
- 比方说，differences = [1, -3, 4] ，lower = 1 ，upper = 6 ，那么隐藏数组是一个长度为 4 且所有值都在 1 和 6 （包含两者）之间的数组。
- [3, 4, 1, 5] 和 [4, 5, 2, 6] 都是符合要求的隐藏数组。
- [5, 6, 3, 7] 不符合要求，因为它包含大于 6 的元素。
- [1, 2, 3, 4] 不符合要求，因为相邻元素的差值不符合给定数据。
请你返回 符合 要求的隐藏数组的数目。如果没有符合要求的隐藏数组，请返回 0 。
示例 1：
输入：differences = [1,-3,4], lower = 1, upper = 6 输出：2 解释：符合要求的隐藏数组为： - [3, 4, 1, 5] - [4, 5, 2, 6] 所以返回 2 。
示例 2：
输入：differences = [3,-4,5,1,-2], lower = -4, upper = 5 输出：4 解释：符合要求的隐藏数组为： - [-3, 0, -4, 1, 2, 0] - [-2, 1, -3, 2, 3, 1] - [-1, 2, -2, 3, 4, 2] - [0, 3, -1, 4, 5, 3] 所以返回 4 。
示例 3：
输入：differences = [4,-7,2], lower = 3, upper = 6 输出：0 解释：没有符合要求的隐藏数组，所以返回 0 。
提示：
- n == differences.length
- 1 <= n <= 105
- -105 <= differences[i] <= 105
- -105 <= lower <= upper <= 105
思路：
本质是一个差分数组，将原数组还原，找到最大最小值的差值minus，与给定区间比较upper - lower
若minus > upper - lower返回0
否则返回upper - lower - minus + 1
:::danger
注意本题可能会爆int
:::
class Solution {public int numberOfArrays(int[] d, int lower, int upper) {int n = d.length;long[] a = new long[n + 1];long min = 0, max = 0;for (int i = 0; i < n; i++) {a[i + 1] = a[i] + d[i];min = Math.min(min, a[i + 1]);max = Math.max(max, a[i + 1]);}// System.out.println(Arrays.toString(a));long minus = max - min;long cnt = Math.max(upper - lower - minus + 1, 0);return (int)cnt;}}
5973. 价格范围内最高排名的 K 样物品
给你一个下标从 0 开始的二维整数数组 grid ，它的大小为 m x n ，表示一个商店中物品的分布图。数组中的整数含义为：
- 0 表示无法穿越的一堵墙。
- 1 表示可以自由通过的一个空格子。
- 所有其他正整数表示该格子内的一样物品的价格。你可以自由经过这些格子。
从一个格子走到上下左右相邻格子花费 1 步。
同时给你一个整数数组 pricing 和 start ，其中 pricing = [low, high] 且 start = [row, col] ，表示你开始位置为 (row, col) ，同时你只对物品价格在 闭区间 [low, high] 之内的物品感兴趣。同时给你一个整数 k 。
你想知道给定范围 内 且 排名最高 的 k 件物品的 位置 。排名按照优先级从高到低的以下规则制定：
- 距离：定义为从 start 到一件物品的最短路径需要的步数（较近 距离的排名更高）。
- 价格：较低 价格的物品有更高优先级，但只考虑在给定范围之内的价格。
- 行坐标：较小 行坐标的有更高优先级。
- 列坐标：较小 列坐标的有更高优先级。
请你返回给定价格内排名最高的 k 件物品的坐标，将它们按照排名排序后返回。如果给定价格内少于 k 件物品，那么请将它们的坐标 全部 返回。
示例 1：
输入：grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3 输出：[[0,1],[1,1],[2,1]] 解释：起点为 (0,0) 。 价格范围为 [2,5] ，我们可以选择的物品坐标为 (0,1)，(1,1)，(2,1) 和 (2,2) 。 这些物品的排名为： - (0,1) 距离为 1 - (1,1) 距离为 2 - (2,1) 距离为 3 - (2,2) 距离为 4 所以，给定价格范围内排名最高的 3 件物品的坐标为 (0,1)，(1,1) 和 (2,1) 。
示例 2：
输入：grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2 输出：[[2,1],[1,2]] 解释：起点为 (2,3) 。 价格范围为 [2,3] ，我们可以选择的物品坐标为 (0,1)，(1,1)，(1,2) 和 (2,1) 。 这些物品的排名为： - (2,1) 距离为 2 ，价格为 2 - (1,2) 距离为 2 ，价格为 3 - (1,1) 距离为 3 - (0,1) 距离为 4 所以，给定价格范围内排名最高的 2 件物品的坐标为 (2,1) 和 (1,2) 。
示例 3：
输入：grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3 输出：[[2,1],[2,0]] 解释：起点为 (0,0) 。 价格范围为 [2,3] ，我们可以选择的物品坐标为 (2,0) 和 (2,1) 。 这些物品的排名为： - (2,1) 距离为 5 - (2,0) 距离为 6 所以，给定价格范围内排名最高的 2 件物品的坐标为 (2,1) 和 (2,0) 。 注意，k = 3 但给定价格范围内只有 2 件物品。
提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 105
- 1 <= m * n <= 105
- 0 <= grid[i][j] <= 105
- pricing.length == 2
- 2 <= low <= high <= 105
- start.length == 2
- 0 <= row <= m - 1
- 0 <= col <= n - 1
- grid[row][col] > 0
- 1 <= k <= m * n
思路：
很简单的一道题，。。。
// 错误的版本class Solution {public List<List<Integer>> highestRankedKItems(int[][] g, int[] p, int[] start, int k) {int n = g.length, m = g[0].length;List<List<Integer>> res = new ArrayList<List<Integer>>();Queue<int[]> q = new LinkedList<>();boolean[][] st = new boolean[n][m];st[start[0]][start[1]] = true;q.offer(new int[]{start[0], start[1], 0});int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};while (!q.isEmpty()) {int[] c = q.poll();int x = c[0], y = c[1], d = c[2];if (g[x][y] >= p[0] && g[x][y] <= p[1]) {List<Integer> t = new ArrayList<>();t.add(x);t.add(y);t.add(d);t.add(g[x][y]);res.add(t);}for (int i = 0; i < 4; i++) {int a = x + dx[i], b = y + dy[i];if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] == 0 || st[a][b])continue;st[a][b] = true;q.offer(new int[]{a, b, d + 1});}}Collections.sort(res, (o1, o2) -> {if (o1.get(2) != o2.get(2))return o1.get(2) - o2.get(2);else if (o1.get(3) != o2.get(3))return o1.get(3) - o2.get(3);else if (o1.get(0) != o2.get(0))return o1.get(0) - o2.get(0);elsereturn o1.get(1) - o2.get(1);});List<List<Integer>> ans = new ArrayList<>();for (int i = 0; i < Math.min(k, res.size()); i++) {List<Integer> t = new ArrayList<>();t.add(res.get(i).get(0));t.add(res.get(i).get(1));ans.add(t);}return ans;}}
:::tips 引用类型不能直接比较！！！！ :::
class Solution {public List<List<Integer>> highestRankedKItems(int[][] g, int[] p, int[] start, int k) {int n = g.length, m = g[0].length;List<List<Integer>> res = new ArrayList<>();Queue<int[]> q = new LinkedList<>();boolean[][] st = new boolean[n][m];st[start[0]][start[1]] = true;q.offer(new int[]{start[0], start[1], 0});int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};while (!q.isEmpty()) {int[] c = q.poll();int x = c[0], y = c[1], d = c[2];if (g[x][y] >= p[0] && g[x][y] <= p[1]) {List<Integer> t = new ArrayList<>();t.add(x);t.add(y);t.add(d);t.add(g[x][y]);res.add(t);}for (int i = 0; i < 4; i++) {int a = x + dx[i], b = y + dy[i];if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] == 0 || st[a][b])continue;st[a][b] = true;q.offer(new int[]{a, b, d + 1});}}Collections.sort(res, (o1, o2) -> {if (Integer.compare(o1.get(2), o2.get(2)) != 0) return o1.get(2) - o2.get(2);else if (Integer.compare(o1.get(3), o2.get(3)) != 0) return o1.get(3) - o2.get(3);else if (Integer.compare(o1.get(0), o2.get(0)) != 0) return o1.get(0) - o2.get(0);else return o1.get(1) - o2.get(1);});List<List<Integer>> ans = new ArrayList<>();for (int i = 0; i < Math.min(k, res.size()); i++) {List<Integer> t = new ArrayList<>();t.add(res.get(i).get(0));t.add(res.get(i).get(1));ans.add(t);}return ans;}}
5974. 分隔长廊的方案数
在一个图书馆的长廊里，有一些座位和装饰植物排成一列。给你一个下标从 0 开始，长度为 n 的字符串 corridor ，它包含字母 ‘S’ 和 ‘P’ ，其中每个 ‘S’ 表示一个座位，每个 ‘P’ 表示一株植物。
在下标 0 的左边和下标 n - 1 的右边 已经 分别各放了一个屏风。你还需要额外放置一些屏风。每一个位置 i - 1 和 i 之间（1 <= i <= n - 1），至多能放一个屏风。
请你将走廊用屏风划分为若干段，且每一段内都 恰好有两个座位 ，而每一段内植物的数目没有要求。可能有多种划分方案，如果两个方案中有任何一个屏风的位置不同，那么它们被视为 不同 方案。
请你返回划分走廊的方案数。由于答案可能很大，请你返回它对 109 + 7 取余 的结果。如果没有任何方案，请返回 0 。
示例 1：
输入：corridor = “SSPPSPS” 输出：3 解释：总共有 3 种不同分隔走廊的方案。 上图中黑色的竖线表示已经放置好的屏风。 上图每种方案中，每一段都恰好有 两个 座位。
示例 2：
输入：corridor = “PPSPSP” 输出：1 解释：只有 1 种分隔走廊的方案，就是不放置任何屏风。 放置任何的屏风都会导致有一段无法恰好有 2 个座位。
示例 3：
输入：corridor = “S” 输出：0 解释：没有任何方案，因为总是有一段无法恰好有 2 个座位。
提示：
- n == corridor.length
- 1 <= n <= 105
- corridor[i] 要么是 ‘S’ ，要么是 ‘P’ 。
思路：
顺序找即可，注意边界处理
class Solution {public int numberOfWays(String s) {int n = s.length(), P = (int)(1e9 + 7);int cnt = 0;for (int i = 0; i < n; i++) {if (s.charAt(i) == 'S')cnt++;}if (cnt % 2 != 0 || cnt == 0) return 0;int res = 1;List<Integer> list = new ArrayList<>();for (int i = 0; i < n; ) {cnt = 0;while (i < n && cnt < 2) {if (s.charAt(i) == 'S')cnt++;i++;}if (i == n) break;int t = 0;while (i < n && s.charAt(i) == 'P') {i++;t++;}if (i < n) t++;else break;// System.out.println(t);res = (int)(((long)res * t) % P);cnt = 0;}return res;}}
若有收获，就点个赞吧
0 人点赞
