# # Leetcode 第278场周赛题解

## # Problem A - 将找到的值乘以 2 (opens new window)

### # 方法一：模拟

• 时间复杂度 $\mathcal{O}(N+\log M)$
• 空间复杂度 $\mathcal{O}(N)$

class Solution:
def findFinalValue(self, nums: List[int], original: int) -> int:
s = set(nums)
while original in s:
original *= 2
return original

1
2
3
4
5
6

## # Problem B - 分组得分最高的所有下标 (opens new window)

### # 方法一：前缀和

• 时间复杂度 $\mathcal{O}(N)$
• 空间复杂度 $\mathcal{O}(N)$

class Solution:
def maxScoreIndices(self, nums: List[int]) -> List[int]:
n = len(nums)
r = nums.count(1)
l = 0
hi = r
ans = [0]
for i in range(n):
if nums[i] == 1:
r -= 1
if nums[i] == 0:
l += 1
now = l + r
if now > hi:
hi = now
ans = []
if now == hi:
ans.append(i + 1)
return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

## # Problem C - 查找给定哈希值的子串 (opens new window)

### # 方法一：倒序滑动窗口

• 从左向右滑动
• 从右向左滑动

• 时间复杂度 $\mathcal{O}(N)$
• 空间复杂度 $\mathcal{O}(N)$

class Solution:
def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:
n = len(s)
pk = 1

now = 0
for i in range(n - k, n):
c = ord(s[i]) - ord('a') + 1
now = (now + c * pk) % modulo
if i != n - 1:
pk = pk * power % modulo

ans = -1 if now != hashValue else n - k

for i in range(n - k - 1, -1, -1):
c = ord(s[i]) - ord('a') + 1
d = ord(s[i + k]) - ord('a') + 1
now += modulo - d * pk % modulo
now = (now * power + c) % modulo
if now == hashValue:
ans = i

return s[ans:ans + k]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

## # Problem D - 字符串分组 (opens new window)

### # 方法一：并查集+枚举

• 删除：相当于把某一位从 1 变为 0
• 添加：相当于把某一位从 0 变为 1
• 修改：相当于把一个 0 变为 1， 同时把一个 1 变为 0（不考虑保持不变的情况）

• 时间复杂度$\mathcal{O}(N|\Sigma|^2\alpha(N))$
• 空间复杂度$\mathcal{O}(N)$

struct UnionFind {
int n;
vector<int> parent, size;

UnionFind(int n) {
this->n = n;
parent = vector<int>(n);
size = vector<int>(n, 1);
for (int i = 0; i < n; ++i)
parent[i] = i;
}

int find(int idx) {
if (parent[idx] == idx)
return idx;
return parent[idx] = find(parent[idx]);
}

void connect(int a, int b) {
int fa = find(a), fb = find(b);
if (fa != fb) {
if (size[fa] > size[fb]) {
parent[fb] = fa;
size[fa] += size[fb];
} else {
parent[fa] = fb;
size[fb] += size[fa];
}
}
}
};

class Solution {
public:
vector<int> groupStrings(vector<string>& words) {
int n = words.size();
vector<int> bits(n);
for (int i = 0; i < n; ++i)
for (char c : words[i])
bits[i] ^= 1 << (c - 'a');

UnionFind uf(n);
unordered_map<int, int> mp;
for (int i = 0; i < n; ++i) {
if (mp.count(bits[i]))
uf.connect(mp[bits[i]], i);
else {
for (int j = 0; j < 26; ++j) {
int nb = bits[i] ^ (1 << j);
if (mp.count(nb))
uf.connect(mp[nb], i);
}
for (int j = 0; j < 26; ++j) {
int mskj = 1 << j;
if ((bits[i] & mskj) == 0)
continue;
for (int k = 0; k < 26; ++k) {
int mskk = 1 << k;
if (bits[i] & mskk)
continue;
int nb = bits[i] ^ mskj ^ mskk;
if (mp.count(nb))
uf.connect(mp[nb], i);
}
}
}

if (!mp.count(bits[i]))
mp[bits[i]] = i;
}

int groups = 0, largest = 0;
for (int i = 0; i < n; ++i) {
if (uf.find(i) == i) {
groups++;
largest = max(largest, uf.size[i]);
}
}

return {groups, largest};
}
};

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82