Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 1888. Minimum Number of Flips to Make the Binary String Alternating

---

參考資訊：
https://algo.monster/liteproblems/1888

題目：


方法：
1. 算出需要翻轉的次數
2. 將s[0]移到尾端
3. 算出需要翻轉的次數(移動後)
4. 全部都移過一次後，找出最小的翻轉次數

解答：

class Solution {
public:
    int minFlips(string s) {
        int r = 0;
        int flip = 0;
        int size = s.size();

        for (int i = 0; i < size; i++) {
            flip += (s[i] != "01"[i & 1]) ? 1 : 0;
        }
        r = min(flip, size - flip);

        for (int i = 0; i < size; i++) {
            if (s[i] != "01"[i & 1]) {
                flip -= 1;
            }

            if (s[i] != "01"[(i + size) & 1]) {
                flip += 1;
            }

            r = min(r, min(flip, size - flip));
        }

        return r;
    }
};