1342. 将数字变成 0 的操作次数
1342. 将数字变成 0 的操作次数
题目
Given an integer num
, return the number of steps to reduce it to zero.
In one step, if the current number is even, you have to divide it by 2
, otherwise, you have to subtract 1
from it.
Example 1:
Input: num = 14
Output: 6
Explanation: Step 1: 14 is even; divide by 2 and obtain 7. Step 2: 7 is odd; subtract 1 and obtain 6. Step 3: 6 is even; divide by 2 and obtain 3. Step 4: 3 is odd; subtract 1 and obtain 2. Step 5: 2 is even; divide by 2 and obtain 1. Step 6: 1 is odd; subtract 1 and obtain 0.
Example 2:
Input: num = 8
Output: 4
Explanation: Step 1: 8 is even; divide by 2 and obtain 4. Step 2: 4 is even; divide by 2 and obtain 2. Step 3: 2 is even; divide by 2 and obtain 1. Step 4: 1 is odd; subtract 1 and obtain 0.
Example 3:
Input: num = 123
Output: 12
Constraints:
0 <= num <= 10^6
题目大意
给你一个非负整数 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
解题思路
可以使用位运算中的右移(即 num >>= 1
)来模拟操作过程:
- 初始化
steps
为 0,用于记录步数。 - 特殊情况:如果
num == 0
,不需要操作,返回0
。 - 循环进行操作,直到
num == 0
。- 如果
num
为偶数:直接除以 2(等价于右移 1 位,即num >>= 1
),步数加 1。 - 如果
num
为奇数:要先减 1 然后除以 2(等价于右移 1 位),步数加 2。 - 其中偶数可以通过
(num & 1) == 0
判断;
- 如果
- 返回步数。
复杂度分析
- 时间复杂度:
O(log num)
,num
的值在每次操作中减半,最多需要进行O(log num)
次操作。 - 空间复杂度:
O(1)
,仅使用常量空间存储变量。
代码
/**
* @param {number} num
* @return {number}
*/
var numberOfSteps = function (num) {
if (num === 0) return 0; // 边界条件:输入为 0
let steps = 0;
while (num > 1) {
// 偶数操作 1 次,奇数操作 2 次
steps += (num & 1) === 0 ? 1 : 2;
num >>= 1; // 除以 2
}
return steps + 1; // 最后一步操作将 1 变为 0
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
2139 | 得到目标值的最少行动次数 | 贪心 数学 | 🟠 | 🀄️ 🔗 | |
2169 | 得到 0 的操作数 | [✓] | 数学 模拟 | 🟢 | 🀄️ 🔗 |