# # Leetcode 第280场周赛题解

## # Problem A - 得到 0 的操作数 (opens new window)

### # 方法一：用辗转相除代替辗转相减

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

class Solution:
def countOperations(self, num1: int, num2: int) -> int:
if num1 == 0 or num2 == 0:
return 0
elif num1 < num2:
return self.countOperations(num2, num1)
else:
return self.countOperations(num2, num1 % num2) + num1 // num2

1
2
3
4
5
6
7
8

## # Problem B - 使数组变成交替数组的最少操作数 (opens new window)

### # 方法一：计数+贪心

• 时间复杂度 $\mathcal{O}(N\log N)$，如果将寻找前二大频率从排序改为线性寻找，则时间复杂度为 $\mathcal{O}(N)$
• 空间复杂度 $\mathcal{O}(N)$

from collections import Counter

class Solution:
def minimumOperations(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return 0

ec = Counter(nums[::2])
oc = Counter(nums[1::2])

e = sorted([(ec[key], key) for key in ec], reverse=True)
o = sorted([(oc[key], key) for key in oc], reverse=True)

ans = n
for i in range(min(2, len(e))):
for j in range(min(2, len(o))):
if e[i][1] != o[j][1]:
ans = min(ans, n - e[i][0] - o[j][0])
else:
ans = min(ans, n - max(e[i][0], o[j][0]))

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

## # Problem C - 拿出最少数目的魔法豆 (opens new window)

### # 方法一：排序

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

class Solution:
def minimumRemoval(self, beans: List[int]) -> int:
beans.sort()
s = sum(beans)
n = len(beans)
ans = s
for i, b in enumerate(beans):
ans = min(ans, s - b * (n - i))
return ans

1
2
3
4
5
6
7
8
9

## # Problem D - 数组的最大与和 (opens new window)

### # 方法一：状态压缩动态规划（三进制记录篮子状态，枚举数字）

• 时间复杂度$\mathcal{O}(NS\cdot3^S)$
• 空间复杂度$\mathcal{O}(3^S)$

class Solution {
public:
int maximumANDSum(vector<int>& nums, int s) {
int n = nums.size();
vector<int> t(s + 1);
t[0] = 1;
for (int i = 1; i <= s; ++i)
t[i] = t[i - 1] * 3;

vector<int> dp(t[s], -1);
dp[0] = 0;

for (int num : nums) {
for (int i = t[s] - 1; i >= 0; --i) {
if (dp[i] == -1)
continue;

int x = i;
for (int j = 0; j < s; ++j) {
if (x % 3 < 2)
dp[i + t[j]] = max(dp[i + t[j]], dp[i] + (num & (j + 1)));
x /= 3;
}
}
}

return *max_element(dp.begin(), dp.end());
}
};

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

### # 方法二：状态压缩动态规划（二进制记录数字状态，枚举篮子）

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

class Solution {
public:
int maximumANDSum(vector<int>& nums, int numSlots) {
int n = nums.size();
int ans = 0;

vector<int> dp(1 << n, -1);
dp[0] = 0;
for (int s = 1; s <= numSlots; ++s) {
for (int i = (1 << n) - 1; i >= 0; --i) {
if (dp[i] == -1)
continue;
for (int j = 0; j < n; ++j) {
if (i & (1 << j))
continue;
int msk = i ^ (1 << j);
dp[msk] = max(dp[msk], dp[i] + (nums[j] & s));
for (int k = j + 1; k < n; ++k) {
if (i & (1 << k))
continue;
dp[msk ^ (1 << k)] = max(dp[msk ^ (1 << k)], dp[i] + (nums[j] & s) + (nums[k] & s));
}
}
}
}

return dp.back();
}
};

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

impl Solution {
pub fn maximum_and_sum(nums: Vec<i32>, num_slots: i32) -> i32 {
let n = nums.len();
let mut ans = 0;
let mut dp = vec![-1; 1 << n];
dp[0] = 0;
for s in 1..=num_slots {
for i in (0..(1<<n)).rev() {
if dp[i] == -1 {
continue;
}

for j in 0..n {
if (i & (1 << j)) != 0 {
continue;
}

let msk = i ^ (1 << j);
dp[msk] = dp[msk].max(dp[i] + (nums[j] & s));

for k in j+1..n {
if (i & (1 << k)) != 0 {
continue;
}
dp[msk ^ (1 << k)] = dp[msk ^ (1 << k)].max(dp[i] + (nums[j] & s) + (nums[k] & s));
}
}
}
}

return dp[(1 << n) - 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
28
29
30
31
32
33

class Solution {
public:
int maximumANDSum(vector<int>& nums, int numSlots) {
int n = nums.size();
int ans = 0;

vector<int> dp(1 << n, -1);
dp[0] = 0;
for (int s = 1; s <= numSlots; ++s) {
for (int i = (1 << n) - 1; i >= 0; --i) {
if (dp[i] == -1 || (__builtin_popcount(i) + (numSlots - s + 1) * 2 < n))
continue;
for (int j = 0; j < n; ++j) {
if (i & (1 << j))
continue;
int msk = i ^ (1 << j);
dp[msk] = max(dp[msk], dp[i] + (nums[j] & s));
for (int k = j + 1; k < n; ++k) {
if (i & (1 << k))
continue;
dp[msk ^ (1 << k)] = max(dp[msk ^ (1 << k)], dp[i] + (nums[j] & s) + (nums[k] & s));
}
}
}
}

return dp.back();
}
};

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

impl Solution {
pub fn maximum_and_sum(nums: Vec<i32>, num_slots: i32) -> i32 {
let n = nums.len();
let mut ans = 0;
let mut dp = vec![-1; 1 << n];
dp[0] = 0;
for s in 1..=num_slots {
for i in (0..(1<<n)).rev() {
if dp[i] == -1 || (i.count_ones() as i32 + (num_slots - s + 1) * 2 < n as i32) {
continue;
}

for j in 0..n {
if (i & (1 << j)) != 0 {
continue;
}

let msk = i ^ (1 << j);
dp[msk] = dp[msk].max(dp[i] + (nums[j] & s));

for k in j+1..n {
if (i & (1 << k)) != 0 {
continue;
}
dp[msk ^ (1 << k)] = dp[msk ^ (1 << k)].max(dp[i] + (nums[j] & s) + (nums[k] & s));
}
}
}
}

return dp[(1 << n) - 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
28
29
30
31
32
33