Re: [閒聊] 每日leetcode
看板Marginalman作者JerryChungYC (JerryChung)時間1年前 (2024/11/10 00:33)推噓0(0推 0噓 1→)留言1則, 1人參與討論串1106/1548 (看更多)
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
邊解釋邊幫自己記 不然下次看到大概已經忘記在寫甚麼了
你版大師都早早就解完 剩我墊底了 我好羨慕
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.45.20.205 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731170029.A.326.html
→
11/10 00:56,
1年前
, 1F
11/10 00:56, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1106 之 1548 篇)：