使二进制字符串字符交替的最少反转次数
难度:
标签:
题目描述
代码结果
运行时间: 148 ms, 内存: 16.4 MB
/*
* 思路:
* 和Java的思路一致,但使用Java Stream API来实现
* 使用IntStream来处理字符串索引,然后使用filter过滤不符合交替要求的字符
*/
import java.util.stream.IntStream;
public class Solution {
public int minFlips(String s) {
int n = s.length();
long count0 = IntStream.range(0, n).filter(i -> s.charAt(i) != (i % 2 == 0 ? '0' : '1')).count();
long count1 = IntStream.range(0, n).filter(i -> s.charAt(i) != (i % 2 == 0 ? '1' : '0')).count();
return (int) Math.min(count0, count1);
}
}
解释
方法:
首先,题解构造了一个理想的交替二进制字符串 `_s`,长度与 `s` 相同,开始以 '10' 交替。接着,题解通过遍历字符串 `s` 与 `_s` 对比,计算与 `_s` 匹配的字符数 `count`。如果 `s` 的长度 `n` 是偶数,直接返回 `min(count, n-count)`,因为可以通过 `count` 次反转得到 `_s` 或者通过 `n-count` 次反转得到 `_s` 的反向交替字符串。如果 `n` 是奇数,通过滑动窗口方式不断旋转字符串并计算最小反转次数,对于每个字符,根据它的值修改 `count`,并不断更新结果 `res` 为最小反转次数。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在构造理想的交替字符串 `_s` 时使用了 '10' 作为重复的基本单元,而不是 '01'?
▷🦆
在偶数长度的字符串中,为什么直接使用 `min(count, n - count)` 可以得到最小的反转次数?
▷🦆
对于奇数长度的字符串,旋转操作是如何在算法中体现的,它具体影响了哪些变量的状态?
▷🦆
算法中对于更新 `count` 的逻辑 `count = n - (count - 1)` 和 `count = n - (count + 1)` 是如何得出的?这里的逻辑是否适用于所有情况?
▷