LeetCode周赛332，让我看看多少人大意翻车在了第二题？

作者 | 梁唐

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

大家好，我是梁唐。

今天是周一，我们来看看昨天的LeetCode周赛。

这次是LeetCode周赛第332场，由浩鲸科技科技赞助，前300名的小伙伴可以获得内推资格。如果我没记错，最近几个月都没有出现过这么多内推的机会了。

有找工作需求的小伙伴不妨多关注关注LeetCode周赛。

这次比赛的题目质量很高，尤其是第二题，很多大佬都表示不小心翻车了。

找出数组的串联值

给你一个下标从 0 开始的整数数组 nums 。

现定义两个数字的 串联 是由这两个数值串联起来形成的新数字。

• 例如，15 和 49 的串联是 1549 。

nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空：

• 如果 nums 中存在不止一个数字，分别选中 nums 中的第一个元素和最后一个元素，将二者串联得到的值加到 nums 的 串联值 上，然后从 nums 中删除第一个和最后一个元素。
• 如果仅存在一个元素，则将该元素的值加到 nums 的串联值上，然后删除这个元素。

返回执行完所有操作后 nums 的串联值。

题解

字符串模拟题，我们从左右两端获取字符串拼接在一起再转成数字求和。

这里我偷懒使用了Python，C++当然也可以，可能会稍微麻烦一些。

class Solution:
    def findTheArrayConcVal(self, nums: List[int]) -> int:
        l, r = 0, len(nums)-1
        ret = 0
        while l < r:
            ret += int(str(nums[l]) + str(nums[r]))
            l += 1
            r -= 1
            
        if l == r:
            ret += nums[l]
            
        return ret

统计公平数对的数目

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

• 0 <= i < j < n，且
• lower <= nums[i] + nums[j] <= upper

题解

这题很阴险，我们很容易想到，对于每一个数nums[i]来说，它能构成的答案数量为它右侧取值在[lower - nums[i], upper-nums[i]]区间内的元素数量。

但比较麻烦的是，本题的数据范围比较大，一共有

个元素，元素的范围也达到了

。使得我们没办法直接使用树状数组之类的数据结构，我当时想到了先离散化再套树状数组，但是这也有新的问题，维护的是每个元素出现的次数，但求解的时候，用到的是lower-nums[i]和upper - nums[i]，所以离散化的时候需要将它们也考虑进去。

我个人感觉这种解法是可行的，但不应该出现在周赛的第二题，难度也不应该是Medium。所以从这个角度出发，我感觉本题一定还有更优的解法。

trick藏在哪里呢？藏在题目的第一个条件里0 <= i < j < n。这个条件限制了i和j的大小关系，意味着对于一个(i, j)的配对，对答案的贡献只有一。也就是说不论i和j的大小关系如何，只要它们的配对符合第二条就可以被计入答案。进而可以想到，数组中元素的顺序并不重要，不论元素的顺序如何，都不会影响答案数量。

既然元素的顺序不重要，那么我们就可以对数组进行排序了，一旦元素有序，我们就可以通过二分法非常快地找到范围。为了保证不重复计入答案，我们枚举i，寻找下标大于i的j，使得

。我们只需要使用STL自带的lower_bound和upper_bound就能快速找出满足的下标范围。

class Solution {
public:
    
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        long long ret = 0;
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < nums.size(); i++) {
            // 由于数组中元素可能出现重复，寻找右侧边界需要使用upper_bound
            auto r = upper_bound(nums.begin()+i+1, nums.end(), upper-nums[i]);
            auto l = lower_bound(nums.begin()+i+1, nums.end(), lower-nums[i]);
            ret += r - l;
        }
        
        return ret;
    }
};

本题的代码很简单，只有十几行，但是当中涉及到大量的思考和推导，想要理清头绪还是有一点难度。

子字符串异或查询

给你一个 二进制字符串 s 和一个整数数组 queries ，其中 queries[i] = [firsti, secondi] 。

对于第 i 个查询，找到 s 的 最短子字符串 ，它对应的 十进制值 val 与 firsti 按位异或 得到 secondi ，换言之，val ^ firsti == secondi 。

第 i 个查询的答案是子字符串 [lefti, righti] 的两个端点（下标从 0 开始），如果不存在这样的子字符串，则答案为 [-1, -1] 。如果有多个答案，请你选择 lefti 最小的一个。

请你返回一个数组 ans ，其中 ans[i] = [lefti, righti] 是第 i 个查询的答案。

子字符串 是一个字符串中一段连续非空的字符序列。

题解

这题的trick和技巧也比较多，我们一一来说。

首先是异或操作的可逆性，我们要找一个val，使得val ^ firsti == secondi。由于异或操作是可逆的，我们在等式两边同时再对firsti取异或，那么就得到val = val ^ firsti ^ firsti = secondi ^ firsti。这样对于每一个query，我们都可以直接知道要找的val是多少。

其次是在线转离线，这是一个空间换时间的做法。本题的数据范围很大，尤其是query的数量有

。如果对于每一个查询，我们都需要

