# # Leetcode 第71场双周赛题解

## # Problem A - 拆分数位后四位数字的最小和 (opens new window)

### # 方法一：贪心

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

class Solution:
def minimumSum(self, num: int) -> int:
d = sorted(list(map(int, str(num))))
return (d[0] + d[1]) * 10 + d[2] + d[3]

1
2
3
4

## # Problem B - 根据给定数字划分数组 (opens new window)

### # 方法一：模拟

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

class Solution:
def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
small = [num for num in nums if num < pivot]
large = [num for num in nums if num > pivot]
return small + [pivot] * (len(nums) - len(small) - len(large)) + large

1
2
3
4
5

## # Problem C - 设置时间的最少代价 (opens new window)

### # 方法一：暴力

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

class Solution {
public:
int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
int ans = INT_MAX;
for (int i = 1; i <= 9999; ++i) {
int result = i / 100 * 60 + i % 100;
if (result != targetSeconds)
continue;

string s = to_string(i);
int cost = 0;
char curr = startAt + '0';
for (char ch : s) {
if (curr == ch)
cost += pushCost;
else {
curr = ch;
cost += moveCost + pushCost;
}
}
ans = min(ans, cost);
}
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

## # Problem D - 删除元素后和的最小差值 (opens new window)

### # 方法一：堆

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

using ll = long long;

class Solution {
public:
ll minimumDifference(vector<int>& nums) {
int n = nums.size() / 3;
ll ans = LLONG_MAX;

vector<ll> L(3 * n), R(3 * n);
ll lsum = 0;

priority_queue<int> pq;
for (int i = 0; i < 2 * n; ++i) {
pq.push(nums[i]);
lsum += nums[i];

if (pq.size() > n) {
lsum -= pq.top();
pq.pop();
}

L[i] = lsum;
}

ll rsum = 0;
priority_queue<int, vector<int>, greater<>> pq2;
for (int i = n * 3 - 1; i >= n; --i) {
pq2.push(nums[i]);
rsum += nums[i];

if (pq2.size() > n) {
rsum -= pq2.top();
pq2.pop();
}

R[i] = rsum;
}

for (int i = n - 1; i < 2 * n; ++i)
ans = min(ans, L[i] - R[i + 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
35
36
37
38
39
40
41
42
43
44