新的一年从刷题开始，LeetCode周赛277题解
新的一年从刷题开始，LeetCode周赛277题解
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
今天是大年初一，首先给大家拜个年，祝大家上学的学业有成，工作的前程似锦，结婚的家庭美满。
新年新气象，刷题不能停，我们一起来回顾一下前天的LeetCode周赛。
年前的这一场周赛是网易游戏赞助的，前三百名可以获得网易游戏的内推资格。老梁非常可惜，排名305，完美错过……
废话不多说，我们来看题。
第一题
给定一个整数数组nums和一个目标值target，要求在数组当中寻找target，如果找到，就将它翻倍得到新的target，从头开始执行这个过程。
如果没有找到就结束，要求target的最终值。
解法
模拟题，照着题目的要求做即可。
我们用一个flag变量控制是否找到了target，将它作为while循环的判断条件。然后遍历数组更新target和flag即可。
class Solution {
public:
int findFinalValue(vector<int>& nums, int original) {
bool flag = true;
while (flag) {
flag = false;
for (auto &x : nums) {
if (x == original) {
original = original << 1;
flag = true;
break;
}
}
}
return original;
}
};
第二题
给你一个下标从 0 开始的二进制数组 nums ，数组长度为 n 。nums 可以按下标 i（ 0 <= i <= n ）拆分成两个数组（可能为空）：numsleft 和 numsright 。
- numsleft 包含 nums 中从下标 0 到 i - 1 的所有元素（包括 0 和 i - 1 ），而 numsright 包含 nums 中从下标 i 到 n - 1 的所有元素（包括 i 和 n - 1 ）。
- 如果 i == 0 ，numsleft 为 空 ，而 numsright 将包含 nums 中的所有元素。
- 如果 i == n ，numsleft 将包含 nums 中的所有元素，而 numsright 为 空 。
下标 i 的 分组得分 为 numsleft 中 0 的个数和 numsright 中 1 的个数之 和 。
返回 分组得分 最高 的 所有不同下标 。你可以按 任意顺序 返回答案。
提示：
n == nums.length1 <= n <= 1e5nums[i]为0或1
解法
首先，我们可以想到枚举所有的分组情况。但很显然，如果直接暴力枚举可能会超时。因为枚举所有的划分方法一重循环，对于每一种划分方法枚举其中0和1的数量，又需要一重循环，所以整体是O(n^2) 的复杂度。显然，在这题当中，这是不可接受的。
我们深入分析会发现，枚举所有划分方法是不可避免的，因为不枚举就找不到答案。唯一可以优化的点就是求0和1数量的时候，这也是我们着手的思路。
其实不难想到，假设我们已经知道了n_{left}, n_{right} 中0和1的数量，它们的划分下标是i。那么当我们枚举i+1的划分位置时，相当于n_{left} 集合当中增加了一个元素nums[i+1]，而n_{right} 集合中少了一个元素nums[i+1]。我们只需要根据nums[i+1]的值去调整答案即可。
如果大家熟悉区间移动的算法问题的话，应该不难想到。
class Solution {
public:
vector<int> maxScoreIndices(vector<int>& nums) {
int n = nums.size();
// 求出数组内0和1的值
int zero = 0, one = 0;
for (auto& x : nums) {
if (x == 0) zero++;
else one++;
}
int maxi = 0;
vector<int> ret;
int left = 0, right = one;
// i = -1 表示左侧区间为空
// i = n 表示右侧区间为空
for (int i = -1; i <= n; i++) {
// 单独特判左区间为空的情况
if (i < 0) {
maxi = one;
ret.push_back(0);
continue;
}
// 单独特判右区间为空的情况
if (i == n) {
if (zero > maxi) {
maxi = zero;
ret.clear();
ret.push_back(i);
}
continue;
}
// 普通情况，如果nums[i]=0，那么left++，即左区间0的数量+1，否则右区间1的数量--
if (nums[i] == 0) left++;
else right--;
// 维护答案
if (left + right > maxi) {
maxi = left+right;
ret.clear();
ret.push_back(i+1);
}else if (left + right == maxi) {
ret.push_back(i+1);
}
}
return ret;
}
};
第三题
给定整数 p 和 m ，一个长度为 k 且下标从 0 开始的字符串 s 的哈希值按照如下函数计算：
- hash(s, p, m) = (val(s[0]) * p^0 + val(s[1]) * p^1 + ... + val(s[k-1]) * p^{k-1}) \mod m
. 其中 val(s[i]) 表示 s[i] 在字母表中的下标，从 val('a') = 1 到 val('z') = 26 。
给你一个字符串 s 和整数 power，modulo，k 和 hashValue 。请你返回 s 中 第一个 长度为 k 的 子串 sub ，满足 hash(sub, power, modulo) == hashValue 。
测试数据保证一定 存在 至少一个这样的子串。
子串 定义为一个字符串中连续非空字符组成的序列。
解法
这题有点难，估计题意很多人就没读懂。
首先解释一下对于字符串s求hash值的公式，如果用代码表示的话，它大概写成这样：
def hash(word, p, m):
h = 0
for i in range(len(word)):
h += (ord(word[i]) - ord('a') + 1) * p ** i
h %= m
return h
题目要求的就是我们根据给出的p和k，在原串中找到一个子串，满足子串的hash值等于hashValue。
首先可以想到枚举，我们枚举出所有的子串，再分别计算出这些子串的hash值。但显然这样的复杂度很大，是O(nk) 的复杂度，估算一下就知道，在这题当中是无法接受的，一定会超时。
那有没有什么办法可以优化呢？
有办法， 我们观察一下hash值的计算公式。我们把word[i] - 'a' + 1看成是系数，那么所有位置的系数计算方法是一样的。不同的是后面乘上的p的幂不同，位数每增加一位，p的幂加一 。同样一个字母在第i为和在第i+1位对于hash值的贡献相差了p倍，从这点入手，我们不难找出优化的方法。
我们假设s[i:i+k]的hash值是k1，s[i+1:i+k+1]的hash值是k2。我们不难发现这两个序列当中s[i+1:i+k]的部分是重合的，根据前面的结论，我们可以知道这个部分在前后的hash值中的贡献相差了p倍。对于k2来说i+1是第0位，而对于k1来说i+1是第1位，也就是说在k1中的贡献比k2中的大。理清楚了这些之后， 我们不难用k2算出k1：
其实很简单，也就是用k2去掉最后一个字母s[i+k]对hash值的影响（因为s[i+k]不在序列k1当中），然后乘上p，加上s[i]的影响。
如此一来我们就找到了一个计算方法，可以快速的迭代出每一个子串的hash值，而不必挨个字母的遍历了。另外我们发现p的幂反复用到，我们也可以事先算出每一个p的幂，存入数组当中，这样可以进一步节省计算资源。
class Solution {
public:
string subStrHash(string s, int p, int m, int k, int hv) {
int n = s.length();
long long pow[k+2];
pow[0] = 1;
// 预处理p的0到k-1次方
for (int i = 1; i < k; i++) {
pow[i] = pow[i-1] * (long long)p;
pow[i] = pow[i] % m;
}
// 算出最后一个区间s[n-k:n]的hash值
long long tmp = 0;
for (int i = n-1; i >= n-k; i--) {
tmp += (s[i] - 'a' + 1) * pow[i-n+k];
tmp = tmp % m;
}
int start = -1;
if (tmp == hv) start = n-k;
// 区间往前移动
for (int i = n-k-1; i > -1; i--) {
tmp -= (s[i+k]-'a' + 1) * pow[k-1];
tmp %= m;
tmp *= p;
tmp += (s[i] - 'a' + 1);
tmp = tmp % m;
if (tmp < 0) tmp += m;
if (tmp == hv) start = i;
}
return s.substr(start, k);
}
};
第四题
给你一个下标从 0 开始的字符串数组 words 。每个字符串都只包含 小写英文字母 。words 中任意一个子串中，每个字母都至多只出现一次。
如果通过以下操作之一，我们可以从 s1 的字母集合得到 s2 的字母集合，那么我们称这两个字符串为 关联的 ：
- 往 s1 的字母集合中添加一个字母。
- 从 s1 的字母集合中删去一个字母。
- 将 s1 中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）。
数组 words 可以分为一个或者多个无交集的 组 。一个字符串与一个组如果满足以下 任一 条件，它就属于这个组：
- 它与组内 至少 一个其他字符串关联。
- 它是这个组中 唯一 的字符串。
注意，你需要确保分好组后，一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下，分组方案是唯一的。
请你返回一个长度为 2 的数组 ans ：
- ans[0] 是 words 分组后的 总组数 。
- ans[1] 是字符串数目最多的组所包含的字符串数目。
解法
读完题目之后不难发现，这是一个合并集合的问题。
我们把所有拥有关联关系的字符串合并到一个集合里，如果一个字符串和其它所有字符串都没有关联，那么它自成一个集合。最后要求的就是合并之后集合的数量以及最大集合中的字符串数量。
观察一下数据范围可以发现，字符串的数量不少，在1e4这个量级。我们要判断两个字符串有没有关联，需要考虑添加字符、删除字符以及替换字符三种情况，如此一来会导致复杂度非常大。所以第一个难题就是怎么样快速地判断两个字符串之间是否拥有关联。
想要破解这个问题需要我们仔细阅读题目，题目当中说了每个单词当中的字母都是唯一的，这也就是说单词的长度最多是26。为什么说这个信息非常关键呢，因为我们判断两个字符串是否关联是不需要考虑字符排列顺序的，也就是说我们可以用一个int整数表示单词了。
怎么操作呢？我们都知道一个int有32个二进制位，而字符串最多只有26个字母，并且不会有重复的字母。那么我们就可以用二进制的0和1表示字母是否存在。比如单词ace，表示成二进制的话它的前5位就是[1, 0, 1, 0, 1]。二进制是可以表示成整数的，也就是说我们就用一个整数代表了一个字符串。这样我们只需要判断整数相等就可以判断两个字符串是否构成相同了。
剩下的问题就是如果两个集合当中存在字符串关联，怎么将它们合并在一起。这个就需要用到专门处理集合合并的并查集算法了，如果不了解并查集算法的同学可以阅读一下老梁之前的文章：
这题还有一个坑点，就是题目中可能预先存在构成相同的字符串，我们需要提前处理，不然很容易超时。
另外这题的时限卡得非常紧，老梁在比赛的时候写出了正解依然被卡超时了。赛后看了一下评论，好像这样遭遇的小伙伴还不少……
class Solution {
public:
// 并查集
vector<int> fa, rank;
void init(int n) {
for (int i = 0; i < n; i++) {
fa[i] = i;
rank[i] = 1;
}
}
int find(int x) {
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
void merge(int i, int j) {
int x = find(i), y = find(j);
if (rank[x] <= rank[y]) fa[x] = y;
else fa[y] = x;
if (rank[x] == rank[y] && x != y) rank[y]++;
}
// 将单词转化成整数
int convert(string& s) {
int n = s.length();
int ret = 0;
for (int i = 0; i < n; i++) {
// s[i] - 'a' 转化成0-25的整数
// 1 << i 表示第i为是1其余都是0的整数
ret |= (1 << (s[i] - 'a'));
}
return ret;
}
vector<int> groupStrings(vector<string>& words) {
int n = words.size();
fa.resize(n+2);
rank.resize(n+2);
init(n);
map<int, int> mp;
vector<int> iwords(n, 0);
for (int i = 0; i < n; i++) {
int c = convert(words[i]);
// 如果已经存在构成相同的，合并
if (mp.count(c)) {
merge(i, mp[c]);
}
mp[c] = i;
iwords[i] = c;
}
for (int i = 0; i < n; i++) {
int c = iwords[i];
// 如果j位为1则枚举删除j为的字母，否则枚举添加j位
for (int j = 0; j < 26; j++) {
// j位为1
if (c & (1 << j)) {
int cur = c - (1 << j);
if (mp.count(cur)) {
int v = mp[cur];
merge(v, i);
}
// 继续枚举替换j为k
for (int k = 0; k < 26; k++) {
if ((c & (1 << k)) == 0) {
int cur = c - (1 << j) + (1 << k);
if (mp.count(cur)) {
int v = mp[cur];
merge(v, i);
}
}
}
}
// j位为0，枚举删除j位
if ((c & (1 << j)) == 0) {
int cur = c + (1 << j);
if (mp.count(cur)) {
int v = mp[cur];
merge(v, i);
}
}
}
}
// 维护答案，也可以直接在并查集中处理
map<int, int> ret;
int maxi = 1;
for (int i = 0; i < n; i++) {
int f = find(i);
if (ret.count(f)) ret[f]++;
else ret[f] = 1;
maxi = max(maxi ,ret[f]);
}
vector<int> ans = {(int) ret.size(), maxi};
return ans;
}
};
这次比赛的难度梯度挺明显的，最后两题还是有一定挑战的，对于思维和算法的考察都比较高一些，除了最后一题时限卡的有点紧，整场比赛的质量是非常高的，非常推荐大家拿来练手。
最后，再次感谢大家的阅读，祝大家新春愉快。