7.思维题（0x3f：从周赛中学算法-2022）_灵茶山艾府

来自0x3f【从周赛中学算法 - 2022 年周赛题目总结（下篇）】：https://leetcode.cn/circle/discuss/WR1MJP/
【【灵茶山艾府】2022 年周赛题目总结（上篇）】https://leetcode.cn/circle/discuss/G0n5iY/

包含贪心、脑筋急转弯等，挑选一些比较有趣的题目。

注：常见于周赛第二题（约占 21%）、第三题（约占 26%）和第四题（约占 17%）。

【灵茶山艾府】2022 年周赛题目总结（上篇）

灵神-从周赛中学算法（思维题）

2022下

2383. 赢得比赛需要的最少训练时长

难度简单78

你正在参加一场比赛，给你两个 正 整数 initialEnergy 和 initialExperience 分别表示你的初始精力和初始经验。

另给你两个下标从 0 开始的整数数组 energy 和 experience，长度均为 n 。

你将会 依次 对上 n 个对手。第 i 个对手的精力和经验分别用 energy[i] 和 experience[i] 表示。当你对上对手时，需要在经验和精力上都 严格 超过对手才能击败他们，然后在可能的情况下继续对上下一个对手。

击败第 i 个对手会使你的经验 增加 experience[i]，但会将你的精力 减少 energy[i] 。

在开始比赛前，你可以训练几个小时。每训练一个小时，你可以选择将增加经验增加 1 或者 将精力增加 1 。

返回击败全部 n 个对手需要训练的 最少 小时数目。

示例 1：

输入：initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]
输出：8
解释：在 6 小时训练后，你可以将精力提高到 11 ，并且再训练 2 个小时将经验提高到 5 。
按以下顺序与对手比赛：
- 你的精力与经验都超过第 0 个对手，所以获胜。
  精力变为：11 - 1 = 10 ，经验变为：5 + 2 = 7 。
- 你的精力与经验都超过第 1 个对手，所以获胜。
  精力变为：10 - 4 = 6 ，经验变为：7 + 6 = 13 。
- 你的精力与经验都超过第 2 个对手，所以获胜。
  精力变为：6 - 3 = 3 ，经验变为：13 + 3 = 16 。
- 你的精力与经验都超过第 3 个对手，所以获胜。
  精力变为：3 - 2 = 1 ，经验变为：16 + 1 = 17 。
在比赛前进行了 8 小时训练，所以返回 8 。
可以证明不存在更小的答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

示例 2：

输入：initialEnergy = 2, initialExperience = 4, energy = [1], experience = [3]
输出：0
解释：你不需要额外的精力和经验就可以赢得比赛，所以返回 0 。
1
2
3

提示：

• n == energy.length == experience.length
• 1 <= n <= 100
• 1 <= initialEnergy, initialExperience, energy[i], experience[i] <= 100

