iT邦幫忙

2021 iThome 鐵人賽

DAY 3
1
自我挑戰組

FRIENDS系列 第 3

Day 3: LeetCode 995. Minimum Number of K Consecutive Bit Flips

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)。

2.思路:

作法:

flipped 因之前的操作而使得目前為已Flip(1),或是未Flip(0);
isFlipped 記錄每個位置是否被Flip;

☆ 什麼情況進行Flip?

情況1: 原arr記錄值為0,還沒被Flip
Or
情況2: 原arr記錄值為1,但被Flip(所以值為0,需再次被Flip)

3.程式碼:

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        flipped = 0
        isFlipped = [0]*len(nums)
        res = 0
        for i in range(len(nums)):
            if i>=k:
                flipped^=isFlipped[i-k]
            if nums[i]^flipped==0:
                if i+k>len(nums):
                    return (-1)
                flipped^=1
                isFlipped[i]=1
                res+=1
        return res        

Result:

https://ithelp.ithome.com.tw/upload/images/20210918/2011151621cdyqpRSK.png

Level:Hard

Note:

Hard 在於提升效能!
O(n^2)會TLE(Time Limit Exceeded).

  • Ex:

    class Solution:
        def minKBitFlips(self, nums: List[int], k: int) -> int:
            flag = 0
            ans = 0
            for i in range(len(nums)):
                if nums[i] == 0:
                    cnt = 0
                    while (i+cnt)<len(nums):
                        if nums[i+cnt]==1:
                            nums[i+cnt]=0
                        else:
                            nums[i+cnt]=1
                        cnt+=1
                        if cnt>=k:
                            break
                    #print("cnt:",cnt)
                    if cnt!=k:
                        flag = 1
                    else:
                        ans+=1
                #print(nums)
    
            if sum(nums)!=len(nums) or flag==1:
                return (-1)
            return ans            
    

    https://ithelp.ithome.com.tw/upload/images/20210918/20111516ZnzeGMsMOD.png

補充


上一篇
Day 2: LeetCode 978. Longest Turbulent Subarray
下一篇
Day 4: LeetCode 995. Minimum Number of K Consecutive Bit Flips(v2)
系列文
FRIENDS30

1 則留言

1
lhttfy
iT邦新手 4 級 ‧ 2021-09-18 23:17:42

看上去就好Hard

我要留言

立即登入留言