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
class Solution {
    public int minSwaps(String s) {
        int zeroes = 0, ones = 0;
        char[] sArray = s.toCharArray();
        for (int i = 0; i < sArray.length; i++) {
            if (sArray[i] == '0') {
                zeroes += 1;
            } else {
                ones += 1;
            }
        }
        if (Math.abs(zeroes - ones) > 1)
            return -1;
        if (zeroes > ones)
            return helper(sArray, '0');
        else if (zeroes < ones)
            return helper(sArray, '1');
        else
            return Math.min(helper(sArray, '0'), helper(sArray, '1'));
    }

    private int helper(char[] sArray, char start) {
        int swaps = 0;
        for (int i = 0; i < sArray.length; i++) {
            if (sArray[i] == start && i % 2 != 0) {
                swaps += 1;
            }
        }
        return swaps;
    }
}

思路是这样的. 首先如果1和0的个数相差超过1, 那肯定不能构成alternating. 因为要么0和1的个数一样, 要么就是一个多一个少, 多的那一个只能多1个. 在这种情况下, 如果1多, 那么1肯定打头, 如果0多肯定0打头, 如果二者一样看哪一个打头需要的swaps少就是谁. 然后我们就开始遍历. 如果1打头, 那么0, 2, 4, 6..偶数index必须是1. 如果遇到一个偶数index不是1, 这就说明一定有一个奇数index是1, 为什么? 如果是0的index全是奇数, 那么偶数index应该全是1才对, 而我们现在遇到一个偶数index不是1, 因此肯定有一饿偶数index是0. 此时让它俩交换一下就ok. 假设我们交换了, 但实际不需要. 我们继续走, 如果还遇到一个偶数index不是1, 那肯定还会有一个奇数index是1, 交换即可. 证明方法还是一样. 我们之前的swap都是交换偶数index是0的和奇数index是1的. 交换后二者都到了想去的位置. 因此swap不会改变后面偶数index是0的地方的值, 这样不影响我们继续往后找.

时间复杂度: O(n)
空间复杂度: O(1)