Solutions CS101

Appearance

M1404.将二进制表示减到 1 的步骤数 ​

bit manipulation, https://leetcode.cn/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/

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

这个问题可以通过模拟或者逻辑位移规律来解决。由于二进制字符串的长度可达 500，虽然 Python 的大整数可以直接处理，但从算法面试的角度，一次遍历（贪心/位移逻辑） 是更优雅且通用的解法。

方法一：直接模拟（利用 Python 大整数特性）

在 Python 中，int(s, 2) 可以将二进制字符串转换为任意精度的整数。然后按照题目规则循环即可。

python
class Solution:
    def numSteps(self, s: str) -> int:
        num = int(s, 2)
        steps = 0
        while num > 1:
            if num % 2 == 0:
                num //= 2
            else:
                num += 1
            steps += 1
        return steps
  • 时间复杂度：O(N2)。在 Python 中，大整数的加法和除法与位数有关，循环次数最多约 2N 次，每次操作复杂度随位数增加。
  • 空间复杂度：O(N)，用于存储转换后的整数。

方法二：从低位到高位遍历（最优解）

我们可以从右向左（从最低位到最高位）遍历字符串，模拟进位（carry）的过程。

逻辑推导：

  1. 当前位 + 进位 = 0：说明当前是偶数（原本是 0，且没有进位），只需一次“除以 2”操作（右移），步数 +1。
  2. 当前位 + 进位 = 1：说明当前是奇数。
    • 奇数需要“加 1”再“除以 2”，这总共需要 2 步。
    • 一旦执行了“加 1”，就会产生一个向更高位的进位（carry 置为 1）。
  3. 当前位 + 进位 = 2：说明原本是 1 且有进位。1+1=10，这一位变成了 0（偶数），只需一次“除以 2”操作，步数 +1，进位保持为 1。

特殊情况：最左边的 1（索引 0）。

  • 遍历到索引 1 停止。最后根据是否有进位来决定。如果最后进位为 1，说明最左边的 1 变成了 10，还需要额外一步除法变成 1。
python
class Solution:
    def numSteps(self, s: str) -> int:
        res = 0
        carry = 0
        # 从右向左遍历，直到倒数第二位 (索引 1)
        for i in range(len(s) - 1, 0, -1):
            current_bit = int(s[i])
            if current_bit + carry == 1:
                # 奇数情况：+1 变成偶数，再除以 2。共 2 步
                res += 2
                carry = 1
            else:
                # 偶数情况：直接除以 2。共 1 步
                # (包括 0+0=0 和 1+1=2 两种情况)
                res += 1
        
        # 最后处理最高位 (s[0])
        # 如果有进位，s[0] 从 1 变成 2 (10)，需要再除以 2 才能变回 1，所以加 1
        return res + carry

复杂度分析：

  • 时间复杂度：O(N)，其中 N 是字符串长度。只需遍历一次字符串。
  • 空间复杂度：O(1)，仅使用了常数个额外变量。

示例 1 演示 (s = "1101")：

  1. i = 3 (bit='1', carry=0): 1+0=1 (奇数) -> res = 2, carry = 1
  2. i = 2 (bit='0', carry=1): 0+1=1 (奇数) -> res = 4, carry = 1
  3. i = 1 (bit='1', carry=1): 1+1=2 (偶数) -> res = 5, carry = 1
  4. 循环结束。
  5. 返回 res + carry = 5 + 1 = 6。符合预期。

总结

推荐使用方法二，因为它展示了对位运算和进位逻辑的深刻理解，且在不支持大数运算的语言（如 C++、Java）中，这是解决该题的标准做法。