推 karin1104: 你是大師 07/29 23:16
→ DJYOMIYAHINA: 其實先更新bit_mem，就也不用做xor了，比較直觀 07/29 23:17
bit-op我真的是肏== 真的想去黑暗一趟了
一個方法是sliding window
maintain window內各bit位置的one-count
從後面做回來
每次loop縮window，當縮到idx會讓某bit位置的one-count==0，則r=idx+1
window的大小就是那個位置的最小subarr長度了
另一個方法是記下各bit位置上次出現1的idx
一樣從後面做回來
nums[i]^target後，等於1的bit位置就是需要從nums[i]以後去取1的位置
遍歷這些bit位置，找出上次出現1最遠的位置，就會是最小subarr的右端了
def smallestSubarrays(self, nums: List[int]) -> List[int]:
target = 0
rets = [-1 for _ in range(len(nums))]
bit_mem = [999999 for _ in range(32)]
for i in range(len(nums)-1, -1, -1):
target = target | nums[i]
tmp = target ^ nums[i]
j = 0
cur_len = 1
while tmp>0:
if tmp&1==1:
cur_len = max(cur_len, bit_mem[j]-i+1)
tmp = tmp>>1
j += 1
rets[i] = cur_len
tmp = nums[i]
j = 0
while tmp>0:
if tmp&1==1:
bit_mem[j]=min(bit_mem[j], i)
j += 1
tmp = tmp>>1
return rets
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.132.58.28 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1753802165.A.396.html