推 Smallsh: 大師 05/29 18:53
推 DJYOSHITAKA: 別捲了 05/29 18:56
推 orangeNoob: 別捲了 05/29 19:02
推 sustainer123: 大師 05/29 19:03
1404. Number of Steps to Reduce a Number in Binary Representation to One
有一個二進位的整數以字串形式表示
可以做以下2種處理
1.如果現在的數字是偶數那除以2
2.如果現在的數字是奇數那+1
請問要做幾次操作才可以把這個數字變成1?
思路:
用一個變數acc紀錄有沒有進位
用cur紀錄第1個bit加上acc，會有3種情況0、1、2
如果是2的話acc=1、cur=0
如果是1的話acc=1、cur=1
如果是0的話acc=0、cur=0
當cur=1需要2個步驟:(1)加上1(2)除以2
當cur=0需要1個步驟:(1)除以2
就這樣一直處理到剩最後一個bit
此時如果acc=1，那再加上1個步驟
C code :
int numSteps(char* s) {
int l=strlen(s),ans=0,acc=0;
if (l==1){
return 0;
}
l--;
while (l>0){
int cur=s[l]-48+acc;
if (cur==2){
cur=0;
acc=1;
}else{
acc=cur;
}
ans+=1+cur;
l--;
}
ans+=acc;
return ans;
}
--
https://i.imgur.com/r9FBAGO.gif
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.164.176 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716979988.A.7D9.html