竞赛链接

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 借助了一些些外力。

上小分。