题目描述

给你一个以二进制形式表示的数字 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 

算法1

(暴力枚举) $O(n)$

因为数据范围指出字符串最大长度为500,所以不能转换为int来操作，而是使用字符串模拟整个计算过程。
如果是奇数，加1，其过程其实就找到最右边的一个0，把它变成1，而它右边都改为0，例如 “1101”加1，变成”1110”;
如果是偶数，直接弹出最右边的0即可。

时间复杂度

这里时间复杂的不太确定hh，
乍一看，奇数+1操作最坏是$O(n)$的，偶数操作是$O(1)$的，最多执行n次，应该是$O(n ^ 2)$。
其实，每一次奇数+1操作，遍历到的地方都会伴随着一次偶数操作，并且后续操作都不会再访问这些遍历过的地方，所以时间复杂度其实是$O(2n)$。

举例1：
“111111”,奇数操作一次变成”1000000”,遍历了整个数组，复杂度$O(n)$；随后，偶数操作n次去0变为”1”，复杂度为$n \times O(1)$,总时间复杂度为$2 \times n = O(n)$

举例2：
“10001”,奇数操作一次变成”10010”,走了1位，复杂度$O(1)$；随后，偶数操作1次去0变为”1001”，复杂度为$O(1)$；总共将执行n次前面这样的循环，故总时间复杂度为$O(1) \times n = O(n)$

参考文献

C++ 代码

class Solution {
public:
    int numSteps(string s) {
        if (s == "1") return 0;
        int step = 0;
        while (s != "1"){
            if (s.back() == '1') add(s);
            else divide(s);
            // cout << s << endl;
            ++step;
        }

        return step;
    }

    string add(string &s){
        int n = s.size(), j = n - 1;
        while (j >= 0 && s[j] == '1') s[j--] = '0';
        if (j >= 0) s[j] = '1';
        else s = "1" + s;
        return s;
    }

    string divide(string &s){
        s.pop_back();
        return s;
    }
};

算法2

(花哨的做法) $O(n)$

实际上，不需要模拟整个过程，逐一分析每个位置的操作数并相加即可。

时间复杂度

只遍历了一遍数组，显然是$O(n)$的时间复杂度。

参考文献

https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/discuss/564287/C%2B%2BJava-O(n)

C++ 代码

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