Tag:隨意刷-已寫過(另解)

Source:

995. Minimum Number of K Consecutive Bit Flips

1.題意:

In: nums,k
Out: 最小Flip次數

由0與1所組成的nums;
k為連續幾bit做一次Flip;
目的為藉由Flip，使得最後nums是皆為1的array。
要連續k bit(s)做Flip才是Flip，無法則視為無解(return -1)。

如果存在無法經由Flip使得最後nums是皆為1的array的情況，
則無解(return -1) aka 沒有完整flip.
Ex:

Input: nums = [1,1,0], k = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2,
we cannot make the array become [1,1,1].

2.思路:

作法:

建立一陣列為diff，標記結束flip的位置為(-1)。

Ex:

3.程式碼:

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        # diff = [] the same size as nums
        # to be flip or not to flip is a question
        n = len(nums)
        diff = [0]*(n)
        flip = 0
        res  = 0
        for i in range(n):
            flip+=diff[i]
            # if flip+nums[i] == 0 => flip=0,nums[i]=0 => %2==0
            # if flip+nums[i] == 2 => flip=1,nums[i]=1 => %2==0
            # if flip+nums[i] == 1 => either flip or nums[i] is 1 => %2!=0
            
            # Need to be flip
            if (flip+nums[i])%2==0:
                if i+k>n:
                    return (-1)
                flip+=1
                if i+k<n:
                    diff[i+k]=(-1)
                res+=1
        return res        

Result:

Track:

Level:Hard

Related Question:

• HackerRank
  • Array Manipulation
  • Difficulty:Hard