跳转至

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

题目描述

给你一个非负整数 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

解法

方法一

思考

偶数除以 \(2\)，奇数减 \(1\)，问到 \(0\) 的步数。\(\textit{num} \le 10^6\)，直接模拟即可：奇数则减一，否则右移，计数直到变为 \(0\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def numberOfSteps(self, num: int) -> int:
        ans = 0
        while num:
            if num & 1:
                num -= 1
            else:
                num >>= 1
            ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {

    public int numberOfSteps(int num) {
        int ans = 0;
        while (num != 0) {
            num = (num & 1) == 1 ? num - 1 : num >> 1;
            ++ans;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int numberOfSteps(int num) {
        int ans = 0;
        while (num) {
            num = num & 1 ? num - 1 : num >> 1;
            ++ans;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func numberOfSteps(num int) int {
    ans := 0
    for num != 0 {
        if (num & 1) == 1 {
            num--
        } else {
            num >>= 1
        }
        ans++
    }
    return ans
}

1
2
3
4
5
6
7
8
function numberOfSteps(num: number): number {
    let ans = 0;
    while (num) {
        num = num & 1 ? num - 1 : num >>> 1;
        ans++;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn number_of_steps(mut num: i32) -> i32 {
        let mut count = 0;
        while num != 0 {
            if num % 2 == 0 {
                num >>= 1;
            } else {
                num -= 1;
            }
            count += 1;
        }
        count
    }
}

方法二

思考

同一规则也可写成递归：偶数递归 \(n/2\)，奇数递归 \(n-1\)，每层加一；\(n=0\) 停止。语义与循环一致，只是用调用栈表达过程。

1
2
3
4
5
6
7
8
9
class Solution:
    def numberOfSteps(self, num: int) -> int:
        if num == 0:
            return 0
        return 1 + (
            self.numberOfSteps(num // 2)
            if num % 2 == 0
            else self.numberOfSteps(num - 1)
        )

1
2
3
4
5
6
7
8
9
class Solution {

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

1
2
3
4
5
6
7
class Solution {
public:
    int numberOfSteps(int num) {
        if (num == 0) return 0;
        return 1 + (num & 1 ? numberOfSteps(num - 1) : numberOfSteps(num >> 1));
    }
};

1
2
3
4
5
6
7
8
9
func numberOfSteps(num int) int {
    if num == 0 {
        return 0
    }
    if (num & 1) == 0 {
        return 1 + numberOfSteps(num>>1)
    }
    return 1 + numberOfSteps(num-1)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
impl Solution {
    pub fn number_of_steps(mut num: i32) -> i32 {
        if num == 0 {
            0
        } else if num % 2 == 0 {
            1 + Solution::number_of_steps(num >> 1)
        } else {
            1 + Solution::number_of_steps(num - 1)
        }
    }
}

评论