1.题目描述
给你一个仅由字符 '0' 和 '1' 组成的字符串 s 。一步操作中，你可以将任一 '0' 变成 '1' ，或者将 '1' 变成 '0' 。
交替字符串 定义为：如果字符串中不存在相邻两个字符相等的情况，那么该字符串就是交替字符串。例如，字符串 "010" 是交替字符串，而字符串 "0100" 不是。
返回使 s 变成 交替字符串 所需的 最少 操作数。
示例 1：
输入：s = "0100"
输出：1
解释：如果将最后一个字符变为 '1' ，s 就变成 "0101" ，即符合交替字符串定义。
示例 2：
输入：s = "10"
输出：0
解释：s 已经是交替字符串。
示例 3：
输入：s = "1111"
输出：2
解释：需要 2 步操作得到 "0101" 或 "1010" 。
2.解题思路与代码
2.1 解题思路
这道题有点脑筋急转弯的感觉，我们直接从头开始遍历字符串如果第一位是 1 则设置标识位 needZero 为 true ，表示下一位需要是 0；反之第一位是 0 的话 needZero 为 false 表示下一位需要 1。如果下一位与 needZero 所需要的 数字不同，那么需要变换，变换结果加 1，当我们遍历完字符串时得到一个变换次数结果 ans。此时我们得到的 ans 还不是最终答案，因为我们是从第一位是否是 1 开始判断统计的变换次数，还有一种情况就是从第一位是否为 0 开始判断，那么就需要返回从 1 开始的变换次数与从 0 开始的变换次数相比的最小值。而我们得到了从 1 开始的变换次数，其实不需要再从头遍历字符串，以 10010100 为例，我们从第一位是 1 开始变换那么变换的情况如下：
以 1 开始变换
而我们以 0 开头的变换情况如下：
以 0 开始变换
此时可以看到以 1 开头的变换正好是以 0 开头的没有变换的位置，而以 0 开头的变换也是以 1 开头没有变换的位置。因此可以得出结论，最后返回的变换最少次数为以 1 开头的变换次数 ans 与字符串长度减去 ans 的最小值。
2.2 代码
class Solution {
public int minOperations(String s) {
boolean needZero = s.charAt(0) == '1';
int ans = 0;
for (int i = 1; i < s.length(); i++) {
if (needZero) {
ans += s.charAt(i) == '0' ? 0 : 1;
needZero = false;
} else {
ans += s.charAt(i) == '1' ? 0 : 1;
needZero = true;
}
}
return Math.min(ans, s.length() - ans);
}
}
2.3 测试结果
通过测试
测试结果
3.总结
- 统计处以 1 开头的变换次数 ans
- 返回 ans 与字符串长度减去 ans 的最小值
