LeetCode周赛291，最后5分钟连A两题，不放弃才皆有可能

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

今天是周一，我们照惯例来聊聊LeetCode周赛。这场比赛的赞助商是FunPlus，我查了一下，这是一家游戏开发公司。

这场比赛的整体难度不算很大，但是我个人的体验可以说是非常刺激。给大家看一下我的提交记录：

第三题错了9次，一直到比赛结束前一分钟才通过。

而这中间，我若干次想要放弃，若干次怀疑人生，也有若干次怀疑自己的认知。尤其是比赛时看着通过的人数飞速地上涨，从一百多涨到两百多，再到八百多，最后到一千多。我陷入了深深的自我怀疑……

当我最终看到绿色的通过时，没有兴奋，没有激动，而是想起了近十年前的那个晚上。

那天晚上我和队友们争夺仅有的几个去往区域赛的入场券，一直到比赛结束前十分钟，我都颗粒无收。我在放弃和再挣扎之间反复摇摆，一直到最后的几分钟，偶然的灵光一闪，我找到了bug，连A了两道题，逆袭了比赛，拿到了名额。

从那一刻起，我就有种感觉，其实比赛的意义其实不在于结果如何，而在于比赛中让你痛苦让你难受，让你怀疑人生的各种难受的磨砺。痛苦并不是必须的，但你的成长路上一定少不了这些。

好了，感慨就说到这里，让我们来看题吧。

移除指定数字得到的最大结果

给你一个表示某个正整数的字符串 number 和一个字符 digit 。

从 number 中 恰好 移除 一个 等于 digit 的字符后，找出并返回按 十进制 表示 最大 的结果字符串。生成的测试用例满足 digit 在 number 中出现至少一次。

解答

题意非常直观，删掉一个字符，使得剩下的数字最大。又看了一眼范围，最大的长度是100，虽然超过了所有整数类型，但并不是非常大，Python可以支持任意长度的整数，100位是小case。

果断Python水过。

class Solution:
    def removeDigit(self, number: str, digit: str) -> str:
        ret = 0
        for i in range(len(number)):
            if number[i] == digit[0]:
                ret = max(ret, int(number[:i] + number[i+1:]))
        return str(ret)
        

赛后想了一下，其实用C++也不麻烦，在长度一定的时候，字符串比大小和数字比大小其实是一样的。都是从最高位开始比较，所以根本没有必要转成整形进行对比，直接比较字符串即可。

class Solution {
public:
    string removeDigit(string number, char digit) {
        int n = number.length();
        string ret = "";
        for (int i = 0; i < n; i++) {
            if (number[i] == digit) {
                string cur = number;
                cur.erase(cur.begin() + i);
                if (ret == "" || cur > ret) ret = cur;
            }
        }
        return ret;
    }
};

必须拿起的最小连续卡牌数

给你一个整数数组 cards ，其中 cards[i] 表示第 i 张卡牌的 值 。如果两张卡牌的值相同，则认为这一对卡牌 匹配 。

返回你必须拿起的最小连续卡牌数，以使在拿起的卡牌中有一对匹配的卡牌。如果无法得到一对匹配的卡牌，返回 -1 。

解答

刷过LeetCode的同学估计看到这道题应该觉得很熟悉，它其实是LeetCode第一题two sum的变种。在two sum中我们是要找到两个数，它们的和等于target。在这题里，我们也是要找两个数，只不过这两个数需要相等，并且间距最小。

two sum当中我们使用了一个技巧，这个技巧也没有名字，我个人将它命名为迭代存储。

先来思考一个问题，假设某一个数出现了很多次，其中有一个位置的下标是i，i之前还有j,k,l等位置。对于下标i位置而言，从它开始找一个最小的连续的匹配，那么它需要关心k和l或者更靠前的位置吗？

显然不需要，因为很明显，j距离更近，它只需要考虑最近的匹配即可。有了这个前提，我们就可以使用map来存储每一个值在迭代中最近一次出现的位置，也就是我们关心的位置。对着迭代的进行，map中值的位置一直在发生变化，后面的新的值不断覆盖前面旧的。

理解了这个思路，很容易写出代码：

class Solution {
public:
    int minimumCardPickup(vector<int>& cards) {
        map<int, int> mp;
        int n = cards.size();
        int ret = n+1;
        for (int i = 0; i < n; i++) {
            int c = cards[i];
            // c出现在map中，说明c在i之前出现过，计算匹配的间隔
            if (mp.count(c)) {
                ret = min(ret, i - mp[c] + 1);
            }
            mp[c] = i;
        }
        return ret == n+1 ? -1 : ret;
    }
};

含最多 K 个可整除元素的子数组

给你一个整数数组 nums 和两个整数 k 和 p ，找出并返回满足要求的不同的子数组数，要求子数组中最多 k 个可被 p 整除的元素。

如果满足下述条件之一，则认为数组 nums1 和 nums2 是 不同 数组：

• 两数组长度 不同 ，或者
• 存在 至少 一个下标 i 满足 nums1[i] != nums2[i] 。

子数组 定义为：数组中的连续元素组成的一个 非空 序列。

解答

这题算是给我坑到了姥姥家，但这并不怪出题人，是我自己不小心。

一开始的时候我不小心把题目看错了，看漏了子数组必须连续的条件，如果不看错题意的话，其实思路并不算难想。因为题目给的范围很小，我们要找到所有被p整除数量小于k的子数组，我们大可以枚举出所有的子数组来进行一个一个地判断。

