https://leetcode.com/problems/minimum-array-end
3133. Minimum Array End
有點難翻 直接講我得到的結論好了
要把 n - 1 的二進位 逐一放進 x 的二進位當中為 0 的位置
如 Example 1: n = 3, x = 4
n - 1 = 2 # 10
x = 4 # 100
x 的最右邊是 0 放入 10 的 0
第二位是 0 放入 10 的 1
沒了所以其他的就不動 變成 110 = 6
Example 2: n = 2, x = 7
n - 1 = 1 # 1
x = 7 # 111
x 的前三位都是 1 所以把 1 放在最左邊 變成 (1 111) = 15
兩個解法 一個字串解 一個位元運算 空間一樣爛 但字串解比位元運算快 為啥
Python Code:
class Solution:
def minEnd(self, n: int, x: int) -> int:
n_rev = f'{n-1:b}'[::-1]
n_len = len(n_rev)
x_rev = f'{x:b}'[::-1]
ans = []
cnt = 0
for i, v in enumerate(x_rev):
if v == '1':
ans.append(v)
elif cnt < n_len:
ans.append(n_rev[cnt]) # x 的部分為 '0' 時 放入 n_rev 的數
cnt += 1
else: # 代表 n_rev 都放完了
ans.append(x_rev[i:][::-1]) # 把當前位置後的反轉加入
break
if cnt < n_len:
ans.append(n_rev[cnt:][::-1]) # 把 x 跑完後剩下的 n 也加進去
ans.reverse()
return int(''.join(ans), 2) # 反轉再轉回十進位
不知道位元運算怎麼搞只好拆成字串
哦 位元運算一樣的Code跑第二次從4ms變0ms了 跟字串解一樣了
Python Code:
class Solution:
def minEnd(self, n: int, x: int) -> int:
z = n - 1
i = 0
while z:
if x & (1 << i) == 0: # 逐位判斷是否為 0
x |= ((z & 1) << i) # 把 z 最右邊的 0/1 放進 x
z >>= 1 # 丟掉一位
i += 1
return x
邊解釋邊幫自己記 不然下次看到大概已經忘記在寫甚麼了
你版大師都早早就解完 剩我墊底了 我好羨慕