[LeetCode] 1404. Number of Steps to Reduce a Number in Binary Representation to One

Given a number s in their binary representation. 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's guaranteed that you can always reach to one for all testcases.

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'

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

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

既然处理的是一个以字符串表示的二进制数字，那么我们就按照规则和需求进行处理。最终的目的是把这个二进制数变成1，所以我们从右往左扫描input字符串，如果遇到0则可以除以2，这里除以2相当于是位运算里的右移一位，需要一步；如果遇到1，则对其 + 1并且再除以2，这里需要两步。在计算的过程中我们需要记录进位carry。

此时我们有一个已经用到的步数step和一个进位carry。

如果当前位置上是0且carry = 0，则可以除以2，这里花费一步

如果当前位置上是0且carry = 1，则需要花费两步，一步是+1，另一步是除以2；此时carry仍然是1

如果当前位置上是1且carry = 0，则需要花费两步，一步是+1，另一步是除以2；此时carry是1

如果当前位置上是1且carry = 1，则可以除以2，这里花费一步

注意题目条件有这一条，s[0] == '1'，所以第一位要特判，从右往左扫描的时候要在第一位停下。最后看一下，如果依然进位carry = 0，则已经满足题意；如果进位carry = 1，则加上进位之后s[0] = 0，此时要变回1则还需要再 + 1。

时间O(n)

空间O(1)

Java实现

class Solution {
    public int numSteps(String s) {
        int step = 0;
        // corner case
        if (s.length() == 1) {
            if (s.charAt(0) == '0') {
                step++;
            }
            return step;
        }

        // normal case
        int carry = 0;
        for (int i = s.length() - 1; i > 0; i--) {
            // '0'
            if (s.charAt(i) == '0') {
                if (carry == 0) {
                    // 右移一步
                    step++;
                } else {
                    step += 2;
                    carry = 1;
                }
            }
            // '1'
            else {
                if (carry == 0) {
                    step += 2;
                } else {
                    step++;
                }
                carry = 1;
            }
        }
        return step + carry;
    }
}

LeetCode 题目总结