DAY 3
1

## Tag:隨意刷-未寫過的

### Source:

995. Minimum Number of K Consecutive Bit Flips

### 1.題意:

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

`k`為連續幾bit做一次Flip;

### 2.思路:

#### 作法:

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

☆ 什麼情況進行Flip?

Or

### 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
``````

#### 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
``````

FRIENDS30

### 1 則留言

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