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