# # Leetcode 第227场周赛题解

## # Problem A - 检查数组是否经排序和轮转得到 (opens new window)

### # 方法一：暴力

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

class Solution:
def check(self, nums: List[int]) -> bool:
asc = sorted(nums)
for i in range(0, len(nums)):
rot = nums[i:] + nums[:i]
if rot == asc:
return True
return False

1
2
3
4
5
6
7
8

### # 方法二：利用有序数组的性质

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

impl Solution {
pub fn check(nums: Vec<i32>) -> bool {
let mut dec = 0;
for i in 0..nums.len() {
let nxt = nums[(i + 1) % nums.len()];
if nums[i] > nxt {
dec += 1;
}
}
dec <= 1
}
}

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

## # Problem B - 移除石子的最大得分 (opens new window)

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

class Solution:
def maximumScore(self, a: int, b: int, c: int) -> int:
hi = max(a, b, c)
lo = min(a, b, c)
mid = sum([a, b, c]) - hi - lo
ans = 0
ans += min(hi, lo + mid)
if lo + mid > hi:
ans += (lo + mid - hi) // 2
return ans

1
2
3
4
5
6
7
8
9
10

## # Problem C - 构造字典序最大的合并字符串 (opens new window)

### # 方法一：贪心

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

class Solution {
public:
string largestMerge(string word1, string word2) {
string ans;
int n = word1.size(), m = word2.size();
int l = 0, r = 0;
auto check = [&](int i, int j) {
while (i < n && j < m) {
if (word1[i] > word2[j]) {
return true;
}
if (word1[i] < word2[j]) {
return false;
}
i++;
if (i == n)
return false;
j++;
if (j == m)
return true;
}
return true;
};
while (l < n || r < m) {
if (r == m || (l < n && check(l, r))) {
ans.push_back(word1[l]);
l++;
} else {
ans.push_back(word2[r]);
r++;
}
}
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

## # Problem D - 最接近目标值的子序列和 (opens new window)

### # 方法一：折半搜索

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

class Solution {
public:
int minAbsDifference(vector<int>& nums, int goal) {
int n = nums.size();
int left = (n + 1) / 2;
set<int> L, R;
vector<int> sl(1 << left), sr(1 << (n - left));
L.insert(0), R.insert(0);
for (int i = 0; i < (1 << left); ++i) {
int s = 0;
for (int j = 0; j < left; ++j)
if (i & (1 << j)) {
L.insert(sl[i] = sl[i ^ (1 << j)] + nums[j]);
break;
}
}

for (int i = 0; i < (1 << (n - left)); ++i) {
int s = 0;
for (int j = 0; j < (n - left); ++j)
if (i & (1 << j)) {
R.insert(sr[i] = sr[i ^ (1 << j)] + nums[j + left]);
break;
}
}

int ans = INT_MAX;
for (int i : L) {
auto it = R.lower_bound(goal - i);
if (it != R.end())
ans = min(ans, abs(*it + i - goal));
if (it != R.begin())
ans = min(ans, abs(*prev(it) + i - goal));
}

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

class Solution {
public:
int minAbsDifference(vector<int>& nums, int goal) {
int n = nums.size();
int left = (n + 1) / 2;
vector<int> sl(1 << left), sr(1 << (n - left));
for (int i = 0; i < (1 << left); ++i) {
int s = 0;
for (int j = 0; j < left; ++j)
if (i & (1 << j)) {
sl[i] = sl[i ^ (1 << j)] + nums[j];
break;
}
}

for (int i = 0; i < (1 << (n - left)); ++i) {
int s = 0;
for (int j = 0; j < (n - left); ++j)
if (i & (1 << j)) {
sr[i] = sr[i ^ (1 << j)] + nums[j + left];
break;
}
}

int ans = INT_MAX;
sort(sl.begin(), sl.end()), sort(sr.begin(), sr.end());

int l = 0, r = sr.size() - 1;
while (l < sl.size() && r >= 0) {
ans = min(ans, abs(sl[l] + sr[r] - goal));
if (sl[l] + sr[r] > goal)
r--;
else if (sl[l] + sr[r] < goal)
l++;
else
break;
}

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

### # 方法二：子集和枚举的优化

• $[0]$作为初始状态
• 每次，我们使用双指针方法进行$[a_1,a_2,a_3,\dots,a_k]$$[a_1+x,a_2+x,a_3+x,\dots,a_k+x]$两个有序数组的归并

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

class Solution {
vector<int> subset_sum(vector<int> &nums, int l, int r) {
int tot = 1 << (r - l + 1);
vector<int> ans(tot), nxt(tot);
for (int i = l; i <= r; ++i) {
int p0 = 0, p1 = 0, limit = 1 << (i - l);
cout << p0 + p1 << " ";
while (p0 < limit || p1 < limit) {
if (p1 == limit || (p0 < limit && ans[p0] <= ans[p1] + nums[i]))
nxt[p0 + p1] = ans[p0], p0++;
else
nxt[p0 + p1] = ans[p1] + nums[i], p1++;
}
swap(ans, nxt);
}
return ans;
}

public:
int minAbsDifference(vector<int>& nums, int goal) {
int n = nums.size();
int left = (n + 1) / 2;
vector<int> sl = subset_sum(nums, 0, left - 1), sr = subset_sum(nums, left, n - 1);

int ans = INT_MAX;

int l = 0, r = sr.size() - 1;
while (l < sl.size() && r >= 0) {
ans = min(ans, abs(sl[l] + sr[r] - goal));
if (sl[l] + sr[r] > goal)
r--;
else if (sl[l] + sr[r] < goal)
l++;
else
break;
}

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