Re: [閒聊] 每日leetcode

[Meaverzt (單推凜寶)]

https://leetcode.com/problems/minimum-array-end/

題目

做出一個長n的陣列 每一項要嚴格遞增

整個陣列每一項做bitwise and後要是x

輸出要是最小可能的最後一項


思路一：

x放第一項 後面的東西跟x and完還要是x

意思就是x bit是1的地方其他位也要是1

x bit是0的地方就隨便

因為or的性質 A or B 時A裡面的1會被保留

且A or (B+C)會大於等於A or B 大於等於 A

所以讓x+1去or最開始的x n-1次就是答案了

C code

long long minEnd(int n,int x){
long long result=x;
while(n>1){
n--;
result=(result+1)|x;
}
return result;
}
結果跑起來一坨 差點TLE

思路二：
把n也當成一個很多bit的東西
一位一位處理
long long minEnd(int n,int x){
n--;
long long result=x,now=1;
for(--n;n>0;n>>=1,now<<=1){
while(result&now)
now<<=1;
if (n&1)
result|=now;
}
return result;
}

是說到底要怎麼把扣複製到ptt上阿

每次複製上來縮排就不見

對阿
--
幫主可愛
https://i.imgur.com/ezdJwbc.jpeg


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.136.4.97 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731159566.A.B2F.html
推 sustainer123: C 大師 剩我被PY寵壞
python用字串搞超久寫不出這題就放棄了
→ sixB: 1e8剛好跑得完 對ㄚ
→ sixB: 你好厲害
※ 編輯: Meaverzt (101.136.4.97 臺灣), 11/09/2024 21:49:04
推 dont: 大師