# # Leetcode 第287场周赛题解

## # Problem A - 转化时间需要的最少操作数 (opens new window)

### # 方法一：模拟

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

class Solution:
def convertTime(self, current: str, correct: str) -> int:
sh, sm = map(int, current.split(':'))
th, tm = map(int, correct.split(':'))
delta = (th * 60 + tm) - (sh * 60 + sm)
ans = 0
for unit in [60, 15, 5, 1]:
ans += delta // unit
delta %= unit
return ans

1
2
3
4
5
6
7
8
9
10

int seconds(string s) {
return stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3, 2));
}

class Solution {
public:
int convertTime(string current, string correct) {
int start = seconds(current);
int end = seconds(correct);
int delta = end - start;
int ans = 0;
if (delta >= 60)
ans += delta / 60, delta %= 60;
if (delta >= 15)
ans += delta / 15, delta %= 15;
if (delta >= 5)
ans += delta / 5, delta %= 5;
return ans + delta;
}
};

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

## # Problem B - 找出输掉零场或一场比赛的玩家 (opens new window)

### # 方法一：模拟

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

class Solution:
def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
all_players = set(itertools.chain(*matches))
lose_count = collections.Counter([loser for winner, loser in matches])
return [sorted([player for player in all_players if lose_count[player] == i]) for i in range(2)]

1
2
3
4
5

class Solution {
public:
vector<vector<int>> findWinners(vector<vector<int>>& matches) {
unordered_map<int, int> cnt;
for (auto &v : matches)
cnt[v[0]] += 0, cnt[v[1]]++;
vector<vector<int>> ans(2);
for (auto [k, v] : cnt)
if (v <= 1)
ans[v].push_back(k);
sort(ans[0].begin(), ans[0].end());
sort(ans[1].begin(), ans[1].end());
return ans;
}
};

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

## # Problem C - 每个小孩最多能分到多少糖果 (opens new window)

### # 方法一：二分答案

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

class Solution {
public:
int maximumCandies(vector<int>& candies, long long k) {
long long lo = 1, hi = 1e12;
while (lo <= hi) {
long long mid = (lo + hi) >> 1;
long long can = 0;
for (int candy : candies)
can += candy / mid;
if (can >= k)
lo = mid + 1;
else
hi = mid - 1;
}
return hi;
}
};

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

## # Problem D - 加密解密字符串 (opens new window)

### # 方法一：预先加密字典中的所有字符串

• 时间复杂度 $\mathcal{O}(\Sigma\cdot K)$，其中 $\Sigma$ 是所有栈的元素数目之和。
• 空间复杂度 $\mathcal{O}(K)$

class Encrypter:

def __init__(self, keys: List[str], values: List[str], dictionary: List[str]):
self.d = {key: value for key, value in zip(keys, values)}
self.cnt = collections.Counter(self.encrypt(word) for word in dictionary)

def encrypt(self, word1: str) -> str:
return ''.join(self.d[ch] for ch in word1) if all(ch in self.d for ch in word1) else ''

def decrypt(self, word2: str) -> int:
return self.cnt[word2]

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

class Encrypter {
vector<string> v;
unordered_map<string, int> cnt;

public:
Encrypter(vector<char>& keys, vector<string>& values, vector<string>& dictionary) {
v = vector<string>(26);

for (int i = 0; i < keys.size(); ++i)
v[keys[i] - 'a'] = values[i];

for (auto &s : dictionary)
cnt[encrypt(s)]++;
}

string encrypt(string word1) {
string result;
for (char ch : word1) {
if (v[ch - 'a'].empty())
return "";
result += v[ch - 'a'];
}
return result;
}

int decrypt(string word2) {
return cnt[word2];
}
};

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

### # 方法二：字典树

struct Trie {
bool flag{};
Trie* children[26]{};

Trie() {}
};

class Encrypter {
Trie *root;
vector<string> v;
unordered_map<string, vector<int>> mp;

public:
Encrypter(vector<char>& keys, vector<string>& values, vector<string>& dictionary) {
v = vector<string>(26);

for (int i = 0; i < keys.size(); ++i)
v[keys[i] - 'a'] = values[i], mp[values[i]].push_back(keys[i] - 'a');

root = new Trie();
for (auto s : dictionary) {
Trie *p = root;
for (char c : s) {
if (p->children[c - 'a'] == nullptr)
p->children[c - 'a'] = new Trie();
p = p->children[c - 'a'];
}
p->flag = true;
}
}

string encrypt(string word1) {
string result;
for (char ch : word1)
if (v[ch - 'a'].empty())
result.push_back(ch);
else
result += v[ch - 'a'];
return result;
}

int decrypt(string word2) {
vector<Trie*> possible{root};

for (int i = 0; i < word2.size(); i += 2) {
vector<Trie*> nxt;
for (int j : mp[word2.substr(i, 2)]) {
for (Trie *p : possible) {
if (p->children[j] != nullptr)
nxt.push_back(p->children[j]);
}
}

possible = move(nxt);
}

int ans = 0;

for (Trie *p : possible)
ans += p->flag;

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