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 3]专案始动(後端篇)

>>:  离职倒数13天:20几岁的时候,羡慕说的一口字正腔圆英文的人。30岁时,佩服的是把自己的意见完整表达的人,用什麽语言都好。

Day 01 HTML<常用标签>

1. 标题标签 <h1> - <h6> (一级标题 - 六级标题) 文字粗体...

CLOUDWAYS 服务器方案评比 - linode / VULTR-HF / Digital Ocean-DP

在 CLOUDWAYS❐ 中,提供了5大云端主机供应商的方案☞ linode 、 VULTR 、 D...

Day21-Go档案处理

前言 Go 语言中的有关档案操作的工具,不可不提到标准函式库里边的io/ioutil 和 os pa...

Day11 Sideproject(作品集) from 0 to 1 - docker化前端篇

docker的使用也是一直都想学了 我们是开始满久才开始套用进来的 因为刚开始都觉得这是一个很难的东...

爬虫crawler -- 虾皮购物

许多厂商、卖家都会想知道自己的商品上架到平台贩售时,商品会排名在哪个位置? 大品牌厂商可能有经费每...