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 。
可以证明不存在更小的答案。

示例 2：

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

提示：

• 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;
    }
}

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

难度中等19

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

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

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

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

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

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

示例 1：

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

示例 2：

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

提示：

• 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;
    }
}

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 。

示例 2：

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

示例 3：

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

提示：

• 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;
    }
}

2498. 青蛙过河 II

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

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

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

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

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

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

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

示例 1：

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

示例 2：

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

提示：

• 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;
    }
}

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 位乘客。
注意你不能跟其他乘客同一时间到达，所以你必须在第二位乘客之前到达。

示例 2：

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

提示：

• 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;
    }
}

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 。
还有别的子序列也无法从原数组中得到。

示例 2：

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

示例 3：

输入：rolls = [1,1,3,2,2,2,3,3], k = 4
输出：1
解释：子序列 [4] 无法从原数组中得到，所以我们返回 1 。
还有别的子序列也无法从原数组中得到，但 [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;
    }
}

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] 。

示例 2：

输入：nums = [2,3,1], k = 3
输出：1
解释：[3] 是唯一一个中位数等于 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;
    }
}

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 ，那么某些交易无法进行。

示例 2：

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

提示：

• 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);
    }
}

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 的方案。

示例 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 ，是所有方案中的最小代价。

示例 3：

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

提示：

• 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;
    }
}

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 。

示例 2：

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

提示：

• 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();
    }
}

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 。

示例 2：

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

提示：

• 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

简洁写法

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

方法二：用栈模拟（类似题目：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

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

735. 行星碰撞

难度中等394

给定一个整数数组 asteroids，表示在同一行的行星。

对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。

找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

示例 1：

输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

示例 2：

输入：asteroids = [8,-8]
输出：[]
解释：8 和 -8 碰撞后，两者都发生爆炸。

示例 3：

输入：asteroids = [10,2,-5]
输出：[10]
解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。

提示：

• 2 <= asteroids.length <= 104
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

题解：https://leetcode.cn/problems/asteroid-collision/solution/xingxing-by-jiang-hui-4-tepq/

根据题中的碰撞规则，只有运动方向为一个向右，一个向左的才会发生碰撞，我们通过栈来模拟这个过程。

若当前行星是大于0的，直接入栈。

若当前行星是小于0的，我们考虑在什么情况下会发生碰撞，并且判断当前行星是否存活

• 若栈为空，直接入栈

• 若栈顶元素小于0，表示栈内元素均向左，直接入栈

• 若栈顶元素大于0，我们需要和当前行星做判断：

  • 绝对值相等，均爆炸
  • 栈顶元素大于当前行星绝对值，当前行星爆炸
  • 栈顶元素小于当前行星绝对值，栈顶元素爆炸，然后接着判断下一个栈顶元素。

上述分析转化为：栈顶元素大于0时，只有栈顶元素小于当前元素的绝对值，或者栈为空，当前元素才会存活。

最终栈内元素即为最终答案

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        st = []
        for n in asteroids:
            if n > 0: # 大于0 直接入栈
                st.append(n)
            else:
                alive = True # 标记当前元素n是否存活
                # 当前元素存活 并且栈不是空 并且栈顶元素大于0
                while alive and st and st[-1] > 0:
                    # 只有栈顶元素小于当前元素的绝对值，才会存活
                    alive = st[-1] < abs(n)
                    # 栈顶元素爆炸（出栈）
                    if st[-1] <= abs(n):
                        st.pop()
                if alive:
                    st.append(n)
        return st

1717. 删除子字符串的最大得分

难度中等29

给你一个字符串 s 和两个整数 x 和 y 。你可以执行下面两种操作任意次。

• 删除子字符串 “ab” 并得到 x 分。
  • 比方说，从 "c**ab**xbae" 删除 ab ，得到 "cxbae" 。
• 删除子字符串"ba"并得到 y分。
  • 比方说，从 "cabx**ba**e" 删除 ba ，得到 "cabxe" 。

请返回对 s 字符串执行上面操作若干次能得到的最大得分。

示例 1：

输入：s = "cdbcbbaaabab", x = 4, y = 5
输出：19
解释：
- 删除 "cdbcbbaaabab" 中加粗的 "ba" ，得到 s = "cdbcbbaaab" ，加 5 分。
- 删除 "cdbcbbaaab" 中加粗的 "ab" ，得到 s = "cdbcbbaa" ，加 4 分。
- 删除 "cdbcbbaa" 中加粗的 "ba" ，得到 s = "cdbcba" ，加 5 分。
- 删除 "cdbcba" 中加粗的 "ba" ，得到 s = "cdbc" ，加 5 分。
总得分为 5 + 4 + 5 + 5 = 19 。

