3191. Minimum Operations to Make Binary Array Elements Equal to One I - Medium

前往題目

想法

• 或許可以用sliding window但對於如何判斷是否應該翻轉bit毫無想法

思路

運用Greedy概念，只需要專注在當前的數字，0就翻轉，否則不管，如果valid最後一定全部都是1，否則會有一或兩個0

1. 三個為一個window，第一個為基準判斷是否翻轉
2. 每次翻轉紀錄次數
3. 結束後，如果最後兩位有1或2個0就是invalid

對於如何確定這是可行的並不清楚…但應該可以看作是每次檢查完一位數字後就相當於把他排除了，就剩下子問題

Code

class Solution {
    public int minOperations(int[] nums) {
        int res = 0;

        // Greedy, flip each current value
        for (int i = 0; i < nums.length - 2; ++i) {
            // When 0, flip the consecutive 3 values
            if (nums[i] == 0) {
                flip(nums, i);
                flip(nums, i + 1);
                flip(nums, i + 2);
                ++res;
            }
            // Otherwise ignore
        }

        if (nums[nums.length - 1] == 0 || nums[nums.length - 2] == 0) return -1;

        return res;
    }

    private int[] flip(int[] nums, int i) {
        if (nums[i] == 0) {
            nums[i] = 1;
        } else {
            nums[i] = 0;
        }
        return nums;
    }
}