Day 4: LeetCode 995. Minimum Number of K Consecutive Bit Flips(v2)

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