原文链接: https://leetcode-cn.com/problems/minimum-number-of-swaps-to-make-the-binary-string-alternating

英文原文

Given a binary string s, return the minimum number of character swaps to make it alternating, or -1 if it is impossible.

The string is called alternating if no two adjacent characters are equal. For example, the strings "010" and "1010" are alternating, while the string "0100" is not.

Any two characters may be swapped, even if they are not adjacent.

 

Example 1:

Input: s = "111000"
Output: 1
Explanation: Swap positions 1 and 4: "111000" -> "101010"
The string is now alternating.

Example 2:

Input: s = "010"
Output: 0
Explanation: The string is already alternating, no swaps are needed.

Example 3:

Input: s = "1110"
Output: -1

 

Constraints:

• 1 <= s.length <= 1000
• s[i] is either '0' or '1'.

中文题目

给你一个二进制字符串 s ，现需要将其转化为一个 交替字符串 。请你计算并返回转化所需的 最小 字符交换次数，如果无法完成转化，返回 -1 。

交替字符串 是指：相邻字符之间不存在相等情况的字符串。例如，字符串 "010" 和 "1010" 属于交替字符串，但 "0100" 不是。

任意两个字符都可以进行交换，不必相邻 。

 

示例 1：

输入：s = "111000"
输出：1
解释：交换位置 1 和 4："111000" -> "101010" ，字符串变为交替字符串。

示例 2：

输入：s = "010"
输出：0
解释：字符串已经是交替字符串了，不需要交换。

示例 3：

输入：s = "1110"
输出：-1

 

提示：

• 1 <= s.length <= 1000
• s[i] 的值为 '0' 或 '1'

通过代码

高赞题解

对于一个size已知的字符串，交替字符串其实只有两种情况

s0（start with 0）：0101010101……
s1（start with 1）：1010101010……

把字符串s和标准答案比较，看看有几个位不一致即可。

n0（not 0）代表与正确的交替字符串对比，有多少个数字本来得是0，但不是0（即要换掉的0的数量）；
同理，n1（not 1），代表有多少个数字不是1（即要换掉的1的数量）。

n0和n1的数字必须一样多，这种情况下，0和1才能互换。

class Solution {
public:
    int minSwaps(string s) {
        int s0n0 = 0, s0n1 = 0;
        int s1n0 = 0, s1n1 = 0;
        for (int c = 0; c < s.size(); c++) {
            if (c % 2 == 0) {
                if (s[c] != '0') s0n0++;    //对于s0来说，这个位得是0
                else s1n1++;                //对于s1来说，这个位得是1
            }
            else {
                if (s[c] != '1') s0n1++;    //对于s0来说，这个位得是1
                else s1n0++;                //对于s1来说，这个位得是0
            }
        }
        if (s0n0 != s0n1 && s1n0 != s1n1) return -1;    // s0 s1 都换不了，返回-1
        if (s0n0 == s0n1 && s1n0 != s1n1) return s0n0;  // s0 换得了，返回s0
        if (s0n0 != s0n1 && s1n0 == s1n1) return s1n0;  // s1 换得了，返回s1
        return min(s0n0, s1n0);                         // 两个都换得了，返回交换次数较少的那个。
    }
};

统计信息

通过次数	提交次数	AC比率
4547	11623	39.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言