唯一的问题是，子数组之间可能存在重复，我们要进行去重。我比赛的时候就是卡在了这里，因为数组去重是一个非常麻烦的操作，针对这个问题并没有什么太好的解法。所以我思前想后也不知道该怎么对这些数组进行去重。

而正解的方案很简单，简单到有些夸张，就是利用set的唯一性来去重。我为什么没有想到呢？因为我把set的概念搞混了，在Python当中，set、map这类对象的key是不能是list、dict这类可变对象的。但C++当中并没有这样的限制，set的key也可以是vector。

为了解决这个问题，我尝试了很多邪道。比如说vector计算hash值，以及将当中的元素转成string进行去重等等。最终的结果是hash的方法会出现hash碰撞，我也不知道这个数据不大为什么会碰撞。转成string的方案不出意外地超时了，所以我当时陷入了深深的绝望。

思维陷入了误区，自然就无论如何绞尽脑汁也无法解决了，最后也是在比赛结束之前，决定尝试一下利用Python的set对tuple进行去重，本来是打算碰碰运气，没想到真的过了。更没想到这就是正解……

在计算区间里能整除p的数量时，我还用了前缀和，其实是没有必要的。

Python版本：

class Solution:
    def countDistinct(self, nums: List[int], k: int, p: int) -> int:
        n = len(nums)
        sums = [0 for _ in range(n+1)]
        for i in range(n):
            c = nums[i]
            if c % p == 0:
                sums[i+1] = sums[i] + 1
            else:
                sums[i+1] = sums[i]
                
        ret = 0
        
        st = set()
        for i in range(n):
            for j in range(i+1, n+1):
                cur = sums[j] - sums[i]
                if cur > k:
                    continue
                tup = tuple(nums[i: j])
                if tup in st:
                    continue
                ret += 1
                st.add(tup)
        return ret

C++版本：

class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        int n = nums.size();
        
        set<vector<int>> st;
        for (int i = 0; i < n; i++) {
            vector<int> vt;
            int cnt = 0;
            for (int j = i; j < n; j++) {
                cnt += (nums[j] % p == 0);
                if (cnt > k) break;
                vt.push_back(nums[j]);
                st.insert(vt);
            }
        }
        return st.size();
    }
};

字符串的总引力

字符串的 引力 定义为：字符串中 不同 字符的数量。

• 例如，"abbca" 的引力为 3 ，因为其中有 3 个不同字符 'a'、'b' 和 'c' 。

给你一个字符串 s ，返回 其所有子字符串的总引力 。

子字符串 定义为：字符串中的一个连续字符序列。

解答

这题乍看起来很难，因为给定的字符串长度很大，有1e5，我刚拿到手也没有想到好的解法。通过分析数据范围，可以基本确定，肯定不可能暴力枚举所有的区间来计算的，复杂度一定撑不住。

排除了暴力枚举之后，我就基本上确定了，这题需要使用贡献法。

所谓贡献法，即计算每一个元素对于答案的贡献，最终将所有的贡献值累加得到答案的方法。在这题当中，我们可以认为字符在子串中出现的次数去重是它的贡献。

对于下标为i的字符来说，它出现的子串数量是很好计算的。我们可以用排列组合的方法，在i及i以前选择区间的开头，在i及以后选择区间的结尾，那么包含下标i的子串的数量就是(i + 1) * (n - i)。

但这里有一个问题，在这个子串当中，我们怎么保证下标i的这个字符只有一个呢？如果出现多个，我们怎么计算呢？

这个问题才是本题的关键，解出了这个问题，基本上也就得到答案了。

想要回答这个问题，需要我们进一步分析。首先，我们规定，在一个子串当中，如果有某个字符出现了超过1次，那么我们认为这个贡献是最靠前的字符贡献的。比如abaac，当中的a出现了3次，我们认为a的贡献是下标0的a带来的，后面的两个a都不算。

我们假设某个字符出现的其中两次位置分别是i和j，其中i < j。基于我们刚才的假设，如果某一个区间同时包含i和j，那么这个贡献算是i的，只有不包含i并且包含j的子串的贡献才是j的。由于j是除了i之外最靠前的位置，所以即使j之后也有同样的字符，也不影响贡献归属于j。

那么，对于j来说它能做出的贡献有多少区间呢？

很简单(j - i) * (n - j)，所以对于每一个字符来说，我们只需要记录下它之前一次出现的位置，套用一下上面的公式进行计算之后累加即可。

class Solution {
public:
    long long appealSum(string s) {
        vector<int> chs(30, -1);
        long long ret = 0;
        
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            int p = s[i] - 'a';
            // -1 表示没出现过，由于下标从0开始，不需要特判
            long long left = i - chs[p];
            long long right = n - i;
            
            ret += left * right;
            // 更新字符p的位置
            chs[p] = i;
        }
        return ret;
    }
};

关于这次的周赛就聊这么多，最后10分钟A掉两题，一方面觉得挽尊成功没有太丢脸之外，另外一方面也觉得挺可惜的。毕竟冷静下来10分钟能AC，说明了题目并不算难，没有拿到好的名次还是挺可惜的。

但想想一方面运气也是实力的体现，另外一方面能有个机会再次锻炼一下心态，其实也挺好的。

之前听到有一些小伙伴说连第四题都没看就去吃饭了，希望这一篇文章能够给你们带来一些鼓励吧。

喜欢本文的话不要忘记三连~