来源第 153 场双周赛 Q2难度中等分数1729
题目描述
给你一个长度为 n 的二进制字符串 s，其中：
'1' 表示一个 活跃 区段。'0' 表示一个 非活跃 区段。
你可以执行 最多一次操作 来最大化 s 中的活跃区段数量。在一次操作中，你可以：
- 将一个被
'0' 包围的连续 '1' 区块转换为全 '0'。 - 然后，将一个被
'1' 包围的连续 '0' 区块转换为全 '1'。
返回在执行最优操作后，s 中的 最大 活跃区段数。
注意：处理时需要在 s 的两侧加上 '1' ，即 t = '1' + s + '1'。这些加上的 '1' 不会影响最终的计数。
示例 1：
输入： s = "01"
输出： 1
解释：
因为没有被 '0' 包围的 '1' 区块，因此无法进行有效操作。最大活跃区段数为 1。
示例 2：
输入： s = "0100"
输出： 4
解释：
- 字符串
"0100" → 两端加上 '1' 后得到 "101001" 。 - 选择
"0100"，"101001" → "100001" → "111111" 。 - 最终的字符串去掉两端的
'1' 后为 "1111" 。最大活跃区段数为 4。
示例 3：
输入： s = "1000100"
输出： 7
解释：
- 字符串
"1000100" → 两端加上 '1' 后得到 "110001001" 。 - 选择
"000100"，"110001001" → "110000001" → "111111111"。 - 最终的字符串去掉两端的
'1' 后为 "1111111"。最大活跃区段数为 7。
示例 4：
输入： s = "01010"
输出： 4
解释：
- 字符串
"01010" → 两端加上 '1' 后得到 "1010101"。 - 选择
"010"，"1010101" → "1000101" → "1111101"。 - 最终的字符串去掉两端的
'1' 后为 "11110"。最大活跃区段数为 4。
提示：
1 <= n == s.length <= 105s[i] 仅包含 '0' 或 '1'
解法
方法一：贪心 + 双指针
思考
一次交易把一段 \(1\) 两侧的 \(0\) 段一起翻成 \(1\)，收益是这两段 \(0\) 的长度之和，再加原本所有 \(1\)。 \(n\le 10^5\)，按段扫描。
不相邻的两段 \(0\) 无法被同一次交易合并，因此只需相邻的 \(0\) 段对。
双指针切出 runs： \(1\) 的长度直接累加；相邻两段 \(0\) 用 \(\textit{pre}+\textit{cur}\) 更新 \(mx\)。答案为 \(1\) 的总数加 \(mx\)。
题目实际上等价于求字符串 \(s\) 中，字符 '1' 的数量，再加上相邻两个连续的字符 '0' 串中 `'0' 的最大数量。
因此，我们可以使用双指针来遍历字符串 \(s\)，用一个变量 \(mx\) 来记录相邻两个连续的字符 '0' 串中 '0' 的最大数量。我们还需要一个变量 \(\textit{pre}\) 来记录上一个连续的字符 '0' 串的数量。
每一次，我们统计当前连续相同字符的数量 \(\textit{cnt}\)，如果当前字符为 '1'，则将 \(\textit{cnt}\) 加入到答案中；如果当前字符为 '0'，则将 \(mx\) 更新为 \(mx = \max(mx, \textit{pre} + \textit{cnt})\)，并将 \(\textit{pre}\) 更新为 \(\textit{cnt}\)。最后，我们将答案加上 \(mx\) 即可。
时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。其中 \(n\) 为字符串 \(s\) 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution:
def maxActiveSectionsAfterTrade(self, s: str) -> int:
n = len(s)
ans = i = 0
pre, mx = -inf, 0
while i < n:
j = i + 1
while j < n and s[j] == s[i]:
j += 1
cur = j - i
if s[i] == "1":
ans += cur
else:
mx = max(mx, pre + cur)
pre = cur
i = j
ans += mx
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 | class Solution {
public int maxActiveSectionsAfterTrade(String s) {
int n = s.length();
int ans = 0, i = 0;
int pre = Integer.MIN_VALUE, mx = 0;
while (i < n) {
int j = i + 1;
while (j < n && s.charAt(j) == s.charAt(i)) {
j++;
}
int cur = j - i;
if (s.charAt(i) == '1') {
ans += cur;
} else {
mx = Math.max(mx, pre + cur);
pre = cur;
}
i = j;
}
ans += mx;
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 | class Solution {
public:
int maxActiveSectionsAfterTrade(std::string s) {
int n = s.length();
int ans = 0, i = 0;
int pre = INT_MIN, mx = 0;
while (i < n) {
int j = i + 1;
while (j < n && s[j] == s[i]) {
j++;
}
int cur = j - i;
if (s[i] == '1') {
ans += cur;
} else {
mx = std::max(mx, pre + cur);
pre = cur;
}
i = j;
}
ans += mx;
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | func maxActiveSectionsAfterTrade(s string) (ans int) {
n := len(s)
pre, mx := math.MinInt, 0
for i := 0; i < n; {
j := i + 1
for j < n && s[j] == s[i] {
j++
}
cur := j - i
if s[i] == '1' {
ans += cur
} else {
mx = max(mx, pre+cur)
pre = cur
}
i = j
}
ans += mx
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | function maxActiveSectionsAfterTrade(s: string): number {
let n = s.length;
let [ans, mx] = [0, 0];
let pre = Number.MIN_SAFE_INTEGER;
for (let i = 0; i < n;) {
let j = i + 1;
while (j < n && s[j] === s[i]) {
j++;
}
let cur = j - i;
if (s[i] === '1') {
ans += cur;
} else {
mx = Math.max(mx, pre + cur);
pre = cur;
}
i = j;
}
ans += mx;
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | impl Solution {
pub fn max_active_sections_after_trade(s: String) -> i32 {
let (ones_count, _, max_gain) = s.as_bytes().chunk_by(|left, right| left == right).fold(
(0, i32::MIN, 0),
|(ones_count, previous_zeros, max_gain), block| {
let block_length = block.len() as i32;
if block[0] == b'1' {
(ones_count + block_length, previous_zeros, max_gain)
} else {
(
ones_count,
block_length,
max_gain.max(previous_zeros + block_length),
)
}
},
);
ones_count + max_gain
}
}
|