将二进制表示减到 1 的步骤数

题目：

给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 1 所需要的步骤数：

• 如果当前数字为偶数，则将其除以 2 。
• 如果当前数字为奇数，则将其加上 1 。

题目保证你总是可以按上述规则将测试用例变为 1 。

示例：

输入：s = "1101"
输出：6
解释："1101" 表示十进制数 13 。
Step 1) 13 是奇数，加 1 得到 14
Step 2) 14 是偶数，除 2 得到 7
Step 3) 7 是奇数，加 1 得到 8
Step 4) 8 是偶数，除 2 得到 4
Step 5) 4 是偶数，除 2 得到 2
Step 6) 2 是偶数，除 2 得到 1

解题方法：

按照题目要求遍历字符串处理就行了：

• 计算当前字符实际大小：k=s[i]-'0'+carry；
• 判断k大小：1. k==1，很明显，按照题目意思，需要加1然后除2，操作步骤为2，且会有一个进位；2. k==2，这个时候最后一位实际是0，有一个进位，对应操作步骤为1；k==0，很简单，没有进位，且操作数为1，最简单的情况；
• 最后就是对字符串第一个字符单独处理。

代码和结果：

class Solution {
public:
    int numSteps(string s) {
        int carry=0;
        int cnt=0;
        for(int i=s.size()-1;i>0;i--)
        {
            int k=s[i]-'0'+carry;
            if(k==1)
            {
                cnt+=2;
                carry=1;
            }
            else if(k==2)
            {
                cnt+=1;
                carry=1;
            }
            else
            {
                cnt++;
            }
        }
        int k=s[0]-'0'+carry;
        if(k==1) return cnt;
        else return cnt+1;
    }

};

运行结果:

最近感觉身心俱疲，确实有点累了，今天睡醒过来，想打游戏，挣扎了半天还是刷起了题，感觉刷题也算是一种消遣吧，虽然有的时候真的觉得刷起来好难，但是做出来的时候还是很开心的。

原题链接：https://leetcode-cn.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/