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'

方法一：模拟

我们可以直接模拟题目中的过程：

• 如果当前数字为偶数，则将其除以 2。当 s 为二进制表示时，就相当于去除末尾的 0。例如当 s = (11010)_2 时，除以 2 得到 (1101)_2；

• 如果当前数字为奇数，则将其加上 1。当 s 为二进制表示时，就相当于对 1 加上 1。例如当 s = (10011)_2 时，加上 1 得到 (10100)_2。特别地，如果 s 的二进制表示只包含 1，那么加上 1 之后会产生额外的进位，需要注意。例如当 s=(1111)_2 时，加上 1 会得到 (10000)_2。

因此我们可以使用字符串直接模拟这两种操作。由于在 C++ 语言中的字符串是可变字符串，而 Python 和 Java 语言中的字符串不可变，因此下面只给出 C++ 语言的代码。

[sol1-C++]

class Solution {
public:
    int numSteps(string s) {
        int steps = 0;
        while (s != "1") {
            ++steps;
            if (s.back() == '0') {
                // 偶数的情况
                s.pop_back();
            }
            else {
                // 第一步：找出最低位的 0
                // 第二步：把这个 0 变成 1，并将后面所有的 1 变成 0，这样就实现了 +1
                // 特别地，如果 s 中全是 1，那么会有额外的进位
                for (int i = s.size() - 1; i >= 0; --i) {
                    if (s[i] == '1') {
                        s[i] = '0';
                        if (i == 0) {
                            s = "1" + s;
                            break;
                        }
                    }
                    else {
                        s[i] = '1';
                        break;
                    }
                }
            }
        }
        return steps;
    }
};

复杂度分析

• 时间复杂度：O(N)，其中 N 是字符串 s 的长度。我们使用均摊分析的方法计算时间复杂度：对于字符串中的一个 1，它的「命运」是在某一时刻由于加一操作变成了 0，并在接下来的某一次除二操作中被丢弃；而对于字符串中的一个 0，它的「命运」要么是直接在某一次除二操作中被丢弃，要么是由于加一操作的进位变成了 1，接下来重复作为 1 的「命运」。因此，字符串 s 中的任意一个字符不会被处理超过三次，即时间复杂度为 O(3N) = O(N)。

• 空间复杂度：O(1)。因为我们直接在原字符串上进行操作，因此没有使用到额外的空间。

方法二：遍历计数

在方法一的「复杂度分析」部分，我们其实已经有了一些优化的思路。具体地，我们举一个例子来看看每个字符的「命运」到底是什么。

我们以字符串 1100011100 为例：

• 一开始最低位为 0，这些 0 的「命运」就是被除二操作删除。我们通过两次除二的操作，得到字符串 11000111；

• 现在的最低位为 1，这些 1 的「命运」就是被加一操作变成 0 再被删除。我们通过一次加一操作将字符串变为 11001000，再进行三次除二操作，得到 11001。这一步的操作次数为 4；

• 现在的最低位为 1，我们通过两次操作（一次加一，一次除二）将字符串变为 1101。最低位仍然为 1，我们通过两次操作将字符串变为 111；最低位还是 1（思考一下，为什么最低位总是 1？除了一开始的情况，最低位可能为 0 吗？），我们通过一次加一操作将字符串变为 1000，产生了额外的进位，再通过三次除二操作将字符串变为 1。

通过上面的例子，我们可以归纳出每一个字符的「命运」以及需要的步骤数：

• 只有在一开始的时候，我们才需要考虑字符串最低位为 0 的情况，我们通过若干次操作删去低位的所有 0；

• 在任意时刻，字符串的最低位均为 1。如果有 k 个 1，那么我们需要 k + 1 次操作（1 次加一操作和 k 次除二操作）将所有的 1 变为 0 并删除。并且在这 k + 1 次操作后，原本最靠近右侧的那个 0 变为了 1。这也解释了为什么我们不需要考虑最低位为 0 的情况了。

