# # Leetcode 第259场周赛题解

## # Problem A - 执行操作后的变量值 (opens new window)

### # 方法一：模拟

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

class Solution:
def finalValueAfterOperations(self, operations: List[str]) -> int:
x = 0
for op in operations:
if op == 'X++' or op == '++X':
x += 1
else:
x -= 1
return x

1
2
3
4
5
6
7
8
9

## # Problem B - 数组美丽值求和 (opens new window)

### # 方法一：前缀和

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

class Solution {
public:
int sumOfBeauties(vector<int>& nums) {
int n = nums.size();
vector<int> pre(n), suf(n);
pre[0] = nums[0];
for (int i = 1; i < n; ++i)
pre[i] = max(pre[i - 1], nums[i]);
suf[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; --i)
suf[i] = min(suf[i + 1], nums[i]);
int ans = 0;
for (int i = 1; i < n - 1; ++i) {
if (pre[i - 1] < nums[i] && nums[i] < suf[i + 1])
ans += 2;
else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1])
ans++;
}
return ans;
}
};

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

## # Problem C - 检测正方形 (opens new window)

### # 方法一：哈希表

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

class DetectSquares:

def __init__(self):
self.cnt = collections.Counter()

def add(self, point: List[int]) -> None:
self.cnt[(point[0], point[1])] += 1

def count(self, point: List[int]) -> int:
x, y = point
ans = 0
for xi, yi in self.cnt:
if abs(xi - x) == abs(yi - y) and xi != x:
if (xi, y) in self.cnt and (x, yi) in self.cnt:
ans += self.cnt[(xi, yi)] * self.cnt[(xi, y)] * self.cnt[(x, yi)]
return ans


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

## # Problem D - 重复 K 次的最长子序列 (opens new window)

### # 方法一：回溯

• 时间复杂度$\mathcal{O}(|S|\cdot\lfloor\frac{|S|}{k}\rfloor!)$，。
• 空间复杂度$\mathcal{O}(|S|)$

class Solution {
int k;
unordered_map<char, int> cnt;
string s, t, ans;

void dfs() {
unordered_map<char, int> cnt2(cnt);
for (auto [ch, freq] : cnt2) {
t.push_back(ch);
if (t.size() > ans.size() || (t.size() == ans.size() && t > ans)) {
int times = 0, pos = 0;
for (char c : s)
if (c == t[pos]) {
pos++;
if (pos == t.size())
times++, pos = 0;
}

if (times >= k)
ans = t;
}
cnt[ch] -= k;
if (cnt[ch] < k)
cnt.erase(ch);
dfs();
t.pop_back();
cnt[ch] = freq;
}
}
public:
string longestSubsequenceRepeatedK(string s, int k) {
this->k = k;
int n = s.size();
for (char c : s)
cnt[c]++;
string to_del;
for (auto [ch, freq] : cnt)
if (freq < k)
to_del.push_back(ch);
for (char ch : to_del)
cnt.erase(ch);

for (char c : s)
if (cnt.count(c))
this->s.push_back(c);

dfs();

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