【力扣周赛】第 357 场周赛（⭐反悔贪心）

竞赛链接

Q1：6925. 故障键盘

https://leetcode.cn/problems/faulty-keyboard/

提示：
1 <= s.length <= 100
s 由小写英文字母组成
s[0] != 'i'

解法1——直接模拟

遇到 ‘i’ 翻转已有的字符串，其它字符直接添加即可。

class Solution {public String finalString(String s) {StringBuilder ans = new StringBuilder();for (char ch: s.toCharArray()) {if (ch != 'i') ans.append(ch);else ans.reverse();}return ans.toString();}
}

解法2——双端队列

用一个变量维护当前翻转了几次，来决定新来的字符添加在开头还是结尾。

class Solution {public String finalString(String s) {int f = 0;Deque<Character> dq = new ArrayDeque<>();for (char ch: s.toCharArray()) {if (ch == 'i') f++;else {if (f % 2 == 0) dq.offerLast(ch);else dq.offerFirst(ch);}}StringBuilder ans = new StringBuilder();for (char ch: dq) ans.append(ch);if (f % 2 == 1) ans.reverse();return ans.toString();}
}

Q2：6953. 判断是否能拆分数组（贪心）

https://leetcode.cn/problems/check-if-it-is-possible-to-split-array/

提示：
1 <= n == nums.length <= 100
1 <= nums[i] <= 100
1 <= m <= 200

class Solution {public boolean canSplitArray(List<Integer> nums, int m) {int n = nums.size();if (n == 1 || n == 2) return true;for (int i = 0; i < n - 1; ++i) {if (nums.get(i) + nums.get(i + 1) >= m) return true;}return false;}
}

Q3：2812. 找出最安全路径⭐

https://leetcode.cn/problems/find-the-safest-path-in-a-grid/

提示：
1 <= grid.length == n <= 400
grid[i].length == n
grid[i][j] 为 0 或 1
grid 至少存在一个小偷

解法1——多源BFS+瓶颈路模型？

第一遍 bfs 求出各个位置的安全系数。
第二遍 bfs，将各个位置的安全系数更新为从终点开始的路径上的较小值。

