LeetCode 1864. 构成交替字符串需要的最小交换次数_力扣1864题目

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'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

2. 解题

• 0, 1 的个数差不能超过 1 个
• 个数相等的话，最终的字符串 不是 0 开头就是 1 开头
• 不相等的话，多的数字开头
• 依次比较，不相同的位置就是需要调整的

class Solution {
public:
    int minSwaps(string s) {
        int one = 0, zero = 0, n = s.size();
        for(auto c : s)
        {
            if(c == '1') one++;
            else zero++;
        }
        if(abs(one-zero) > 1) return -1; // 不满足
        int a = 0, b = 0;
        if(one == zero)
        {
            for(int i = 0; i < s.size(); ++i)
            {
                if((i&1) && s[i]=='1') a++;
                else if((i&1)==0 && s[i]=='1') b++;
            }
            return min(n/2-a, n/2-b);//需要把所有奇数位的1换掉，或者所有偶数位的1换掉
        }
        else if(one > zero) // 1 多，1开头
        {
            for(int i = 0; i < s.size(); i += 2)
            {
                if(s[i] == '0') a++;
            }
            return a;
        }
        else
        {
            for(int i = 0; i < s.size(); i += 2)
            {
                if(s[i] == '1') a++;
            }
            return a;
        }
    }
};
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
30
31
32
33
34
35
36
37
38

4 ms 6.4 MB C++

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！