# # Leetcode 第70场双周赛题解

## # Problem A - 打折购买糖果的最小开销 (opens new window)

### # 方法一：排序+贪心

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

class Solution:
def minimumCost(self, cost: List[int]) -> int:
return sum(x for i, x in enumerate(sorted(cost, reverse=True)) if i % 3 != 2)

1
2
3

## # Problem B - 统计隐藏数组数目 (opens new window)

### # 方法一：假设起始值为0

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

class Solution:
def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
lo = 0
hi = 0
now = 0
for diff in differences:
now += diff
lo = min(lo, now)
hi = max(hi, now)
hi += lower - lo
return max(0, upper - hi + 1)

1
2
3
4
5
6
7
8
9
10
11

## # Problem C - 价格范围内最高排名的 K 样物品 (opens new window)

### # 方法一：BFS+排序

BFS找出所有符合条件的物品，再按照题目要求排序取前 $K$ 个即可。

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

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

class Solution {
public:
vector<vector<int>> highestRankedKItems(vector<vector<int>>& grid, vector<int>& pricing, vector<int>& start, int k) {
int n = grid.size(), m = grid[0].size();
int lo = pricing[0], hi = pricing[1];
int r = start[0], c = start[1];
vector<tuple<int, int, int, int>> ans;
queue<tuple<int, int, int>> q;
vector<vector<bool>> vis(n, vector<bool>(m));
q.emplace(0, r, c);
vis[r][c] = true;
while (!q.empty()) {
auto [steps, i, j] = q.front();
if (grid[i][j] >= lo && grid[i][j] <= hi)
ans.emplace_back(steps, grid[i][j], i, j);
q.pop();
for (int t = 0; t < 4; ++t) {
int ni = i + d[t][0], nj = j + d[t][1];
if (ni < 0 || ni >= n || nj < 0 || nj >= m || vis[ni][nj] || grid[ni][nj] == 0)
continue;
q.emplace(steps + 1, ni, nj);
vis[ni][nj] = true;
}
}
sort(ans.begin(), ans.end());
vector<vector<int>> ret;
for (int i = 0; i < min(k, (int)ans.size()); ++i)
ret.push_back(vector<int>{get<2>(ans[i]), get<3>(ans[i])});
return ret;
}
};

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}(N)$
• 空间复杂度$\mathcal{O}(1)$

const int MOD = 1e9 + 7;

class Solution {
public:
int numberOfWays(string corridor) {
int seats = 0;
for (char ch : corridor)
seats += ch == 'S';
if (seats % 2 != 0)
return 0;

int zero = 1, one = 0, two = 0;
for (char ch : corridor) {
if (ch == 'S') {
int tmp = zero;
zero = two = one;
one = tmp;
} else {
zero = (zero + two) % MOD;
}
}

return two;
}
};

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