[LeetCode] 1342. Number of Steps to Reduce a Number to Zero 将数字变成 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。既然是一道简单题，那么博主认为就应该没有啥特别的技巧，就直接按要求来写就行了，用一个 while 循环，若 num 大于0则进行循环，在循环中判断，若 num 为偶数，则除以2，否则自减1，然后结果 res 自增1。循环退出后返回 res 即可，参见代码如下：

解法一：

class Solution {
public:
    int numberOfSteps(int num) {
        int res = 0;
        while (num > 0) {
            num = (num % 2 == 0) ? num / 2 : (num - 1);
            ++res;
        }
        return res;
    }
};

我们可以稍稍进行一下优化，若判断 num 是奇数的话，上面的解法是先减去1，然后在下次循环中再除以2，这里可以直接两步一起处理，因为整型数情况下的奇数除以2就等于其先减1再除以2的值。直接结果 res 加上2就可以了，需要注意的是，循环退出后，返回 res-1，因为当 num 为1的时候，res 还是加上了2，需要减掉。还有就是要提前判断 num 为0的情况，直接返回0即可，参见代码如下：

解法二：

class Solution {
public:
    int numberOfSteps(int num) {
        if (num == 0) return 0;
        int res = 0;
        while (num > 0) {
            res += (num & 1) ? 2 : 1;
            num >>= 1;
        }
        return res - 1;
    }
};

这道题还有特别叼的解法，一行搞定碉堡了，根据上面的解法，每次 num 都要除以2，则若能快速知道总共可以除以多少个2的话，就可以直接将个数加到结果 res 中，则可以对 num 取以2为底的对数，同时还要将过程中的奇数加上，快速处理的方法就是找出 num 的二进制数中的1的个数，可以用 built-in 类 bitset 来得到1的个数，跟之前的对数值加起来即可，注意还是要处理 num 为0的 corner case，因为不能对0取对数，参见代码如下：

解法三：

class Solution {
public:
    int numberOfSteps(int num) {
        return num == 0 ? 0 : log2(num) + bitset<32>(num).count();
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1342

类似题目：

Minimum Moves to Reach Target Score

Count Operations to Obtain Zero

参考资料：

https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/

https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/solutions/502809/just-count-number-of-0-and-1-in-binary/

https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/solutions/502719/c-single-line-in-o-1-with-explanation/

LeetCode All in One 题目讲解汇总(持续更新中...)