示例 2：

输入：s = "aabbaaxybbaabb", x = 5, y = 4
输出：20

提示：

• 1 <= s.length <= 105
• 1 <= x, y <= 104
• s 只包含小写英文字母。

class Solution {
    // 对于任意的只含a、b的子串s
    // 每次消除ab或者ba，会将子串中的a的数量和b的数量同时减一。
    // 结束状态一定是：子串为空，或者只剩下a，或者只剩下b。否则就可以继续消除获得更大的得分。

    // 因此，消除的次数是确定的。即一定是可以消除min(cnt_a, cnt_b)次。
    // 那么，我们优先选择消除分高的组合，在消除总次数一定的条件下，分高的组合消除的次数更多，就能获得更大的得分。

    // 会不会出现一种情况：当我们消除了一种分高的组合（如ab），会导致另一种分低的组合（如ba）消除次数变得很少，以至于消除的总次数变少？
    // 不可能。根据以上分析，结束状态一定是：子串为空，或者只剩下a，或者只剩下b。否则就可以继续消除获得更大的得分。消除的总次数一定是min(cnt_a, cnt_b)次。

    // 会不会出现一种情况：当我们在消除一种分高的组合（如ab）时，存在先消除另一个位置上的分高组合可以让分高的组合消除次数更多？
    // 不存在。因为每次消除的字符都是相邻的，上面这种情况只是消除的顺序不同而已，并不会让分高的组合消除次数更多。

    public int maximumGain(String s, int x, int y) {
        int cntmaxc = 0, cntminc = 0;
        int maxv = Math.max(x, y), minv = Math.min(x, y);
        char maxc = 'a', minc = 'b';
        if(y > x){
            maxc = 'b'; 
            minc = 'a';
        }

        int res = 0;
        for(char c : s.toCharArray()){
            if(c == maxc) cntmaxc++;
            else if(c == minc){
                if(cntmaxc > 0){
                    cntmaxc--;
                    res += maxv;
                }else  
                    cntminc++;
            }else{
                // 消除分低的组合
                res += Math.min(cntmaxc, cntminc) * minv;
                cntmaxc = cntminc = 0;
            }
        }
        // 消除分低的组合
        res += Math.min(cntmaxc, cntminc) * minv;
        cntmaxc = cntminc = 0;
        return res;    
    }
}

2317. 操作后的最大异或和

难度中等31

给你一个下标从 0 开始的整数数组 nums 。一次操作中，选择 任意 非负整数 x 和一个下标 i ，更新 nums[i] 为 nums[i] AND (nums[i] XOR x) 。

注意，AND 是逐位与运算，XOR 是逐位异或运算。

请你执行 任意次 更新操作，并返回 nums 中所有元素 最大 逐位异或和。

示例 1：

输入：nums = [3,2,4,6]
输出：7
解释：选择 x = 4 和 i = 3 进行操作，num[3] = 6 AND (6 XOR 4) = 6 AND 2 = 2 。
现在，nums = [3, 2, 4, 2] 且所有元素逐位异或得到 3 XOR 2 XOR 4 XOR 2 = 7 。
可知 7 是能得到的最大逐位异或和。
注意，其他操作可能也能得到逐位异或和 7 。

示例 2：

输入：nums = [1,2,3,9,2]
输出：11
解释：执行 0 次操作。
所有元素的逐位异或和为 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11 。
可知 11 是能得到的最大逐位异或和。

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 108

脑经急转弯

class Solution {
    /*

        nums[i]逐位异或任意非负整数 = 把nums[i]修改为任意非负整数

        nums[i]逐位与任意非负整数 = 把 nums[i] 的某些比特位的值，由1修改为0， 但不能由 0 修改为 1

        脑筋急转弯(贪心):
        我们注意到在一次操作中，选择 任意 非负整数 x 和一个下标 i ，更新 nums[i] 为 nums[i] AND (nums[i] XOR x)
        因为与nums[i]进行 与 操作只能将部分1置为0,而不能将0置为1
        因此我们问题转化为求将nums[i]中二进制位任意1转化为0后最大的异或值
        最优的解决方案为:相同一位只保留1个1,其余为0即可,这样异或后该位为1,最后的值必定最大
        那么原来至少有1个1才可以,只要原来该位有1个或以上的1就可以为1,想到或运算求该位最大的可能值
    */
    public int maximumXOR(int[] nums) {
        int res = 0;
        for(int num : nums){
            // 所有数字经过1轮的异或之后就可以得到该位最大可能的值
            res |= num;
        }
        return res;
    }
}