的复杂度获得结果。那么在本题这么大的规模下一定是会超时的。查询的次数和每次查询的复杂度这两点我们都没有很好的办法优化，唯一能用的就是在线转离线，也就是通过预处理把所有能够得到的结果全部存下来，构造答案的时候从已经存储的结果当中找。这种技巧在竞赛中被称为在线转离线。

由于int的范围是32位，所以我们只需要维护出字符串s中长度从1到32的所有子串对应的10进制整数即可，我们可以使用32个map来分别存储不同长度下每个10进制数最早出现的下标。

这些都存储下来之后，对于每一个查询q，我们只需要遍历一下这些map寻找一下是否出现即可。

class Solution {
public:
    vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {
        vector<vector<int>> ret;
        int n = s.length();
        
        map<int, int> mps[33];
        
        // 枚举子串长度
        for (int i = 1; i < 32; i++) {
            // 枚举子串起始位置
            for (int j = 0; j < n-i+1; j++) {
                int cur = 0;
                // 计算子串对应的10进制数
                for (int k = j; k < j+i; k++) {
                    cur <<= 1;
                    cur += (s[k] == '1');
                }
                if (!mps[i].count(cur)) mps[i][cur] = j;
            }
        }
        
        for (auto &vt: queries) {
            int q = vt[1] ^ vt[0];
            int l = -1, r = -1;
            // 从长度1开始遍历，也可以算出q对应的二进制长度
            for (int i = 1; i < 32; i++) {
                if (mps[i].count(q)) {
                    l = mps[i][q];
                    r = mps[i][q] + i - 1;
                    break;
                }
            }
            ret.push_back({l, r});
        }
        return ret;
    }
};

最少得分子序列

给你两个字符串 s 和 t 。

你可以从字符串 t 中删除任意数目的字符。

如果没有从字符串 t 中删除字符，那么得分为 0 ，否则：

• 令 left 为删除字符中的最小下标。
• 令 right 为删除字符中的最大下标。

字符串的得分为 right - left + 1 。

请你返回使 t 成为 s 子序列的最小得分。

一个字符串的 子序列 是从原字符串中删除一些字符后（也可以一个也不删除），剩余字符不改变顺序得到的字符串。（比方说 "ace" 是 "abcde" 的子序列，但是 "aec" 不是）。

题解

我们要在字符串t中寻找长度最小的区间，使得删除之后t能成为s的子串。

我们假设删除的区间是[l, r]，那么必然有t[: l]和t[r+1:]都是s的子串。我们确定了l之后，就可以确定能够容纳t[: l]的s的最小子串，也就是最小的k，使得t[:l]是s[:k]的子串。接着我们只需要对比s[k+1:]能够匹配的最小r，使得t[r:]是s[k+1:]的子串。

也就是说只要确定了l，就能随之确定删除的最小区间的长度。我们考虑l能够取的最大值，即t串能够成为s子串的最大前缀。这个前缀很好求，使用贪心算法尽可能匹配即可。在此过程当中，我们还可以记录下每一次匹配对应的s串最小前缀的下标。

int j = 0;
for (int i = 0; i < n; i++) {
    if (j < m && s[i] == t[j]) {
        // 记录s串中匹配t[:j]的最小前缀的位置
        fwd[j++] = i;
    }
}
int le = j;

同理，我们也可以对t[r:]的情况如法炮制：

j = m-1;
for (int i = n-1; i > -1; i--) {
    if (j > -1 && s[i] == t[j]) {
        // 记录s串匹配t[j:]的最小后缀的位置
        bwd[j--] = i;
    }
}
j++;

循环之后j停留的位置就是l达不到的边界，我们称为左侧边界，用le记录(left_end)。这样一来，l的遍历范围就有了，是区间[0, le)。有了fwd数组之后， 我们就可以查到每一个l对应的s串的前缀，这就要求了与t[r:]匹配的s串的后缀不能有重叠。也就是要保证bwd[r] > fwd[l]，可以结合下图理解：

我们要使得删除的部分最小，也就是要找到每一个l对应的最小的r。而r的限制条件只有一个就是bwd[r] > fwd[l]，由于fwd[l]是递增的，而bwd[r]也是伴随r递增的。这样一来，我们使用两指针算法就可以轻松求出范围了。最后考虑一下边界情况，就可以AC了。

class Solution {
public:
    int minimumScore(string s, string t) {
        int n = s.length(), m = t.length();
        
        vector<int> fwd(m+1, -1), bwd(m+1, -1);
        
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (j < m && s[i] == t[j]) {
                fwd[j++] = i;
            }
        }
        int le = j;
        if (le == m) return 0;
        
        j = m-1;
        for (int i = n-1; i > -1; i--) {
            if (j > -1 && s[i] == t[j]) {
                bwd[j--] = i;
            }
        }
        j++;
        
        int re = j;
        
        // 删除le右侧以及re左侧的情况
        int ret = min(m-le+1, re);
        
        for (int i = 0; i < le; i++) {
            while (j < m && bwd[j] <= fwd[i]) j++;
            ret = min(ret, j-i-1);
        }
        return ret;
    }
};

总体来说这题的思路不算很难，但是边界情况以及对代码细节的要求比较高，可能调试起来会比较棘手。

好了，关于本次周赛就聊到这里，感谢大家的阅读，欢迎多多转发帮助老梁攒一点人气。