leetcode 1404. 将二进制表示减到 1 的步骤数 中等

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

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

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

题目保证你总是可以按上述规则将测试用例变为 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

示例 2：

输入：s = "10"输出：1解释："10" 表示十进制数 2 。 Step 1) 2 是偶数，除 2 得到 1

示例 3：

输入：s = "1"输出：0

提示：

• 1 <= s.length <= 500
• s由字符'0'或'1'组成。
• s[0] == '1'

分析：模拟整个过程，从后向前遍历，如果 s[i] 为 0，则直接除以 2，次数 cnt++；如果 s[i] 为 1，从 i 开始向前找到连续的 1 的个数，代表需要右移的次数，同时额外补上 +1 的次数，并把前一位置 0，重复过程直到 i 等于 0。

class Solution { public: int numSteps(string s) { int cnt=0; for(int i=s.length()-1;i>0;) { while(i>=0&&s[i]=='0') cnt++,i--; if(i==0)break; int temp=0; while(i>=0&&s[i]=='1') temp++,i--; cnt+=temp+1; if(i>=0)s[i]='1'; } if(s[0]=='0')cnt++; return cnt; } };