LeetCode 解題紀錄 1529. Minimum Suffix Flips

Minimum Suffix Flips - LeetCode

題目

給定一個只包含字元 '0' 與 '1' 的字串 target，另外給定一個字串 s ，長度與 target 一樣但初始為全部都是 '0'，可以在任意位置 i 進行 flip，將 '1' 變為 '0' 或是反過來，在 index 大於 i 的所有字元也都要 flip，要求返回最小的 flip 數目

限制

• 1 ≤ target.length ≤ 10⁵

觀察

• 從 index 小的位置開始 flip，一旦變得跟 target 一樣，我們就不須要去管它了，因此是最佳解，可以使用 Greedy

解法 1 (Greedy)

• 使用一個變數來記住目前位置的字元
• 與 target 下一個字元比較時，如果不同則須 flip 並更新變數內容

class Solution {
    public int minFlips(String target) {
        int next = 0;
        int count = 0;
        for(char c: target.toCharArray()) {
            if(next != c-'0') {
                count++;
                next = 1-next;
            }
        }
        return count;
    }
}

結果

TC：O(n)，SC：O(1)