LeetCode 题解工作台
将二进制表示减到 1 的步骤数
给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 1 所需要的步骤数： 如果当前数字为偶数，则将其除以 2 。 如果当前数字为奇数，则将其加上 1 。 题目保证你总是可以按上述规则将测试用例变为 1 。 示例 1： 输入： s = "1101" 输出： 6 解释： "1101" 表…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · string·结合·位运算·操作
答案摘要
我们模拟操作 和 ，同时维护一个进位 来表示当前是否有进位，初始时 $\textit{carry} = \text{false}$。 我们从字符串 的末尾开始向前遍历：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 string·结合·位运算·操作 题型思路
题目描述
给你一个以二进制形式表示的数字 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 <= 500s由字符'0'或'1'组成。s[0] == '1'
解题思路
方法一：模拟
我们模拟操作 和 ，同时维护一个进位 来表示当前是否有进位，初始时 。
我们从字符串 的末尾开始向前遍历：
- 如果 为 ，则当前位 需要加 ，如果 是 ，则加 后变为 ，同时 变为 ；如果 是 ，则加 后变为 ，同时 保持为 。
- 如果 是 ，则需要执行操作 ，即加 ，同时 变为 。
- 此时 是 ，则需要执行操作 ，即除以 。
当遍历结束后，如果 仍然为 ，则需要再执行一次操作 。
时间复杂度 ，其中 是字符串 的长度。空间复杂度 。
class Solution:
def numSteps(self, s: str) -> int:
carry = False
ans = 0
for c in s[:0:-1]:
if carry:
if c == '0':
c = '1'
carry = False
else:
c = '0'
if c == '1':
ans += 1
carry = True
ans += 1
if carry:
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
The candidate should demonstrate familiarity with string manipulation and bitwise operations.
- question_mark
Look for clarity in how they explain the iterative process and how they handle even/odd cases.
- question_mark
Check if they optimize the solution with minimal extra space usage.
常见陷阱
外企场景- error
Misunderstanding the even/odd rule and applying the wrong operation (e.g., dividing by 2 when the number is odd).
- error
Overcomplicating the solution by introducing unnecessary data structures or operations.
- error
Not efficiently handling large binary strings, leading to incorrect time complexity analysis.
进阶变体
外企场景- arrow_right_alt
Modify the problem to handle decimal numbers directly instead of binary strings.
- arrow_right_alt
Allow multiple ways of representing the number (e.g., hexadecimal or octal).
- arrow_right_alt
Introduce variations like counting steps for different bases, or changing the reduction rules.