推 JIWP: 這題有個規則在 11/08 22:41
推 oin1104: 這題太難 放棄 11/08 22:54
推 sixB: 哇靠 龜扣 明天來寫 11/10 02:09
幾百年沒寫了
今天的寫不出來
看答案才知道gray code 這甚麼姬芭==
還有遞迴 這感覺我也想不太到
姆咪
def minimumOneBitOperations(self, n: int) -> int:
# init
bits = []
while n:
bits.append(n&1)
n >>= 1
# brute force
# is_left = (len(stk)!=1) # trick
# while stk:
# if is_left: # do op. 2
# idx_0 = stk.pop()
# if stk and stk[-1] == (idx_0+1):
# stk.pop()
# else:
# stk.append(idx_0+1)
# stk.append(idx_0)
# is_left = False
# else: # do op. 1
# if stk[-1]==0: # [0] is 1
# stk.pop()
# else: # [0] is [0]
# stk.append(0)
# is_left = True
# rets += 1
###############
# while stk:
# if len(stk)>=2 and stk[-2] != (stk[-1]+1):
# # do op.2, 0 to 1
# idx0 = stk.pop()
# stk.append(idx0+1)
# stk.append(idx0)
# rets += 1
# elif len(stk)==2 and stk[-2] == (stk[-1]+1):
# # do op.2, 1 to 0
# idx0 = stk.pop()
# _ = stk.pop()
# stk.append(idx0)
# rets += 1
# else:
# # erase right most bit: costs 2*n-1 steps
# idx0 = stk.pop()
# rets += ((1<<(idx0+1))-1)
################
rets = 0
pre_bit = 0
for i in range(len(bits)-1, -1, -1):
rets += (bits[i]^pre_bit)*(2**i)
pre_bit = (bits[i]^pre_bit)
return rets
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.132.58.28 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1762612838.A.2A3.html