class Solution {int[] dx = new int[]{-1, 0, 1, 0}, dy = new int[]{0, -1, 0, 1};public int maximumSafenessFactor(List<List<Integer>> grid) {int n = grid.size();if (grid.get(0).get(0) == 1 || grid.get(n - 1).get(n - 1) == 1) return 0;int[][] g = new int[n][n], safe = new int[n][n];Queue<int[]> q = new LinkedList<>();// 第一遍多源bfs 求出各个位置的安全系数for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {if (grid.get(i).get(j) == 1) {g[i][j] = 1;q.offer(new int[]{i, j});}}}while (!q.isEmpty()) {int sz = q.size();for (int i = 0; i < sz; ++i) {int[] cur = q.poll();int x = cur[0], y = cur[1];for (int k = 0; k < 4; ++k) {int nx = x + dx[k], ny = y + dy[k];if (nx >= 0 && ny >= 0 && nx < n && ny < n && g[nx][ny] == 0) {q.offer(new int[]{nx, ny});g[nx][ny] = g[x][y] + 1;}}}}// 第二遍bfs 从终点出发，求出各个路径的最小安全系数q.offer(new int[]{n - 1, n - 1});safe[n - 1][n - 1] = g[n - 1][n - 1];while (!q.isEmpty()) {int[] cur = q.poll();int x = cur[0], y = cur[1];for (int k = 0; k < 4; ++k) {int nx = x + dx[k], ny = y + dy[k];if (nx >= 0 && ny >= 0 && nx < n && ny < n) {int nsafe = Math.min(g[nx][ny], safe[x][y]);if (nsafe > safe[nx][ny]) {safe[nx][ny] = nsafe;q.offer(new int[]{nx, ny});}}}}return safe[0][0] - 1;}
}

解法2——多源BFS + 倒序枚举答案 + 并查集（TODO）

https://leetcode.cn/problems/find-the-safest-path-in-a-grid/solutions/2375565/jie-jin-on2-de-zuo-fa-duo-yuan-bfsdao-xu-r5um/

在这里插入代码片

Q4：2813. 子序列最大优雅度⭐⭐⭐⭐⭐（反悔贪心）

https://leetcode.cn/problems/maximum-elegance-of-a-k-length-subsequence/

提示：
1 <= items.length == n <= 10^5
items[i].length == 2
items[i][0] == profiti
items[i][1] == categoryi
1 <= profiti <= 10^9
1 <= categoryi <= n
1 <= k <= n

思路——反悔贪心

https://leetcode.cn/problems/maximum-elegance-of-a-k-length-subsequence/solutions/2375128/fan-hui-tan-xin-pythonjavacgo-by-endless-v2w1/

代码

核心的思想是：x + y^2，枚举 y^2的值，并使得 x 在该枚举值下的值最大，就得到了该枚举值下的最大值。比较得到的所有的最大值就是最终结果了。

class Solution {public long findMaximumElegance(int[][] items, int k) {// 把利润从大到小排序Arrays.sort(items, (a, b) -> b[0] - a[0]);long ans = 0, totalProfit = 0;Set<Integer> vis = new HashSet<>();Deque<Integer> duplicate = new ArrayDeque<>();for (int i = 0; i < items.length; ++i) {int profit = items[i][0], category = items[i][1];if (i < k) {totalProfit += profit;if (!vis.add(category)) {// 如果已经有这个类别了，就把当前的放在栈顶duplicate.push(profit);}} else if (!duplicate.isEmpty() && vis.add(category)) {// 如果当前栈不为空，且当前种类没有出现过totalProfit += profit - duplicate.pop();    // 修改利润}ans = Math.max(ans, totalProfit + (long) vis.size() * vis.size());}return ans;}
}

相似题目列表

做完之后感觉这两个题目更相似一些，但是和反悔贪心关系不是那么大。

LCP 30. 魔塔游戏（堆+贪心）

https://leetcode.cn/problems/p0NxJO/description/

提示：
1 <= nums.length <= 10^5
-10^5 <= nums[i] <= 10^5

先检查是否有答案存在。

如果有答案存在，就将已经枚举到的负值放入堆中，每次 s <= 0 时，就取出最小的那个负数移动到末尾即可。

class Solution {public int magicTower(int[] nums) {if (Arrays.stream(nums).sum() < 0) return -1;int ans = 0;// pq中存放目前遇到的负数PriorityQueue<Integer> pq = new PriorityQueue<>();long s = 1;for (int x: nums) {s += x;if (x < 0) pq.offer(x);while (s <= 0) {// 每次把最小的移动到最后面去s -= pq.poll();ans++;}}return ans;}
}

871. 最低加油次数（堆+贪心）

https://leetcode.cn/problems/minimum-number-of-refueling-stops/

提示：
1 <= target, startFuel <= 10^9
0 <= stations.length <= 500
1 <= positioni < positioni+1 < target
1 <= fueli < 10^9

用堆维护目前可以加的油，但是先不加，等到走不动了再一个个加。

class Solution {public int minRefuelStops(int target, int startFuel, int[][] stations) {if (startFuel >= target) return 0;Arrays.sort(stations, (x, y) -> x[0] - y[0]);   // 按照位置排序PriorityQueue<Integer> pq = new PriorityQueue<Integer>((x, y) -> y - x);int p = startFuel, ans = 0;for (int i = 0; i < stations.length; ++i) {while (p < stations[i][0] && !pq.isEmpty()) {p += pq.poll();ans++;}if (p < stations[i][0]) break;if (p >= target) return ans;pq.offer(stations[i][1]);}while (p < target && !pq.isEmpty()) {p += pq.poll();ans++;}return p < target? -1: ans;}
}

成绩记录

T3 借助了一些些外力。

上小分。