LeetCode算法：1758. 生成交替二进制字符串的最少操作数

1758. 生成交替二进制字符串的最少操作数

给你一个仅由字符 ‘0’ 和 ‘1’ 组成的字符串 s 。一步操作中，你可以将任一 ‘0’ 变成 ‘1’ ，或者将 ‘1’ 变成 ‘0’ 。

交替字符串 定义为：如果字符串中不存在相邻两个字符相等的情况，那么该字符串就是交替字符串。例如，字符串 “010” 是交替字符串，而字符串 “0100” 不是。

返回使 s 变成 交替字符串 所需的 最少 操作数。

示例 1：

输入：s = "0100"
输出：1
解释：如果将最后一个字符变为 '1' ，s 就变成 "0101" ，即符合交替字符串定义。
1
2
3

示例 2：

输入：s = "10"
输出：0
解释：s 已经是交替字符串。
1
2
3

示例 3：

输入：s = "1111"
输出：2
解释：需要 2 步操作得到 "0101" 或 "1010" 。
1
2
3

提示：

1 <= s.length <= 104
s[i] 是 '0' 或 '1'
1
2

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-changes-to-make-alternating-binary-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法1：暴力解法

思路

判断输入开头是否为 ‘1’, 计算交替变回操作的次数;
判断输入开头是否为 ‘0’, 计算交替变回操作的次数;
比较两次变换的次数谁最小, 取最小的值

代码实现

public class MinimumChangesToMakeAlternatingBinaryString {

    public int minOperations(String s) {
        char[] a = new char[]{'0', '1'};
        char[] chars0 = s.toCharArray();
        int minOperations0 = 0;
        int index = 0;
        for (int i = 0; i < chars0.length; i++) {
            final int k = index % 2;
            if (chars0[i] != a[k]) {
                chars0[i] = a[k];
                minOperations0++;
            }
            index++;
        }
        char[] chars1 = s.toCharArray();
        int minOperations1 = 0;
         index =1;
        for (int i = 0; i < chars1.length; i++) {
            final int k = index % 2;
            if (chars1[i] != a[k]) {
                chars1[i] = a[k];
                minOperations1++;
            }
            index++;
        }
        return Math.min(minOperations0, minOperations1);
    }
}
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

方法2：找规律

思路

分析：
当输入开头为 0100 时, 从0开始为01为1， 10的次数为0，总长度为4，最少需要变换 (4-1*2)/2=1 次

当输入开头为 01 时, 从0开始为01为1， 10的次数为0，总长度为2，最少需要变换 (2-1*2)/2=0 次

当输入开头为 1111 时, 从0开始为01为0， 10的次数为0，总长度为4，最少需要变换 (4-0*2)/2=1 次

当输入开头为 10010100 时, 从0开始为01为2， 10的次数为1，总长度为8，最少需要变换 (8-1*2)/2=3 次

当输入开头为 00000000 时, 从0开始为01为0， 10的次数为0，总长度为8，最少需要变换 (8-0*2)/2=4 次

当输入开头为 00101010 时, 从0开始为01为0， 10的次数为3，总长度为8，最少需要变换 (8-3*2)/2=1 次

规律总结：

• 1、当01的次数和10的次数均等于0时，最少交换次数为：长度n/2;

• 2、当01的次数大于10的次数且10的次数等于0是时，最少交换次数为：长度(n/2- [01]*2)/2;

• 3、当01的次数小于10的次数且01的次数等于0是时，最少交换次数为：长度(n/2- [10]*2)/2;

• 4、当01的次数大于10的次数且01和10的次数均大于0是时，最少交换次数为：长度(n/2- max([10],[10]) + min([10],[10]);

• 5、当字符串长度为奇数时，判断最后一个字符是否与交替操作之后的第一个字符相同，如下：

  • 开头为 0 与最后一个字符不同，则在上述长度+1;

  • 开头为 1 与最后一个字符不同，则在上述长度+1;

最终总结：最少的操作次数为：(n/2- max([10],[10]) + min([10],[10])

代码实现

public class MinimumChangesToMakeAlternatingBinaryString {

    public int minOperations2(String s) {
        int count01 = 0;
        int count10 = 0;
        final int length = s.length();
        for (int i = 0; i < length; i += 2) {
            if (s.startsWith("01", i)) {
                count01++;
            } else if (s.startsWith("10", i)) {
                count10++;
            }
        }
        int lastOperation = 0;
        if (length % 2 == 1) {
            if (count01 > count10 && s.charAt(length - 1) == '1') {
                lastOperation = 1;
            }
            if (count01 < count10 && s.charAt(length - 1) == '0') {
                lastOperation = 1;
            }
        }
        return lastOperation + length / 2 - Math.max(count01, count10)  + Math.min(count01, count10) ;
    }
}
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

方法3：官方解法模拟

思路

根据题意，经过多次操作，ss 可能会变成两种不同的交替二进制字符串，即：

• 开头为 00，后续交替的字符串；
• 开头为 11，后续交替的字符串。

注意到，变成这两种不同的交替二进制字符串所需要的最少操作数加起来等于 ss 的长度，我们只需要计算出变为其中一种字符串的最少操作数，就可以推出另一个最少操作数，然后取最小值即可。

代码实现

class Solution {
    public int minOperations(String s) {
        int cnt = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c != (char) ('0' + i % 2)) {
                cnt++;
            }
        }
        return Math.min(cnt, s.length() - cnt);
    }
}
// 作者：LeetCode-Solution
// 链接：https://leetcode.cn/problems/minimum-changes-to-make-alternating-binary-string/solution/sheng-cheng-jiao-ti-er-jin-zhi-zi-fu-chu-91c5/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

方法4：图解LeetCode

解题思路

根据题意，我们可以先以第1个字符作为“基础字符”（即：不翻转），然后判断下一个字符是否满足与前一个字符相同，如果相同，则翻转数加1，否则不需要增加翻转数。并且，通过下面图例，我们可以看到如下规律，即：

如果不翻转第1个字符，那么成为“交替字符串”的最终翻转数结果为——N；
如果翻转第1个字符，那么成为“交替字符串”的最终翻转数结果为——s.length()-N；

所以，根据以上规律，我们先以第1个字符作为“基础字符”，去遍历字符串s的所有字符，可以计算出成为交替字符串的翻转次数N。那么，如果第1个字符我们不作为“基础字符”（即：翻转）的话，成为交替字符串需要翻转的次数就为s.length()-N。最后，我们返回N与s.length()-N之间最小的那个值即可。

代码实现

class Solution {
    public int minOperations(String s) {
        int result = 0;
        char[] sc = s.toCharArray();
        char preChar = sc[0];
        for (int i = 1; i < sc.length; i++) {
            if (preChar == sc[i]) {
                result++;
                preChar = (char) (preChar ^ 1);
            } else {
                preChar = sc[i];
            }
        }
        return Math.min(result, s.length() - result);
    }
}

// 作者：muse-77
// 链接：https://leetcode.cn/problems/minimum-changes-to-make-alternating-binary-string/solution/-by-muse-77-gwcw/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21