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
边解释边帮自己记 不然下次看到大概已经忘记在写什么了
你版大师都早早就解完 剩我垫底了 我好羡慕