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

英文原文

Given the binary representation of an integer as a string s, return the number of steps to reduce it to 1 under the following rules:

• If the current number is even, you have to divide it by 2.

• If the current number is odd, you have to add 1 to it.

It is guaranteed that you can always reach one for all test cases.

 

Example 1:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.  

Example 2:

Input: s = "10"
Output: 1
Explanation: "10" corressponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.  

Example 3:

Input: s = "1"
Output: 0

 

Constraints:

• 1 <= s.length <= 500
• s consists of characters '0' or '1'
• s[0] == '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'

通过代码

高赞题解

解题思路

对字符串找规律:

• 如果末位是0（偶数），则直接右移（除2）
• 如果末位是1（奇数），则需要加一，反应在二进制串上相当于不断进位，举几个例子
  • 11001 -> 11010 -> 1101
  • 1011 -> 1100 -> 110 -> 11
  • 从以上例子可以看出，我们可以做的一个阶段性操作为：加1后，将末尾的0都去掉 ，总共需要的步骤数为：
    • 1(进位) + 当前位起连续的1的个数(相当于进位后末尾新产生多少个0)

代码

class Solution {
public:
    int numSteps(string s) {
        int idx = s.size() - 1;
        int ans = 0;
        while(idx > 0){//第一位最后肯定剩1，不另计算
            if(s[idx] == '0'){
                ans++;
                idx--;
            }
            else{
                ans++;//进位的+1
                while(idx >= 0 && s[idx] == '1'){//进位后，连续的1产生连续的0
                    ans++;
                    idx--;
                }
                if(idx > 0)
                    s[idx] = '1';
            }
        }
        return ans;
    }
};

统计信息

通过次数	提交次数	AC比率
7454	15110	49.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言