跳至主要內容

1342. 将数字变成 0 的操作次数


1342. 将数字变成 0 的操作次数

🟢   🔖  位运算 数学  🔗 力扣open in new window LeetCodeopen in new window

题目

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)来模拟操作过程:

  1. 初始化 steps 为 0,用于记录步数。
  2. 特殊情况:如果 num == 0,不需要操作,返回 0
  3. 循环进行操作,直到 num == 0
    • 如果 num 为偶数:直接除以 2(等价于右移 1 位,即 num >>= 1),步数加 1。
    • 如果 num 为奇数:要先减 1 然后除以 2(等价于右移 1 位),步数加 2。
    • 其中偶数可以通过 (num & 1) == 0 判断;
  4. 返回步数。

复杂度分析

  • 时间复杂度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得到目标值的最少行动次数贪心 数学🟠🀄️open in new window 🔗open in new window
2169得到 0 的操作数[✓]数学 模拟🟢🀄️open in new window 🔗open in new window