菜单
文章 Leetcode

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

beautifulremi

beautifulremi

• 阅读本文需 5 分钟

题目

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

解题思路

直观模拟法

这是最符合直觉的方法：题目怎么说，我就怎么做。

  1. 准备阶段：因为 Python 的字符串不能改，所以先用 list_s = list(s) 把文本拆成列表。
  2. 判断奇偶：看列表的最后一位 list_s[-1]。
    • 如果是 '0'（偶数）：执行“除以 2”，在二进制里就是删掉最后一位。对应操作：list_s.pop()。
    • 如果是 '1'（奇数）：执行“加 1”。对应操作：调用你写的 add_one 函数。
  3. 循环终止：直到列表里只剩下 ['1'] 为止。
  4. 计数：每操作一次，ans += 1。

评价：逻辑清晰，非常适合理解二进制底层操作。虽然在极端情况下（比如全是 1）不断进位会导致效率略低，但对于题目给出的长度 500 的限制，这绝对能过。

大数转换法（Python 的特权）

Python 的 int 类型是“自带外挂”的——它支持无限精度。

  1. 一键转换：利用 num = int(s, 2) 直接把几百位的二进制字符串变成一个巨大的十进制整数。

简单循环：

while num > 1:
    if num % 2 == 0:
        num //= 2
    else:
        num += 1
    ans += 1

评价：这是“暴力美学”。在别的语言（如 C++ 或 Java）里，500 位的二进制数会直接溢出（long long 也放不下），但 Python 却能处理得游刃有余。这是日常开发中最快、最不容易出错的写法。

一次遍历法（算法优化 $O(N)$）

这里的核心逻辑是观察“进位”**对后续位的影响：

  • 从右往左看：
  • 如果遇到 0 且没有进位，直接除以 2（1 步）。
  • 如果遇到 1，它必须先加 1 变成偶数（1 步），然后除以 2（1 步），共 2 步。并且，它会产生一个持续向左的“进位”。
  • 一旦产生了进位，接下来的 0 也会被进位变成 1，从而变成“奇数”的情况。

逻辑精髓：

  • 只要最右边出现了 1，它就迟早要通过“加 1”变成 0 并进位。
  • 每一个 0 最终都会因为除以 2 被消掉。
  • 每一个 1（除了最左边的那个）最终都要先加 1 变成 0，再除以 2 消耗掉。

在二进制中，如果你从最低位（最右边）开始看：

  1. 如果当前位 + 进位 = 0：
    • 说明它是偶数。只需要执行 1 步：除以 2。
    • 进位保持为 0。
  2. 如果当前位 + 进位 = 1：
    • 说明它是奇数。需要执行 2 步：先加 1（变偶数），再除以 2。
    • 此时会产生一个进位，所以 carry 变为 1。
  3. 如果当前位 + 进位 = 2：
    • 说明原本是 1 且有进位，变回了偶数（10）。只需要执行 1 步：除以 2。
    • 进位依然保持为 1。

具体代码

方法一

class Solution:
    def numSteps(self, s: str) -> int:
        ans = 0
        list_s = list(s)
        while list_s != ["1"]:
            if list_s[-1] == "1":
                list_s = self.add_one(list_s)
            else:
                list_s.pop()
            ans += 1
        return ans
        
    def add_one(self, list_s):
        i = len(list_s) - 1
        while i >= 0:
            if list_s[i] == "0":
                list_s[i] = "1"
                return list_s
            else:
                list_s[i] = "0"
                i -= 1
        return ["1"] + list_s

方法二

class Solution:
    def numSteps(self, s: str) -> int:
        num = int(s, 2) # 直接转成十进制大整数
        steps = 0
        while num > 1:
            if num % 2 == 1: num += 1
            else: num //= 2
            steps += 1
        return steps

方法三

class Solution:
    def numSteps(self, s: str) -> int:
        steps = 0
        carry = 0
        
        # 从右往左遍历，直到倒数第二位 (索引 1)
        for i in range(len(s) - 1, 0, -1):
            # 当前位真正的数值 = 原始字符 + 进位
            current_val = int(s[i]) + carry
            
            if current_val == 1:
                # 奇数情况：加 1 再除以 2，共 2 步
                steps += 2
                carry = 1 # 产生/维持进位
            else:
                # 偶数情况（0+0 或 1+1）：只需除以 2，共 1 步
                steps += 1
                # 如果是 1+1，carry 依然是 1；如果是 0+0，carry 依然是 0
                # 简单写法：如果 current_val 是 2，carry 保持 1，否则保持原样
                if current_val == 2:
                    carry = 1
        
        # 最后处理最左边的 s[0]
        # s[0] 始终是 '1'。如果最后还有进位，说明变成了 '10'，还需要 1 步除法
        return steps + carry
分享