# # Leetcode 第295场周赛题解

## # Problem A - 重排字符形成目标字符串 (opens new window)

### # 方法一：计数

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

class Solution:
def rearrangeCharacters(self, s: str, target: str) -> int:
cs = collections.Counter(s)
ct = collections.Counter(target)
return min(cs[key] // ct[key] for key in ct)

1
2
3
4
5

## # Problem B - 价格减免 (opens new window)

### # 方法一：模拟 + 正则表达式

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

class Solution:
def discountPrices(self, sentence: str, discount: int) -> str:
return ' '.join([f'${int(word[1:]) * (100 - discount) / 100:.2f}' if re.fullmatch(r'\$[1-9]\d*', word) else word for word in sentence.split()])

1
2
3

## # Problem C - 使数组按非递减顺序排列 (opens new window)

### # 方法一：链表模拟

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

class Solution {
public:
int totalSteps(vector<int>& nums) {
list<int> lst(nums.begin(), nums.end());
vector<list<int>::iterator> to_del;
for (auto p = lst.begin(); next(p) != lst.end(); ++p) {
if (*p > *next(p))
to_del.push_back(next(p));
}

int ans = 0;
while (!to_del.empty()) {
ans++;
vector<list<int>::iterator> check;
for (auto p : to_del) {
auto pre = prev(p);
lst.erase(p);
if (check.empty() || check.back() != pre)
check.push_back(pre);
}
to_del.clear();
for (auto p: check) {
if (next(p) != lst.end() && *p > *next(p))
to_del.push_back(next(p));
}
}

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

## # Problem D - 到达角落需要移除障碍物的最小数目 (opens new window)

### # 方法一：0-1 BFS

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

const int d[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

class Solution {
public:
int minimumObstacles(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> dis(n, vector<int>(m, INT_MAX));
dis[0][0] = 0;
deque<pair<int, int>> dq;
dq.emplace_back(0, 0);
while (!dq.empty()) {
auto [i, j] = dq.front();
dq.pop_front();
for (int k = 0; k < 4; ++k) {
int ni = i + d[k][0], nj = j + d[k][1];
if (ni < 0 || ni >= n || nj < 0 || nj >= m || dis[ni][nj] < INT_MAX)
continue;
dis[ni][nj] = dis[i][j] + grid[ni][nj];
if (grid[ni][nj])
dq.emplace_back(ni, nj);
else
dq.emplace_front(ni, nj);
}
}
return dis[n - 1][m - 1];
}
};

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