# # Leetcode 第75场双周赛题解

## # Problem A - 转换数字的最少位翻转次数 (opens new window)

### # 方法一：位运算

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

class Solution {
public:
int minBitFlips(int start, int goal) {
return __builtin_popcount(start ^ goal);
}
};

1
2
3
4
5
6

## # Problem B - 数组的三角和 (opens new window)

### # 方法一：模拟

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

impl Solution {
pub fn triangular_sum(mut nums: Vec<i32>) -> i32 {
while nums.len() > 1 {
let n = nums.len();
let mut new_nums = vec![];
for i in 0..n - 1 {
new_nums.push((nums[i] + nums[i + 1]) % 10);
}
nums = new_nums;
}
return nums[0];
}
}

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

### # 方法二：组合数

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

## # Problem C - 选择建筑的方案数 (opens new window)

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

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

using ll = long long;

class Solution {
public:
ll numberOfWays(string s) {
int n = s.size();
ll ans = 0;
ll z = 0, o = 0, zo = 0, oz = 0, zoz = 0, ozo = 0;
for (char c : s) {
int i = c - '0';
if (i == 0) {
zoz += zo;
oz += o;
z++;
} else {
ozo += oz;
zo += z;
o++;
}
}
return zoz + ozo;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

## # Problem D - 构造字符串的总得分和 (opens new window)

### # 方法一：后缀数组

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

#include <atcoder/string>

using ll = long long;

class Solution {
public:
long long sumScores(string s) {
int n = s.size();
auto sa = atcoder::suffix_array(s);
auto lcp = atcoder::lcp_array(s, sa);
int i = 0;
while (sa[i] != 0)
i++;

ll ans = n;
int l = n;
int j = i - 1;
while (j >= 0) {
l = min(l, lcp[j]);
ans += l;
j--;
}

j = i;
l = n;
while (j < n - 1) {
l = min(l, lcp[j]);
ans += l;
j++;
}

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

### # 方法二 Z-算法

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

#include <atcoder/string>

using ll = long long;

class Solution {
public:
long long sumScores(string s) {
auto z = atcoder::z_algorithm(s);
ll ans = 0;
for (int zi : z)
ans += zi;
return ans;
}
};

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