在下面的代码中，我们将「命运」均摊到字符串中的每一个字符上进行计数，并给出了详细的注释。

[sol2-C++]

class Solution {
public:
    int numSteps(string s) {
        int n = s.size();
        int ans = 0;
        // meet1 记录我们有没有遇见过字符 1
        bool meet1 = false;
        // 从后向前遍历字符
        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == '0') {
                // 如果当前字符为 0，分为两种情况
                // (1) 还没有遇见过字符 1，那么这个 0 是字符串低位的 0，需要一次除二操作
                // (2) 遇见过字符 1，那么这个 0 会因为它右侧的某次加一操作变为 1，因此它需要一次加一和一次除二操作
                ans += (meet1 ? 2 : 1);
            }
            else {
                // 如果当前字符为 1，分为两种情况
                // (1) 还没有遇见过字符 1，那么这个 1 需要一次加一和一次除二操作
                //     这里需要考虑一种特殊情况，就是这个 1 是字符串最左侧的 1，它并不需要任何操作
                // (2) 遇见过字符 1，那么这个 1 会因为它右侧的某次加一操作变为 0，因此它只需要一次除二操作
                if (!meet1) {
                    if (i != 0) {
                        ans += 2;
                    }
                    meet1 = true;
                }
                else {
                    ++ans;
                }
            }
        }
        return ans;
    }
};

[sol2-Java]

class Solution {
    public int numSteps(String s) {
        int n = s.length();
        int ans = 0;
        // meet1 记录我们有没有遇见过字符 1
        boolean meet1 = false;
        // 从后向前遍历字符
        for (int i = n - 1; i >= 0; --i) {
            if (s.charAt(i) == '0') {
                // 如果当前字符为 0，分为两种情况
                // (1) 还没有遇见过字符 1，那么这个 0 是字符串低位的 0，需要一次除二操作
                // (2) 遇见过字符 1，那么这个 0 会因为它右侧的某次加一操作变为 1，因此它需要一次加一和一次除二操作
                ans += (meet1 ? 2 : 1);
            } else {
                // 如果当前字符为 1，分为两种情况
                // (1) 还没有遇见过字符 1，那么这个 1 需要一次加一和一次除二操作
                //     这里需要考虑一种特殊情况，就是这个 1 是字符串最左侧的 1，它并不需要任何操作
                // (2) 遇见过字符 1，那么这个 1 会因为它右侧的某次加一操作变为 0，因此它只需要一次除二操作
                if (!meet1) {
                    if (i != 0) {
                        ans += 2;
                    }
                    meet1 = true;
                } else {
                    ++ans;
                }
            }
        }
        return ans;
    }
}

[sol2-Python3]

class Solution:
    def numSteps(self, s: str) -> int:
        n, ans = len(s), 0
        # meet1 记录我们有没有遇见过字符 1
        meet1 = False
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                # 如果当前字符为 0，分为两种情况
                # (1) 还没有遇见过字符 1，那么这个 0 是字符串低位的 0，需要一次除二操作
                # (2) 遇见过字符 1，那么这个 0 会因为它右侧的某次加一操作变为 1，因此它需要一次加一和一次除二操作
                ans += (2 if meet1 else 1)
            else:
                # 如果当前字符为 1，分为两种情况
                # (1) 还没有遇见过字符 1，那么这个 1 需要一次加一和一次除二操作
                #     这里需要考虑一种特殊情况，就是这个 1 是字符串最左侧的 1，它并不需要任何操作
                # (2) 遇见过字符 1，那么这个 1 会因为它右侧的某次加一操作变为 0，因此它只需要一次除二操作
                if not meet1:
                    if i != 0:
                        ans += 2
                    meet1 = True
                else:
                    ans += 1
        return ans

复杂度分析

• 时间复杂度：O(N)，我们只遍历整个字符串一次。

• 空间复杂度：O(1)。