LeetCode 题解工作台
将数字变成 0 的操作次数
给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。 示例 1： 输入： num = 14 输出： 6 解释： 步骤 1) 14 是偶数，除以 2 得到 7 。 步骤 2） 7 是奇数，减 1 得到 6 。 步骤 3） 6 是…
2
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数学·位运算
答案摘要
class Solution: def numberOfSteps(self, num: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·位运算 题型思路
题目描述
给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。
示例 1：
输入：num = 14 输出：6 解释： 步骤 1) 14 是偶数，除以 2 得到 7 。 步骤 2） 7 是奇数，减 1 得到 6 。 步骤 3） 6 是偶数，除以 2 得到 3 。 步骤 4） 3 是奇数，减 1 得到 2 。 步骤 5） 2 是偶数，除以 2 得到 1 。 步骤 6） 1 是奇数，减 1 得到 0 。
示例 2：
输入：num = 8 输出：4 解释： 步骤 1） 8 是偶数，除以 2 得到 4 。 步骤 2） 4 是偶数，除以 2 得到 2 。 步骤 3） 2 是偶数，除以 2 得到 1 。 步骤 4） 1 是奇数，减 1 得到 0 。
示例 3：
输入：num = 123 输出：12
提示：
0 <= num <= 10^6
解题思路
方法一
class Solution:
def numberOfSteps(self, num: int) -> int:
ans = 0
while num:
if num & 1:
num -= 1
else:
num >>= 1
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate demonstrate the ability to break down a simple problem into smaller, manageable steps?
- question_mark
Does the candidate understand the use of bit manipulation for optimization?
- question_mark
Can the candidate explain edge cases and handle them efficiently?
常见陷阱
外企场景- error
Failing to handle the edge case when `num` is 0.
- error
Not leveraging bit manipulation for efficient computation, leading to slower solutions.
- error
Forgetting to properly count the number of steps and incorrectly returning the result.
进阶变体
外企场景- arrow_right_alt
Optimize the solution by using bitwise operations to reduce time complexity.
- arrow_right_alt
Change the problem to require tracking the operations performed, such as adding an operation history.
- arrow_right_alt
Instead of counting steps, return the series of numbers obtained during the process.