# # Leetcode 第251场周赛题解

## # Problem A - 字符串转化后的各位数字之和 (opens new window)

### # 方法一：模拟

• 时间复杂度$\mathcal{O}(k|S|)$
• 空间复杂度$\mathcal{O}(|S|)$

class Solution:
def getLucky(self, s: str, k: int) -> int:
snum = ''.join(map(lambda x: str(ord(x) - ord('a') + 1), s))
for _ in range(k):
snum = str(sum(map(int, snum)))
return int(snum)

1
2
3
4
5
6

## # Problem B - 子字符串突变后可能得到的最大整数 (opens new window)

### # 方法一：贪心

• 时间复杂度$\mathcal{O}(|S|)$
• 空间复杂度$\mathcal{O}(1)$

class Solution {
public:
string maximumNumber(string num, vector<int>& change) {
int n = num.size(), i = 0;
while (i < n && change[num[i] - '0'] <= num[i] - '0')
i++;
while (i < n && change[num[i] - '0'] >= num[i] - '0')
num[i] = change[num[i] - '0'] + '0', i++;
return num;
}
};

1
2
3
4
5
6
7
8
9
10
11

## # Problem C - 最大兼容性评分和 (opens new window)

### # 方法一：穷举

• 时间复杂度$\mathcal{O}(M\cdot M!)=\mathcal{O}(M!)$
• 空间复杂度$\mathcal{O}(M^2)$

class Solution:
def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
m, n = len(students), len(students[0])
points = [[0] * m for _ in range(m)]
for i in range(m):
for j in range(m):
for k in range(n):
points[i][j] += 1 if students[i][k] == mentors[j][k] else 0
ans = 0
for order in itertools.permutations(range(m)):
curr = 0
for i in range(m):
curr += points[i][order[i]]
ans = max(ans, curr)
return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

### # 方法二：状态压缩动态规划

• 时间复杂度$\mathcal{O}(M\cdot2^M)$
• 空间复杂度$\mathcal{O}(M^2+2^M)=\mathcal{O}(2^M)$

class Solution {
public:
int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
int m = students.size(), n = students[0].size();
vector<vector<int>> points(m, vector<int>(m));
for (int i = 0; i < m; ++i)
for (int j = 0; j < m; ++j)
for (int k = 0; k < n; ++k)
points[i][j] += students[i][k] == mentors[j][k];

vector<int> dp(1 << m);
for (int i = 0; i + 1 < (1 << m); ++i) {
int idx = __builtin_popcount(i);
for (int j = 0; j < m; ++j) {
if (!(i & (1 << j))) {
int nxt = i ^ (1 << j);
dp[nxt] = max(dp[nxt], dp[i] + points[idx][j]);
}
}
}

return dp.back();
}
};

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

## # Problem D - 删除系统中的重复文件夹 (opens new window)

### # 方法一：树哈希

$h=H(name_1+h_1+"/"+name_2+h_2+"/"+\dots)$

[["a"], ["a", "b"], ["a", "c"], ["d"], ["d", "c"], ["d", "b"]]

using ull = unsigned long long;
const int P = 129;

struct Node {
string name;
map<string, Node*> children;
ull hash = 0;
bool deleted = false;

Node(string name): name(name) {}
};

unordered_map<ull, vector<Node*>> mp;
vector<vector<string>> ans;

void dfs(Node *p) {
string sub;
for (auto [name, node] : p->children) {
dfs(node);
sub += name + to_string(node->hash) + "/";
}
for (char ch : sub)
p->hash = p->hash * P + ch;
if (!p->children.empty())
mp[p->hash].emplace_back(p);
}

void dfs2(Node *p, vector<string> &curr) {
if (!p->deleted) {
if (p->name != "/") {
curr.push_back(p->name);
ans.push_back(curr);
}
for (auto [_name, node] : p->children)
dfs2(node, curr);
if (p->name != "/")
curr.pop_back();
}
}

class Solution {
public:
vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {
Node *root = new Node("/");
for (auto &path : paths) {
Node *p = root;
for (string &dir : path) {
if (!p->children.count(dir))
p->children[dir] = new Node(dir);
p = p->children[dir];
}
}

mp.clear();
dfs(root);
for (auto [hash, nodes] : mp) {
if (nodes.size() >= 2) {
for (Node *node : nodes)
node->deleted = true;
}
}

ans.clear();
vector<string> curr;
dfs2(root, curr);
return ans;
}
};

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