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

2021-02-14

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

难度简单

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

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

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

示例 1：

1
2
3

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

示例 2：

1
2
3

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

示例 3：

1
2
3

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

提示：

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

因为字符’0’和’1’是交替出现的，所以只有两种情况

字符’1’在奇数位置出现，此时所有的字符’0’在偶数位置出现
字符’1’在偶数位置出现，此时所有的字符’0’在奇数位置出现

只需要比较待判断的字符串$s$与上述两种情况下字符串中不同的字符数量那个小，答案就是哪个。

例1：

"1111"
情况一：字符’1’在奇数位置出现，此时所有的字符’0’在偶数位置出现

"0101"对应位置不同的字符数量为2

情况二：字符’1’在偶数位置出现，此时所有的字符’0’在奇数位置出现

"1010"对应位置不同的字符数量为2

两种情况下不同的字符数量都是2，所以答案是2

例2

"0100"

情况一：字符’1’在奇数位置出现，此时所有的字符’0’在偶数位置出现
"0101"对应位置不同的字符数量为1

情况二：字符’1’在偶数位置出现，此时所有的字符’0’在奇数位置出现

"1010"对应位置不同的字符数量为3

两种情况较小值是1，所以答案应该是1

class Solution {
    public int minOperations(String s) {
        int n = s.length();

        int res = 0;
        int min=Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                char c = '1';
                if (s.charAt(i) != c) res++;
            } else {
                char c = '0';
                if (s.charAt(i) != c) res++;
            }
        }
        min=Math.min(res,min);

        res=0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                char c = '0';
                if (s.charAt(i) != c) res++;
            } else {
                char c = '1';
                if (s.charAt(i) != c) res++;
            }
        }
        min=Math.min(res,min);
        return min;

    }
}

动态规划

每一步都可以做两种选择：换或者不换。

当前字符和前一个字符相同时，换的话那就意味前一个字符不做替换，否则结果错误，操作次数为前一个字符不替换的次数+1；如果不换，那操作次数就和前一个字符替换之后的操作次数相同。
当前字符和前一个字符不同时，不替换就和前一个字符不替换的操作次数相同；如果替换操作次数就等于前面一个字符替换之后的次数+1。

class Solution {
    public int minOperations(String str) {
        char [] s=str.toCharArray();
        int len=s.length;
        int [][]dp=new int[len][2];
            
        dp[0][0]=0;//不做替换
        dp[0][1]=1;//替换
        
        for(int i=1;i<len;i++)
        {
            if(s[i]==s[i-1])
            {
                dp[i][0]=dp[i-1][1];
                dp[i][1]=dp[i-1][0]+1;
            }
            else
            {
                dp[i][0]=dp[i-1][0];
                dp[i][1]=dp[i-1][1]+1;
            }
        }
            
        return Math.min(dp[len-1][0],dp[len-1][1]);
    }
}

作者：yutianzuijin-s
链接：https://leetcode-cn.com/problems/minimum-changes-to-make-alternating-binary-string/solution/dpde-jie-fa-by-yutianzuijin-s-96aw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

作者：yutianzuijin-s 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。