995. Minimum Number of K Consecutive Bit Flips
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)。
flipped 因之前的操作而使得目前为已Flip(1),或是未Flip(0);
isFlipped 记录每个位置是否被Flip;
☆ 什麽情况进行Flip?
情况1: 原arr记录值为0,还没被Flip
Or
情况2: 原arr记录值为1,但被Flip(所以值为0,需再次被Flip)
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
Hard
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
>>: 离职倒数13天:20几岁的时候,羡慕说的一口字正腔圆英文的人。30岁时,佩服的是把自己的意见完整表达的人,用什麽语言都好。
1. 标题标签 <h1> - <h6> (一级标题 - 六级标题) 文字粗体...
在 CLOUDWAYS❐ 中,提供了5大云端主机供应商的方案☞ linode 、 VULTR 、 D...
前言 Go 语言中的有关档案操作的工具,不可不提到标准函式库里边的io/ioutil 和 os pa...
docker的使用也是一直都想学了 我们是开始满久才开始套用进来的 因为刚开始都觉得这是一个很难的东...
许多厂商、卖家都会想知道自己的商品上架到平台贩售时,商品会排名在哪个位置? 大品牌厂商可能有经费每...