# # Leetcode 第238场周赛题解

## # Problem A - K 进制表示下的各位数字总和 (opens new window)

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

class Solution {
public:
int sumBase(int n, int k) {
int ans = 0;
while (n) {
ans += n % k;
n /= k;
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11

## # Problem B - 最高频元素的频数 (opens new window)

• 时间复杂度$\mathcal{O}(N\log N)$，因为我们需要对数组进行排序。
• 空间复杂度$\mathcal{O}(1)$

using ll = long long;

class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int ans = 0, n = nums.size();
ll sum = 0;
int l = 0;
for (int r = 0; r < n; ++r) {
sum += nums[r];
while (1LL * nums[r] * (r - l + 1) - sum > k) {
sum -= nums[l];
l++;
}
ans = max(ans, r - l + 1);
}
return ans;
}
};

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

## # Problem C - 所有元音按顺序排布的最长子字符串 (opens new window)

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

class Solution {
public:
int longestBeautifulSubstring(string word) {
string ref = "aeiou";
int ans = 0;
int start = -1;
int now = 0;
for (int i = 0; i < word.size(); ++i) {
if (start == -1) {
if (word[i] != 'a')
continue;
else {
start = i;
now = 0;
}
} else {
if (now < 4 && word[i] == ref[now + 1])
now++;
else if (word[i] != ref[now]) {
if (word[i] == 'a')
start = i, now = 0;
else
start = -1;
}
}

if (start != -1 && now == 4)
ans = max(ans, i - start + 1);
}

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

## # Problem D - 最高建筑高度 (opens new window)

• 时间复杂度$\mathcal{O}(M\log M)$，因为我们需要对限制条件进行排序。
• 空间复杂度$\mathcal{O}(M)$

class Solution {
public:
int maxBuilding(int n, vector<vector<int>>& restrictions) {
int m = restrictions.size();
if (m == 0)
return n - 1;
restrictions.push_back({1, 0});
m++;
sort(restrictions.begin(), restrictions.end());
vector<int> l(m), r(m);
l[0] = 0;
for (int i = 1; i < m; ++i) {
int left = l[i - 1];
int dist = restrictions[i][0] - restrictions[i - 1][0];
l[i] = min(restrictions[i][1], left + dist);
}
r[m - 1] = restrictions[m - 1][1];
for (int i = m - 2; i >= 0; --i) {
int right = r[i + 1];
int dist = restrictions[i + 1][0] - restrictions[i][0];
r[i] = min(restrictions[i][1], right + dist);
}
int ans = 0;
for (int i = 0; i < m - 1; ++i) {
int lh = min(l[i], r[i]);
int rh = min(l[i + 1], r[i + 1]);
int dist = restrictions[i + 1][0] - restrictions[i][0];
ans = max(ans, (lh + rh + dist) / 2);
}
ans = max(ans, n - restrictions[m - 1][0] + min(l[m - 1], r[m - 1]));

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