class Solution {
    public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {
        int cost = 0;
        int n = energy.length;
        for(int i = 0; i < n; i++){
            int en = energy[i], ex = experience[i];
            // 注意是严格大于等于
            if(initialEnergy <= en){
                cost += en - initialEnergy + 1;
                initialEnergy = en + 1;
            }
            if(initialExperience <= ex){
                cost += ex - initialExperience + 1;
                initialExperience = ex + 1;
            }
            initialEnergy -= en;
            initialExperience += ex;
        }
        return cost;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

2419. 按位与最大的最长子数组

难度中等19

给你一个长度为 n 的整数数组 nums 。

考虑 nums 中进行 **按位与（bitwise AND）**运算得到的值 最大 的 非空 子数组。

• 换句话说，令 k 是 nums 任意 子数组执行按位与运算所能得到的最大值。那么，只需要考虑那些执行一次按位与运算后等于 k 的子数组。

返回满足要求的 最长 子数组的长度。

数组的按位与就是对数组中的所有数字进行按位与运算。

子数组 是数组中的一个连续元素序列。

示例 1：

输入：nums = [1,2,3,3,2,2]
输出：2
解释：
子数组按位与运算的最大值是 3 。
能得到此结果的最长子数组是 [3,3]，所以返回 2 。
1
2
3
4
5

示例 2：

输入：nums = [1,2,3,4]
输出：1
解释：
子数组按位与运算的最大值是 4 。 
能得到此结果的最长子数组是 [4]，所以返回 1 。
1
2
3
4
5

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 106

题解：根据按位与的性质：都为1才为1，因此按位与最大值一定是数组的最大值，且答案就是数组中最大值连续出现的次数

class Solution {
    // 由于 AND 不会让数字变大，那么最大值就是数组的最大值。
    public int longestSubarray(int[] nums) {
        int max = 0;
        int n = nums.length;
        for(int num : nums) max = Math.max(max, num);
        int res = 0;
        int left = 0, right = 0;
        while(right < n){
            if(nums[right] != max){
                res = Math.max(res, right - left);
                left = right+1;
            }
            right++;
        }
        res = Math.max(res, right - left);
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

2337. 移动片段得到字符串

难度中等32收藏分享切换为英文接收动态反馈

给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 'L'、'R' 和 '_' 组成，其中：

• 字符 'L' 和 'R' 表示片段，其中片段 'L' 只有在其左侧直接存在一个 空位 时才能向 左 移动，而片段 'R' 只有在其右侧直接存在一个 空位 时才能向 右 移动。
• 字符 '_' 表示可以被 任意 'L' 或 'R' 片段占据的空位。

如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。

示例 1：

输入：start = "_L__R__R_", target = "L______RR"
输出：true
解释：可以从字符串 start 获得 target ，需要进行下面的移动：
- 将第一个片段向左移动一步，字符串现在变为 "L___R__R_" 。
- 将最后一个片段向右移动一步，字符串现在变为 "L___R___R" 。
- 将第二个片段向右移动散步，字符串现在变为 "L______RR" 。
可以从字符串 start 得到 target ，所以返回 true 。
1
2
3
4
5
6
7

示例 2：

输入：start = "R_L_", target = "__LR"
输出：false
解释：字符串 start 中的 'R' 片段可以向右移动一步得到 "_RL_" 。
但是，在这一步之后，不存在可以移动的片段，所以无法从字符串 start 得到 target 。
1
2
3
4

示例 3：

输入：start = "_R", target = "R_"
输出：false
解释：字符串 start 中的片段只能向右移动，所以无法从字符串 start 得到 target 。
1
2
3

提示：

• n == start.length == target.length
• 1 <= n <= 105
• start 和 target 由字符 'L'、'R' 和 '_' 组成

题解：0X3F：https://leetcode.cn/problems/move-pieces-to-obtain-a-string/solution/nao-jin-ji-zhuan-wan-pythonjavacgo-by-en-9sqt/

class Solution {
    // 首先，无论怎么移动，由于 L 和 R 无法互相穿过对方，那么去掉 _ 后的剩余字符应该是相同的，否则返回 false。
    // 然后用双指针遍历 start[i] 和 target[j] , 分类讨论
    //      如果当前字符为 L 且 i < j, 那么这个L由于无法向右移动，返回false
    //      如果当前字符为 R 且 i > j, 那么这个R由于无法向右移动，返回false
    public boolean canChange(String start, String target) {
        if(!start.replaceAll("_","").equals(target.replaceAll("_", ""))) return false;
        for(int i = 0, j = 0; i < start.length(); i++){
            if(start.charAt(i) == '_') continue;
            while(target.charAt(j) == '_') j++;
            // 若i=j，则说明一定匹配（因为在for循环上面的判断中保证了相对顺序）
            // 若L：则它不能向右移动 i < j
            // 若R：则它不能向左移动 j < i
            //if (start.charAt(i) != target.charAt(j)) return false;
            //if (start.charAt(i) == 'L' && i < j) return false;
            //if (start.charAt(i) == 'R' && i > j) return false;
            if(i != j && (start.charAt(i) == 'L') == (i < j)) return false;
            ++j;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2498. 青蛙过河 II

难度中等21收藏分享切换为英文接收动态反馈

给你一个下标从 0 开始的整数数组 stones ，数组中的元素 严格递增 ，表示一条河中石头的位置。

一只青蛙一开始在第一块石头上，它想到达最后一块石头，然后回到第一块石头。同时每块石头 至多 到达 一次。

一次跳跃的 长度 是青蛙跳跃前和跳跃后所在两块石头之间的距离。

• 更正式的，如果青蛙从 stones[i] 跳到 stones[j] ，跳跃的长度为 |stones[i] - stones[j]| 。

一条路径的 代价 是这条路径里的 最大跳跃长度 。

请你返回这只青蛙的 最小代价 。

示例 1：

输入：stones = [0,2,5,6,7]
输出：5
解释：上图展示了一条最优路径。
这条路径的代价是 5 ，是这条路径中的最大跳跃长度。
无法得到一条代价小于 5 的路径，我们返回 5 。
1
2
3
4
5

示例 2：

输入：stones = [0,3,9]
输出：9
解释：
青蛙可以直接跳到最后一块石头，然后跳回第一块石头。
在这条路径中，每次跳跃长度都是 9 。所以路径代价是 max(9, 9) = 9 。
这是可行路径中的最小代价。
1
2
3
4
5
6

提示：

• 2 <= stones.length <= 105
• 0 <= stones[i] <= 109
• stones[0] == 0
• stones 中的元素严格递增。

题解：https://leetcode.cn/problems/frog-jump-ii/solution/dengj-by-nreyog-ytmr/

class Solution {
    // 问题转换：题意等价于两只青蛙从0开始跳，跳到最后一块石头，且两只青蛙跳的路径没有交集
    // ==> 那么一只青蛙跳1、3、5、7...，另一只青蛙跳2、4、6、8...就好了，这样代价一定最小
    public int maxJump(int[] s) {
        int n = s.length;
        // 
        int max = Math.max(s[0], s[1]);
        for(int i = 0; i+2 < n; i += 2){
            max = Math.max(max, s[i+2] - s[i]);
        }
        for(int i = 1; i+2 < n; i += 2){
            max = Math.max(max, s[i+2] - s[i]);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

2332. 坐上公交的最晚时间

难度中等32

给你一个下标从 0 开始长度为 n 的整数数组 buses ，其中 buses[i] 表示第 i 辆公交车的出发时间。同时给你一个下标从 0 开始长度为 m 的整数数组 passengers ，其中 passengers[j] 表示第 j 位乘客的到达时间。所有公交车出发的时间互不相同，所有乘客到达的时间也互不相同。

给你一个整数 capacity ，表示每辆公交车 最多 能容纳的乘客数目。

每位乘客都会搭乘下一辆有座位的公交车。如果你在 y 时刻到达，公交在 x 时刻出发，满足 y <= x 且公交没有满，那么你可以搭乘这一辆公交。最早 到达的乘客优先上车。

返回你可以搭乘公交车的最晚到达公交站时间。你 不能 跟别的乘客同时刻到达。

**注意：**数组 buses 和 passengers 不一定是有序的。

示例 1：

输入：buses = [10,20], passengers = [2,17,18,19], capacity = 2
输出：16
解释：
第 1 辆公交车载着第 1 位乘客。
第 2 辆公交车载着你和第 2 位乘客。
注意你不能跟其他乘客同一时间到达，所以你必须在第二位乘客之前到达。
1
2
3
4
5
6

示例 2：

输入：buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2
输出：20
解释：
第 1 辆公交车载着第 4 位乘客。
第 2 辆公交车载着第 6 位和第 2 位乘客。
第 3 辆公交车载着第 1 位乘客和你。
1
2
3
4
5
6

提示：

• n == buses.length
• m == passengers.length
• 1 <= n, m, capacity <= 105
• 2 <= buses[i], passengers[i] <= 109
• buses 中的元素 互不相同 。
• passengers 中的元素 互不相同 。

题解：https://leetcode.cn/problems/the-latest-time-to-catch-a-bus/solution/pai-xu-by-endlesscheng-h9w9/

排序后，用双指针模拟乘客上车的过程：遍历公交车，找哪些乘客可以上车（先来先上车）。

模拟结束后：

• 如果最后一班公交还有空位，我们可以在发车时到达公交站，如果此刻有人，我们可以顺着他往前找到没人到达的时刻；
• 如果最后一班公交没有空位，我们可以找到上一个上车的乘客，顺着他往前找到一个没人到达的时刻。

这里可以「插队」的理由是，如果一个乘客上了车，那么他前面的乘客肯定也上了车（因为先来先上车）。

class Solution {
    // 上帝视角：你可以插队
    // 找到最后一个上车的人，如果他上车了 那么他前面的人一定也上车了
    // 顺着最后一个人往前找，找到一个空位，就是答案
    public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
        Arrays.sort(passengers);
        Arrays.sort(buses);
        int j = 0, c = 0; // j 表示乘客，以下模拟乘客是否能上车
        for(int t : buses){ // 每辆公交车的发车时间
            c = capacity;// 容量还有，乘客还没遍历完，乘客到达时间不晚于发车时间
            while(c > 0 && j < passengers.length && passengers[j] <= t){
                c -= 1;
                j += 1; // 上车
            }
        }
        j -= 1; // 最后一个上车的乘客
        //模拟过后从最后往前找
        //如果最后一个公交车容量满了，就从最后一位乘客往前找到空的时间点插队，
        //  在这之前的任意一个时间节点都是可以的，因为最后一位乘客都有机会上车，你比他先来的话肯定也能上车
        //如果最后一个公交车没满，在最后一个公交车到达的时间到就可以了
        int ans = c == 0 ? passengers[j] : buses[buses.length - 1];
        // （因为不能 跟别的乘客同时刻到达）顺着最后一个人往前找，找到一个空位，就是答案
        while(j >= 0 && passengers[j--] == ans) 
            ans--; //没有空位就往前找，有空位就插队
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

---

2350. 不可能得到的最短骰子序列

难度困难36

给你一个长度为 n 的整数数组 rolls 和一个整数 k 。你扔一个 k 面的骰子 n 次，骰子的每个面分别是 1 到 k ，其中第 i 次扔得到的数字是 rolls[i] 。

请你返回 无法 从 rolls 中得到的 最短 骰子子序列的长度。

扔一个 k 面的骰子 len 次得到的是一个长度为 len 的 骰子子序列 。

注意 ，子序列只需要保持在原数组中的顺序，不需要连续。

示例 1：

输入：rolls = [4,2,1,2,3,3,2,4,1], k = 4
输出：3
解释：所有长度为 1 的骰子子序列 [1] ，[2] ，[3] ，[4] 都可以从原数组中得到。
所有长度为 2 的骰子子序列 [1, 1] ，[1, 2] ，... ，[4, 4] 都可以从原数组中得到。
子序列 [1, 4, 2] 无法从原数组中得到，所以我们返回 3 。
还有别的子序列也无法从原数组中得到。
1
2
3
4
5
6

示例 2：

输入：rolls = [1,1,2,2], k = 2
输出：2
解释：所有长度为 1 的子序列 [1] ，[2] 都可以从原数组中得到。
子序列 [2, 1] 无法从原数组中得到，所以我们返回 2 。
还有别的子序列也无法从原数组中得到，但 [2, 1] 是最短的子序列。
1
2
3
4
5

示例 3：

输入：rolls = [1,1,3,2,2,2,3,3], k = 4
输出：1
解释：子序列 [4] 无法从原数组中得到，所以我们返回 1 。
还有别的子序列也无法从原数组中得到，但 [4] 是最短的子序列。
1
2
3
4

提示：

• n == rolls.length
• 1 <= n <= 105
• 1 <= rolls[i] <= k <= 105

脑经急转弯 + 贪心

题解：https://leetcode.cn/problems/shortest-impossible-sequence-of-rolls/solution/by-endlesscheng-diiq/

（贪心）不断去找 1～k（作为一段），m段，答案就是 m +1

• 当1～k都找到即找到了一段，m段，长度为m的子序列就都可以从原数组中得到

实现方法：

• 方法1. 用set实现好理解，找到 1～k就结束，再清空set重新找
• 方法2.只要初始化一次空间，用mark数组标记1～k个元素在哪一段，用left该段还剩下没找到的元素个数，当left等于0，即都找到，ans才+1

class Solution {
    /* 10^5 : 不是DP就是贪心
        取最后一个尚未出现的数字

        不断去找 1~k 的数字，如果都找到，就取最后一个找到的数字，
        然后把找到的数字清空，重复该过程
        答案就是 1~k 段的个数 + 1
    */
    // 方法1
    public int shortestSequence(int[] rolls, int k) {
        int res = 1;
        Set<Integer> set = new HashSet<>();
        for(int r : rolls){
            set.add(r);
            if(set.size() == k){
                set = new HashSet<>();
                res++;
            }
        }
        return res;
    }
    // 方法2
    public int shortestSequence(int[] rolls, int k) {
        int[] mark = new int[k+1];// mark[v] 标记 v 属于哪个子段
        int res = 1, left = k;// left 剩余未找到的数字
        for(int v : rolls){
            if(mark[v] < res){
                mark[v] = res; // 如果v还没有标记，就标记v属于哪个子段
                if(--left == 0){// left == 0 说明又找到了一个段
                    left = k;
                    res++;
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

---

2488. 统计中位数为 K 的子数组

难度困难163收藏分享切换为英文接收动态反馈

给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的 不同 整数组成。另给你一个正整数 k 。

统计并返回 nums 中的 中位数 等于 k 的非空子数组的数目。

注意：

• 数组的中位数是 按递增 顺序排列后位于 中间 的那个元素，如果数组长度为偶数，则中位数是位于中间靠 左 的那个元素。
  • 例如，[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。
• 子数组是数组中的一个连续部分。

示例 1：

输入：nums = [3,2,1,4,5], k = 4
输出：3
解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。
1
2
3

示例 2：

输入：nums = [2,3,1], k = 3
输出：1
解释：[3] 是唯一一个中位数等于 3 的子数组。
1
2
3

提示：

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i], k <= n
• nums 中的整数互不相同

class Solution {
    /*
        # 展开成一个数学式子
        # 中位数 ==> (奇数长度) 小于 k 的数的个数 = 大于 k 的数的个数       
        # ==>    k左侧小于k的个数 + k右侧小于k的个数 = k左侧大于k的个数 + k右侧大于k的个数
        # ==>    + k左侧小于k的个数 - k左侧大于k的个数 = + k右侧大于k的个数 - k右侧小于k的个数
        # 用哈希表将k左边出现的数的次数统计下来，再k的右侧遍历 从左到右遍历找个数
        # 偶数长度怎么办？ 小于+1 = 大于
        # 左侧小于 + 右侧小于+1 = 左侧大于 + 右侧大于
        # + 左侧小于 - 左侧大于+1 = + 右侧大于 - 右侧小于
    */
    public int countSubarrays(int[] nums, int k) {
        int pos = 0, n = nums.length;
        // 找到数组中k所在的下标pos
        while(nums[pos] != k) ++pos;
        int cnt = 0, sum = 0;
        Map<Integer,Integer> left = new HashMap<>();
         // i=pos 的时候 x 是 0，直接记到 cnt 中，这样下面不是大于 k 就是小于 k
        left.put(0, 1);
        // 用哈希表记录下idx左侧 大于小于k 出现的情况(类似前缀和)
        for(int i = pos-1; i>= 0; i--){
            if(nums[i] < k) sum--;
            else sum++;
            left.put(sum, left.getOrDefault(sum, 0) + 1);
        }
        cnt += left.get(0); // i=pos 的时候 x 是 0，直接加到答案中，这样下面不是大于 k 就是小于 k
        cnt += left.getOrDefault(1,0); // i=pos 的时候 偶数子数组的情况
        sum = 0;
        // 从k+1开始从左往右遍历，与左侧出现次数进行匹配
        // 使得sum + x = 0（奇数长度） sum + x = 1（偶数长度）
        for(int i = pos + 1; i < n; i++){
            if(nums[i] < k) sum--;
            else sum++;
            cnt += left.getOrDefault(-1 * sum, 0); // sum + x = 0
            cnt += left.getOrDefault(1 - sum, 0); // sum + x == 1
        }
        return cnt;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

---

2412. 完成所有交易的初始最少钱数

难度困难21收藏分享切换为英文接收动态反馈

给你一个下标从 0 开始的二维整数数组 transactions，其中transactions[i] = [costi, cashbacki] 。

数组描述了若干笔交易。其中每笔交易必须以 某种顺序 恰好完成一次。在任意一个时刻，你有一定数目的钱 money ，为了完成交易 i ，money >= costi 这个条件必须为真。执行交易后，你的钱数 money 变成 money - costi + cashbacki 。

请你返回 任意一种 交易顺序下，你都能完成所有交易的最少钱数 money 是多少。

示例 1：

输入：transactions = [[2,1],[5,0],[4,2]]
输出：10
解释：
刚开始 money = 10 ，交易可以以任意顺序进行。
可以证明如果 money < 10 ，那么某些交易无法进行。
1
2
3
4
5

示例 2：

输入：transactions = [[3,0],[0,3]]
输出：3
解释：
- 如果交易执行的顺序是 [[3,0],[0,3]] ，完成所有交易需要的最少钱数是 3 。
- 如果交易执行的顺序是 [[0,3],[3,0]] ，完成所有交易需要的最少钱数是 0 。
所以，刚开始钱数为 3 ，任意顺序下交易都可以全部完成。
1
2
3
4
5
6

提示：

• 1 <= transactions.length <= 105
• transactions[i].length == 2
• 0 <= costi, cashbacki <= 109

题解：https://leetcode.cn/problems/minimum-money-required-before-transactions/solution/by-endlesscheng-lvym/

1. 对于所有 cost <= cashback 的交易，只要我的初始money 为 max(cost), 那么无论什么顺序我都能完成所有交易。因为 max(cost) - any(cost) + 一个更大的 cashback 会变的更大，足以启动任何一个剩余的交易。以此类推。并且因为max(cost)为最大值，也足够我启动最大的cost交易。
2. 对于所有 cost > cashback的交易, 我至少需要亏掉 sum (cost - cashback) 的money，因此，对于cost > cashback的交易，我初始的钱为 cost1 - cashback1 + cost2 - cashback2 + cost3 - cashback3 + ..... + costi - cashbacki。 但是怎么能保证我的启动资金一定够？？？？ 。我需要 sum(cost - cashback) + max(cashback)。对于任意一次交易，因为： cost - cashback + max(cashback) >= cost ！！！！ 然后我进行了此次交易后，我的总钱数又剪掉了 cost - cashback. 但是这个 max(cashback) 一直留在了钱包里，因此，可以保证我完成所有的交易。
3. 综上：最后结果为 sum(cost - cashback) + max(max(cashback), max(cost)). 其中 sum(cost - cashback) 为所有 cost > cashback 项。max(cashback）为cost > cashback的项， max(cost) 为cost <= cashback的项

class Solution {
    // 亏的交易，所有亏的交易，且cashback最大的那笔还没有拿到时，就是亏最多的时候（要求最大的cashback）
    // 赚的交易，cost最多的那笔，就是需要钱最多的时候（要求最大的cost）
    public long minimumMoney(int[][] transactions) {
        long maxCashBack = 0, maxCost = 0, sum = 0;
        for(int[] t : transactions){
            int cost = t[0], cashbask = t[1];
            // 对于所有 cost > cashback的交易, 我至少需要亏掉 sum (cost - cashback) 的money
            // 对于任意一次交易，因为： cost - cashback + max(cashback) >= cost ！！！！ 
            // 然后我进行了此次交易后，我的总钱数又剪掉了 cost - cashback. 
            // 但是这个 max(cashback) 一直留在了钱包里，因此，可以保证我完成所有的交易。
            if(cost > cashbask){ //这笔交易可以发生在最后一笔亏钱时,亏的交易
                sum += cost - cashbask;
                maxCashBack = Math.max(maxCashBack, cashbask);
            // 对于所有 cost <= cashback 的交易，只要我的初始money 为 max(cost), 那么无论什么顺序我都能完成所有交易。
            }else{ //赚的交易
                maxCost = Math.max(maxCost, cost);
            }
        }
        return sum + Math.max(maxCashBack, maxCost);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2499. 让数组不相等的最小总代价

难度困难22

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都为 n 。

每次操作中，你可以选择交换 nums1 中任意两个下标处的值。操作的 开销 为两个下标的 和 。

你的目标是对于所有的 0 <= i <= n - 1 ，都满足 nums1[i] != nums2[i] ，你可以进行 任意次 操作，请你返回达到这个目标的 最小 总代价。

请你返回让 nums1 和 nums2 满足上述条件的 最小总代价 ，如果无法达成目标，返回 -1 。

示例 1：

输入：nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5]
输出：10
解释：
实现目标的其中一种方法为：
- 交换下标为 0 和 3 的两个值，代价为 0 + 3 = 3 。现在 nums1 = [4,2,3,1,5] 。
- 交换下标为 1 和 2 的两个值，代价为 1 + 2 = 3 。现在 nums1 = [4,3,2,1,5] 。
- 交换下标为 0 和 4 的两个值，代价为 0 + 4 = 4 。现在 nums1 = [5,3,2,1,4] 。
最后，对于每个下标 i ，都有 nums1[i] != nums2[i] 。总代价为 10 。
还有别的交换值的方法，但是无法得到代价和小于 10 的方案。
1
2
3
4
5
6
7
8
9

示例 2：

输入：nums1 = [2,2,2,1,3], nums2 = [1,2,2,3,3]
输出：10
解释：
实现目标的一种方法为：
- 交换下标为 2 和 3 的两个值，代价为 2 + 3 = 5 。现在 nums1 = [2,2,1,2,3] 。
- 交换下标为 1 和 4 的两个值，代价为 1 + 4 = 5 。现在 nums1 = [2,3,1,2,2] 。
总代价为 10 ，是所有方案中的最小代价。
1
2
3
4
5
6
7

示例 3：

输入：nums1 = [1,2,2], nums2 = [1,2,2]
输出：-1
解释：
不管怎么操作，都无法满足题目要求。
所以返回 -1 。
1
2
3
4
5

提示：

• n == nums1.length == nums2.length
• 1 <= n <= 105
• 1 <= nums1[i], nums2[i] <= n

题解：https://leetcode.cn/problems/minimum-total-cost-to-make-arrays-unequal/solution/li-yong-nums10-tan-xin-zhao-bu-deng-yu-z-amvw/

class Solution {
    /**
    分类讨论：看众数的频率是否超过一半（众数： 出现次数最多的数）
    出现次数相等的 x = nums1[i] = nums2[i]
    1. x 的众数的出现次数 <= 这些数字的个数 / 2
        1.1 这些数字的个数是奇数  两两匹配                   下标之和
        1.2 这些数字的个数是偶数                            下标之和
                这些数字的种类至少为3，必然可以跟nums[0]交换
    2. x 的众数的出现次数 > 这些数字的个数 / 2                 下标之和
        场外求助（需要和多出来的x进行交换）                     下标之和
        找nums1[j] != nums2[j] 的树，且它两都不等于众数（多出来的数是众数）
        直到 x 的众数的出现次数 <= 这些数字的个数 / 2
    */
    public long minimumTotalCost(int[] nums1, int[] nums2) {
        long ans = 0l;
        // swapCnt相等数字个数；modecnt众数出现次数；mode众数
        int swapCnt = 0, modeCnt = 0, mode = 0, n = nums1.length;
        int[] cnt = new int[n+1];
        for(int i = 0; i < n; i++){
            int x = nums1[i];
            if(x == nums2[i]){ // 如果同一下标两元素相等，记录到cnt数组中
                ans += i;
                swapCnt++;
                cnt[x]++;
                if(cnt[x] > modeCnt){
                    modeCnt = cnt[x];
                    mode = x; // 找到最大众数
                }
            }
        }
        // x 的众数的出现次数 > 这些数字的个数 / 2
        // 场外求助：直到x的众数出现次数 <= 这些数字的个数/2
        for(int i = 0; i < n && modeCnt * 2 > swapCnt; i++){
            int x = nums1[i], y = nums2[i];
            if(x != y && x != mode && y != mode){
                ans += i;
                ++swapCnt;
            }
        }
        // 场外求助后仍不满足x 的众数的出现次数 <= 这些数字的个数 / 2 , return -1
        return modeCnt * 2 > swapCnt ? -1 : ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

2386. 找出数组的第 K 大和

难度困难62

给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。

数组的 第 k 大和 定义为：可以获得的第 k 个 最大 子序列和（子序列和允许出现重复）

返回数组的 第 k 大和 。

子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。

**注意：**空子序列的和视作 0 。

示例 1：

输入：nums = [2,4,-2], k = 5
输出：2
解释：所有可能获得的子序列和列出如下，按递减顺序排列：
- 6、4、4、2、2、0、0、-2
数组的第 5 大和是 2 。
1
2
3
4
5

示例 2：

输入：nums = [1,-2,3,4,-10,12], k = 16
输出：10
解释：数组的第 16 大和是 10 。
1
2
3

提示：

• n == nums.length
• 1 <= n <= 105
• -109 <= nums[i] <= 109
• 1 <= k <= min(2000, 2n)

https://leetcode.cn/problems/find-the-k-sum-of-an-array/solution/zhuan-huan-dui-by-endlesscheng-8yiq/

1. 从最大的子序列和来考虑，那么这个序列和就是所有正数的和 sum。
2. 怎么找到第二大的子序列和？从最大的子序列和中减去最小的正数或加上最大的负数。
3. 为了统一操作，将负数取反，然后排序，每次取最小的数，得到的就是最小的正数或最大的负数。sum 中减去它，就可以得到下一个更小的子序列和。
4. 被减去的数们实际上也是组成了一个子序列。按照生成子序列的模板，就是依次对每个数，考虑选择它，还是不选择它。

这样分析之后，就可以回答大家的两个问题：

• Q：怎么保证 pq 的顶就是答案？A：因为是用当前值最大和减去最小值，所以得到的一定是下一个略小的最大和。
• Q：保留和不保留 nums[i-1] 是不是写反了？A：是否保留指的是在被 减去 的子序列中是否保留此数。所以，如果不保留的话，反而是要加回来，因为它不该被从 sum 里减去。

class Solution {
    /**
    1. 怎么处理负数 ？ 能不能找到一个负数的等价形式
    2. 从和最大的子序列开始考虑：所有非负数的和 sum
    3. 若要继续找后续较小的子序列的和，等价于从sum里面减去一个子序列的和
            减去一个子序列的和：正数就直接减，负数就直接加（将nums所有数取绝对值，这样可以统一成从sum中减去某些数）
    4. 目标是从 sum 里面选择 k-1 个最小的子序列和
    5. 用最大堆来维护第k个最大子序列和

     */
    public long kSum(int[] nums, int k) {
        long sum = 0l; // 获取数组非负数的和（正数就直接加，负数就直接减）
        for(int i = 0; i < nums.length; i++){
            if(nums[i] >= 0) sum += nums[i];
            else nums[i] = -nums[i];
        }
        Arrays.sort(nums);
        // 构造一个最大堆(堆顶是第k个最小的子序列的和)
        PriorityQueue<Pair<Long, Integer>> pq = new PriorityQueue<>((a, b) -> Long.compare(b.getKey(), a.getKey()));
        pq.offer(new Pair<>(sum, 0)); // 初始状态(数组非负数和，第)
        while(--k > 0){ // 选k-1次
            Pair<Long, Integer> p = pq.poll();
            Long s = p.getKey();
            Integer i = p.getValue();
            if(i < nums.length){
                pq.offer(new Pair<>(s - nums[i], i + 1)); // 保留 nums[i-1]
                if (i > 0){
                    pq.offer(new Pair<>(s - nums[i] + nums[i - 1], i + 1)); // 不保留 nums[i-1]，把之前减去的加回来
                }
            }
        }
        return pq.peek().getKey();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

2022上

2211. 统计道路上的碰撞次数

难度中等30

在一条无限长的公路上有 n 辆汽车正在行驶。汽车按从左到右的顺序按从 0 到 n - 1 编号，每辆车都在一个 独特的 位置。

给你一个下标从 0 开始的字符串 directions ，长度为 n 。directions[i] 可以是 'L'、'R' 或 'S' 分别表示第 i 辆车是向 左 、向 右 或者 停留 在当前位置。每辆车移动时 速度相同 。

碰撞次数可以按下述方式计算：

• 当两辆移动方向 相反 的车相撞时，碰撞次数加 2 。
• 当一辆移动的车和一辆静止的车相撞时，碰撞次数加 1 。

碰撞发生后，涉及的车辆将无法继续移动并停留在碰撞位置。除此之外，汽车不能改变它们的状态或移动方向。

返回在这条道路上发生的 碰撞总次数 。

示例 1：

输入：directions = "RLRSLL"
输出：5
解释：
将会在道路上发生的碰撞列出如下：
- 车 0 和车 1 会互相碰撞。由于它们按相反方向移动，碰撞数量变为 0 + 2 = 2 。
- 车 2 和车 3 会互相碰撞。由于 3 是静止的，碰撞数量变为 2 + 1 = 3 。
- 车 3 和车 4 会互相碰撞。由于 3 是静止的，碰撞数量变为 3 + 1 = 4 。
- 车 4 和车 5 会互相碰撞。在车 4 和车 3 碰撞之后，车 4 会待在碰撞位置，接着和车 5 碰撞。碰撞数量变为 4 + 1 = 5 。
因此，将会在道路上发生的碰撞总次数是 5 。
1
2
3
4
5
6
7
8
9

示例 2：

输入：directions = "LLRR"
输出：0
解释：
不存在会发生碰撞的车辆。因此，将会在道路上发生的碰撞总次数是 0 。
1
2
3
4

提示：

• 1 <= directions.length <= 105
• directions[i] 的值为 'L'、'R' 或 'S'

显然，左侧的 ’L’ 和右侧的 ’R’ 不会被撞停；而中间的车辆都会最终停止，因此统计中间的、一开始没有停止的车辆数（即不是 ’S’ 的车辆数）即可。

• 去掉往左右两边开的车之后，剩下非停止的车必然会碰撞。

class Solution:
    def countCollisions(self, directions: str) -> int:
        l, r = 0, len(directions)-1
        while l < r and ord(directions[l]) == ord('L'):
            l += 1
        while l < r and ord(directions[r]) == ord('R'):
            r -= 1
        ans = 0
        if l >= r: return ans
        for i in range(l, r+1):
            if ord(directions[i]) != ord('S'):
                ans += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

简洁写法

class Solution:
    def countCollisions(self, s: str) -> int:
        s = s.lstrip('L')  # 前缀向左的车不会发生碰撞
        s = s.rstrip('R')  # 后缀向右的车不会发生碰撞
        return len(s) - s.count('S')  # 剩下非停止的车必然会碰撞
1
2
3
4
5

方法二：用栈模拟（类似题目：LC 735. 行星碰撞）

https://leetcode.cn/problems/count-collisions-on-a-road/solution/da-an-hui-bei-zhuang-ting-de-che-liang-s-yyfl/

用栈来做，会遇到三种情况：

1.静止的’S’：如果前面有往右的，就不断让前面的’R’撞击当前的’S’，每次加1分。最后加一个’S’

2.往右的’R’：直接加入

3.往左的’L’:三种情况：

（1）前面没有，就不用管

（2）前面是静止的，那就撞一次1分的

（3）前面是往右的，那就撞一次2分的，变成静止的’S’，然后用新的’S’去和前面的’R’继续撞1分的

class Solution:
    def countCollisions(self, directions: str) -> int:
        ans = 0
        st = []
        for n in directions:
            if not st:
                st.append(n)
            
            # 静止的话，就看前面有没有往右的
            elif n == 'S':
                while st and st[-1] == 'R':
                    ans += 1
                    st.pop()
                st.append(n)
            
            # 往右的直接添加
            elif n == 'R':
                st.append(n)
            
            # 往左的话，如果左边没有就不用管
            # 如果左边有，就看看左边是哪种，如果是静止的话就只撞一次
            #           如果是往右的话，撞完会变成S，此时还要继续判断左边还有没有往右边的，有的话用S撞击R
            else:
                if not st:
                    continue
                elif st[-1] == 'S':
                    ans += 1
                elif st[-1] == 'R':
                    ans += 2
                    st.pop()
                    while st and st[-1] == 'R':
                        ans += 1
                        st.pop()
                    st.append('S')
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

理解了这个思路可以尝试下1717. 删除子字符串的最大得分，应该会理解得深刻些