几百年没写了
今天的写不出来
看答案才知道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