2227. 加密解密字符串

难度困难24

给你一个字符数组 keys ，由若干 互不相同 的字符组成。还有一个字符串数组 values ，内含若干长度为 2 的字符串。另给你一个字符串数组 dictionary ，包含解密后所有允许的原字符串。请你设计并实现一个支持加密及解密下标从 0 开始字符串的数据结构。

字符串 加密 按下述步骤进行：

1. 对字符串中的每个字符 c ，先从 keys 中找出满足 keys[i] == c 的下标 i 。
2. 在字符串中，用 values[i] 替换字符 c 。

字符串 解密 按下述步骤进行：

1. 将字符串每相邻 2 个字符划分为一个子字符串，对于每个子字符串 s ，找出满足 values[i] == s 的一个下标 i 。如果存在多个有效的 i ，从中选择 任意 一个。这意味着一个字符串解密可能得到多个解密字符串。
2. 在字符串中，用 keys[i] 替换 s 。

实现 Encrypter 类：

• Encrypter(char[] keys, String[] values, String[] dictionary) 用 keys、values 和 dictionary 初始化 Encrypter 类。
• String encrypt(String word1) 按上述加密过程完成对 word1 的加密，并返回加密后的字符串。
• int decrypt(String word2) 统计并返回可以由 word2 解密得到且出现在 dictionary 中的字符串数目。

示例：

