# # Leetcode 第52场双周赛题解

## # Problem A - 将句子排序 (opens new window)

### # 方法一：模拟

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

class Solution:
def sortSentence(self, s: str) -> str:
words = list(map(lambda x: (int(x[-1]), x[:-1]), s.split()))
words.sort()
return ' '.join(map(lambda x: x[1], words))

1
2
3
4
5

## # Problem B - 增长的内存泄露 (opens new window)

### # 方法一：模拟

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

class Solution:
def memLeak(self, memory1: int, memory2: int) -> List[int]:
i = 1
while memory1 >= i or memory2 >= i:
if memory1 >= memory2:
memory1 -= i
else:
memory2 -= i
i += 1
return [i, memory1, memory2]

1
2
3
4
5
6
7
8
9
10

## # Problem C - 旋转盒子 (opens new window)

### # 方法一：模拟

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

class Solution {
public:
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
int n = box.size(), m = box[0].size();
vector<vector<char>> ans(m, vector<char>(n, '.'));
for (int i = 0; i < n; ++i) {
int bottom = m, stones = 0;
for (int j = m - 1; j >= 0; --j) {
if (box[i][j] == '*') {
while (stones) {
bottom--, stones--;
ans[bottom][n - 1 - i] = '#';
}
bottom = j;
ans[bottom][n - 1 - i] = '*';
} else if (box[i][j] == '#') {
stones++;
}
}
while (stones) {
bottom--, stones--;
ans[bottom][n - 1 - i] = '#';
}
}

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

## # Problem D - 向下取整数对和 (opens new window)

### # 方法一：计数+前缀和+调和级数思想

• 时间复杂度$\mathcal{O}(H\log H+N)$，其中$H=\max{nums}$
• 空间复杂度$\mathcal{O}(H)$

using ll = long long;
const ll MOD = 1e9 + 7;

class Solution {
public:
int sumOfFlooredPairs(vector<int>& nums) {
int n = nums.size();
int hi = *max_element(nums.begin(), nums.end());
ll ans = 0;

vector<int> cnt(hi + 1);
vector<int> a(hi + 1);
for (int num : nums)
cnt[num]++;
for (int i = 1; i <= hi; ++i)
a[i] = a[i - 1] + cnt[i];

for (int i = 1; i <= hi; ++i) {
if (cnt[i]) {
int j = i * 2 - 1;
for (; j < hi; j += i) {
ans += 1LL * cnt[i] * (j / i) * (a[j] - a[j - i]);
}
ans += 1LL * cnt[i] * (hi / i) * (a[hi] - a[hi / i * i - 1]);
}
}

return ans % MOD;
}
};

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