# # Leetcode 第192场周赛题解

## # Problem A - 重新排列数组 (opens new window)

### # 方法一：模拟

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

class Solution {
public:
vector<int> shuffle(vector<int>& nums, int n) {
vector<int> ans(n * 2);
for (int i = 0; i < n; ++i) {
ans[i * 2] = nums[i];
ans[i * 2 + 1] = nums[n + i];
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11

## # Problem B - 数组中的 k 个最强值 (opens new window)

### # 方法一：排序

• 时间复杂度$\mathcal{O}(N\log N)$
• 空间复杂度$\mathcal{O}(1)$，使用了常数量级的额外空间。

class Solution {
public:
vector<int> getStrongest(vector<int>& arr, int k) {
int n = arr.size();
nth_element(arr.begin(), arr.begin() + (n - 1) / 2, arr.end());
int mid = arr[(n - 1) / 2];
sort(arr.begin(), arr.end(), [&](int p, int q){
return abs(p - mid) == abs(q - mid) ? p > q : abs(p - mid) > abs(q - mid);
});
arr.resize(k);
return arr;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13

## # Problem C - 设计浏览器历史记录 (opens new window)

### # 方法一：模拟

class BrowserHistory:

def __init__(self, homepage: str):
self.history = [homepage]
self.idx = 0

def visit(self, url: str) -> None:
self.history = self.history[:self.idx + 1]
self.idx += 1
self.history.append(url)

def back(self, steps: int) -> str:
self.idx = max(self.idx - steps, 0)
return self.history[self.idx]

def forward(self, steps: int) -> str:
self.idx = min(len(self.history) - 1, self.idx + steps);
return self.history[self.idx]

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

## # Problem D - 粉刷房子 III (opens new window)

### # 方法一：动态规划

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

const int INF = 0x3f3f3f3f;

class Solution {
public:
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
vector<vector<int>> dp(target + 1, vector<int>(n, INF));
for (int i = 0; i < n; ++i)
dp[0][i] = 0;
vector<array<int, 3>> best(target + 1, {INF, INF, INF});
best[0] = {0, -1, 0};
for (int i = 0; i < m; ++i) {
vector<vector<int>> ndp(target + 1, vector<int>(n, INF));
vector<array<int, 3>> nbest(target + 1, {INF, INF, INF});

for (int blocks = 0; blocks <= target; ++blocks) {
for (int color = 0; color < n; ++color) {
if (houses[i] == 0) {
// Case 1&2: Use a different color.
if (blocks < target) {
// Case 1: Current house is not colored, and the color to use matches the best choice, so we need to use the second best.
if (color == best[blocks][1]) {
ndp[blocks + 1][color] = min(ndp[blocks + 1][color], best[blocks][2] + cost[i][color]);
} else {
// Case 2: Current house is not colored, and we use the best.
ndp[blocks + 1][color] = min(ndp[blocks + 1][color], best[blocks][0] + cost[i][color]);
}
}

// Case 3: Use the same color.
if (blocks > 0) {
ndp[blocks][color] = min(ndp[blocks][color], dp[blocks][color] + cost[i][color]);
}
} else if (houses[i] - 1 == color && blocks > 0) {
// Case 4: Current house is already colored, but does not form a new block.
ndp[blocks][color] = min(ndp[blocks][color], dp[blocks][color]);
} else if (blocks < target) {
// Case 5: Current house is already colored, and forms a new block.
ndp[blocks + 1][houses[i] - 1] = min(ndp[blocks + 1][houses[i] - 1], dp[blocks][color]);
}
}
}

for (int blocks = 1; blocks <= target; ++blocks) {
for (int color = 0; color < n; ++color) {
if (ndp[blocks][color] < nbest[blocks][0]) {
nbest[blocks][2] = nbest[blocks][0];
nbest[blocks][1] = color;
nbest[blocks][0] = ndp[blocks][color];
} else if (ndp[blocks][color] < nbest[blocks][2]) {
nbest[blocks][2] = ndp[blocks][color];
}
}
}

dp = move(ndp);
best = move(nbest);
}

int ans = INF;
for (int color = 0; color < n; ++color)
ans = min(ans, dp[target][color]);
return ans == INF ? -1 : 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
52
53
54
55
56
57
58
59
60
61
62
63
64