输入：
["Encrypter", "encrypt", "decrypt"]
[[['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]], ["abcd"], ["eizfeiam"]]
输出：
[null, "eizfeiam", 2]

解释：
Encrypter encrypter = new Encrypter([['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]);
encrypter.encrypt("abcd"); // 返回 "eizfeiam"。 
                           // 'a' 映射为 "ei"，'b' 映射为 "zf"，'c' 映射为 "ei"，'d' 映射为 "am"。
encrypter.decrypt("eizfeiam"); // return 2. 
                              // "ei" 可以映射为 'a' 或 'c'，"zf" 映射为 'b'，"am" 映射为 'd'。 
                              // 因此，解密后可以得到的字符串是 "abad"，"cbad"，"abcd" 和 "cbcd"。 
                              // 其中 2 个字符串，"abad" 和 "abcd"，在 dictionary 中出现，所以答案是 2 。

提示：

• 1 <= keys.length == values.length <= 26
• values[i].length == 2
• 1 <= dictionary.length <= 100
• 1 <= dictionary[i].length <= 100
• 所有 keys[i] 和 dictionary[i] 互不相同
• 1 <= word1.length <= 2000
• 1 <= word2.length <= 200
• 所有 word1[i] 都出现在 keys 中
• word2.length 是偶数
• keys、values[i]、dictionary[i]、word1 和 word2 只含小写英文字母
• 至多调用 encrypt 和 decrypt 总计 200 次

题解：https://leetcode.cn/problems/encrypt-and-decrypt-strings/solution/by-endlesscheng-sm8h/

难度在于字节串解密操作。

加密：一个字符串A只对应一个加密后的字符串B

解密：一个字节串A解密后可能对应多个字符串B[]，并且满足这多个字符串加密后都对应同一个字符A。

因此可以得到这样的结论：

• 结论一：判断一个字符串B是否有A解密得到的方式 就是 判断B加密是不是A

给你一个字符串数组，题目的要求是 返回

1. 可以由word2解密得到的
2. 在dictionary数组中

的字符串数目。

注意这两者之间是与，并且的关系，那么是不是可以换一个表述顺序呢？

• 在dictionary数组中
• 可以由word2解密得到的 由结论一，就是加密之后等于word2的。

题目变成了

• 在dictionary数组中
• 加密之后等于word2的

因此，遍历dictionary数组，获取加密之后等于word2的字符串个数即可。

由于dictionary数组是预先给出的，是固定的，不是在解密方法中给出的，因此可以预处理。

class Encrypter {
    /**解密需要逆向思维，因为解密需要判断的字符串是固定的，
                直接加密看是否和需要解密串是否一致，即密码破解撞库方式。 */
    String[] map = new String[26];
    Map<String, Integer> cnt = new HashMap<>();
    
    public Encrypter(char[] keys, String[] values, String[] dictionary) {
        // 解密结果不唯一，但是加密结果是唯一的
        // 直接解密较为复杂，不妨逆向思考，即加密 dictionary 中的每个字符串，
        // 并用哈希表记录每个加密后的字符串的出现次数。
        // 这样每次调用 decrypt 时，返回哈希表中 word2 的出现次数即可。
        for(int i = 0; i < keys.length; i++){
            map[keys[i] - 'a'] = values[i];
        }
        for(String s : dictionary){
            String e = encrypt(s);
            cnt.put(e, cnt.getOrDefault(e, 0) + 1);
        }
    }
    
    public String encrypt(String word1) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < word1.length(); i++){
            String s = map[word1.charAt(i) - 'a'];
            if(s == null) return "";
            sb.append(s);
        }
        return sb.toString();
    }
    
    public int decrypt(String word2) {
        return cnt.getOrDefault(word2, 0);
    }
}

2306. 公司命名

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

给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下：

1. 从 ideas 中选择 2 个 不同 名字，称为 ideaA 和 ideaB 。
2. 交换 ideaA 和 ideaB 的首字母。
3. 如果得到的两个新名字 都 不在 ideas 中，那么 ideaA ideaB（串联 ideaA 和 ideaB ，中间用一个空格分隔）是一个有效的公司名字。
4. 否则，不是一个有效的名字。

返回 不同 且有效的公司名字的数目。

示例 1：

输入：ideas = ["coffee","donuts","time","toffee"]
输出：6
解释：下面列出一些有效的选择方案：
- ("coffee", "donuts")：对应的公司名字是 "doffee conuts" 。
- ("donuts", "coffee")：对应的公司名字是 "conuts doffee" 。
- ("donuts", "time")：对应的公司名字是 "tonuts dime" 。
- ("donuts", "toffee")：对应的公司名字是 "tonuts doffee" 。
- ("time", "donuts")：对应的公司名字是 "dime tonuts" 。
- ("toffee", "donuts")：对应的公司名字是 "doffee tonuts" 。
因此，总共有 6 个不同的公司名字。

下面列出一些无效的选择方案：
- ("coffee", "time")：在原数组中存在交换后形成的名字 "toffee" 。
- ("time", "toffee")：在原数组中存在交换后形成的两个名字。
- ("coffee", "toffee")：在原数组中存在交换后形成的两个名字。

示例 2：

输入：ideas = ["lack","back"]
输出：0
解释：不存在有效的选择方案。因此，返回 0 。

提示：

• 2 <= ideas.length <= 5 * 104
• 1 <= ideas[i].length <= 10
• ideas[i] 由小写英文字母组成
• ideas 中的所有字符串 互不相同

题解：Fomalhaut

分组枚举+互补匹配: ideas = ["coffee","donuts","time","toffee"]

我们要求ideas[i]首字母被其他ideas[j]替换后两个单词都不在ideas中

直接计算时间复杂度为:O(N^2)必定TLE

因此我们试想一下如何将它计算(统计)出来

以coffee为例,那些不可以与之交换的?toffee肯定不可以(组内互斥);time也不可以(组内存在前缀)

1.因此将ideas[i]的后缀进行分组,每一组的保留首字母有哪几个

2.我们知道同一组两单词之间不能交换(与组内单词相同);而且不同组的有相同首字母的的两个单词不能交换(等于本身)

3.学会一个思想很重要,我们不直接枚举ideas数组,而是枚举首字母的情况 定义:cnt[x][y]为组中不包含首字母x但是包含首字母y的组数

4.求解:枚举每个分组 -> 枚举不存在的首字母i∈[0-25] -> 枚举存在的首字母j∈[0-25] 假若该分组不存在首字母i与存在首字母j -> 说明可以匹配包含首字母x但是不包含首字母y的分组,数目为cnt[i][j]

将结果res进行累加即可

class Solution {
    /**
    洞察一："coffee", "donuts"  按照s[1:]分组
    洞察二："coffee", "toffee"  交换的两个字符串一定是不同组的
    洞察三：尝试枚举字母，i是不存在的，j是存在的
     */
    public long distinctNames(String[] ideas) {
        HashMap<String, Integer> group = new HashMap<>();
        for(String s : ideas){
            String t = s.substring(1);
            // 记录以t为后缀时，s[0]的首字母情况
            group.put(t, group.getOrDefault(t, 0) | 1 << (s.charAt(0) - 'a'));
        } 

        long ans = 0L;
        // 定义:cnt[x][y]为组中包含首字母x但是不包含首字母y的**组数** 
        int[][] cnt = new int[26][26];
        for(int mask : group.values()){
            for(int i = 0; i < 26; i++){
                // i 不在里面时，枚举j
                if((mask >> i & 1) == 0){
                    for(int j = 0; j < 26; j++){
                        if((mask >> j & 1) > 0) cnt[i][j]++;
                    }
                }else{
                    // i在mask中，找有i无j的情况，记录答案
                    for(int j = 0; j < 26; j++){
                        if((mask >> j & 1) == 0){
                            ans += cnt[i][j];
                        }
                    }
                }
            }
        }
        return ans * 2; // 在组合时，名字是可以互换的
    }
}

交换的条件是两个不同的分组AB，对于两个字母ij，A有i无j，B有j无i，可以进行交换。但是在算cnt的途中，这个交换算了两次，因为A可以去找B换，B也可以找A换。

这就相当于用有i无j和有j无i对两个分组进行了一个关联，而最终的方案数就是所有这种关联的个数。

有点类似于n个点两两连接，查边的个数。

所以如果整个遍历完再进行累加，每条边算了两次，要除以2。如果一次遍历的路上进行累加，由于只查了指向当前点前面的边，所以每条边只算了一次，所以直接就是边的个数。

最后是因为一次交换可以产生两个答案，对交换的方案数再乘2就好了

2242. 节点序列的最大得分

难度困难27

给你一个 n 个节点的 无向图 ，节点编号为 0 到 n - 1 。

给你一个下标从 0 开始的整数数组 scores ，其中 scores[i] 是第 i 个节点的分数。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] ，表示节点 ai 和 bi 之间有一条 无向 边。

一个合法的节点序列如果满足以下条件，我们称它是 合法的 ：

• 序列中每 相邻 节点之间有边相连。
• 序列中没有节点出现超过一次。

节点序列的分数定义为序列中节点分数之 和 。

请你返回一个长度为 4 的合法节点序列的最大分数。如果不存在这样的序列，请你返回 -1 。

示例 1：

输入：scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
输出：24
解释：上图为输入的图，节点序列为 [0,1,2,3] 。
节点序列的分数为 5 + 2 + 9 + 8 = 24 。
观察可知，没有其他节点序列得分和超过 24 。
注意节点序列 [3,1,2,0] 和 [1,0,2,3] 也是合法的，且分数为 24 。
序列 [0,3,2,4] 不是合法的，因为没有边连接节点 0 和 3 。

示例 2：

输入：scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]]
输出：-1
解释：上图为输入的图。
没有长度为 4 的合法序列，所以我们返回 -1 。

提示：文章来源地址https://www.toymoban.com/news/detail-417996.html

• n == scores.length
• 4 <= n <= 5 * 104
• 1 <= scores[i] <= 108
• 0 <= edges.length <= 5 * 104
• edges[i].length == 2
• 0 <= ai, bi <= n - 1
• ai != bi
• 不会有重边。

class Solution {
    // 简化问题可以帮我们找到思路：如果序列长度为3，要如何枚举？
    // 只要三个节点的话，我们可以枚举端点，也可以枚举中间点，还可以枚举边，哪一种是最方便的？
    // 枚举中间点是最方便的，算出与其相邻的分数最大的两个点即可
    // 要求序列长度为4？回到原问题
    // 设序列为 a-x-y-b，枚举edges中的每条边，作为序列正中间的那条边，即 x-y
    // 我们需要把与 x 相邻的点中，分数最大且不同于 y 和 b 的点作为a;
    //            把与 y 相邻的点中，分数最大且不同于 x 和a的点作为 b
    // 与 x 相邻的点中，由于只需要与 y 和 b 不一样，我们仅需要保留分数最大的三个点，a 必定在这三个点中。
    // 剩下要做的，就是在枚举 edges 前，预处理出这三个点。
    public int maximumScore(int[] scores, int[][] edges) {
        int n = scores.length;
        List<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for(int[] e : edges){
            int x = e[0], y = e[1];
            g[x].add(new int[]{scores[y], y});
            g[y].add(new int[]{scores[x], x});
        }
        
        for(int i = 0; i < n; i++){
            if(g[i].size() > 3){
                // 保留与 x 相邻的点中 分数最大的三个点（排序）
                g[i].sort((a, b) -> (b[0] - a[0]));
                g[i] = new ArrayList<>(g[i].subList(0, 3));
            }
        }
        int ans = -1;
        for(int[] e : edges){ // 枚举中间的边 x-y
            int x = e[0], y = e[1];
            for(int[] p : g[x]){
                int a = p[1];
                for(int[] q : g[y]){
                    int b = q[1];
                    if(a != y && b != x && a != b){
                        ans = Math.max(ans, p[0] + scores[x] + scores[y] + q[0]);
                    }
                }
            }
        }
        return ans;
    }
}

到了这里，关于7.思维题（0x3f：从周赛中学算法 2022下）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！