leetcode
leetcode 1201 ~ 1250
将数字变成 0 的操作次数

将数字变成 0 的操作次数

难度:

标签:

题目描述

代码结果

运行时间: 18 ms, 内存: 16.2 MB


/*
 * 思路:
 * 1. 使用 IntStream.iterate 生成一个数字流,每次按题意的规则转换 num。
 * 2. 计算出满足 num == 0 的元素的索引,即为需要的步数。
 */
import java.util.stream.IntStream;

public class Solution {
    public int numberOfSteps(int num) {
        return (int) IntStream.iterate(num, n -> n != 0, n -> n % 2 == 0 ? n / 2 : n - 1).count() - 1;
    }
}

解释

方法:

题解的思路是通过模拟操作来逐步将输入的数字减少到0。具体做法是使用一个循环来反复检查数字的奇偶性。如果数字是偶数,就将其除以2;如果是奇数,则将其减1。每执行一次操作,计数器就增加1。循环持续进行,直到数字变为0为止。

时间复杂度:

O(log n)

空间复杂度:

O(1)

代码细节讲解

🦆
在实现中你使用了整除`num = num / 2`,为何不使用位运算`num >>= 1`来优化性能?
在实现中使用`num = num / 2`而不是`num >>= 1`主要是为了保持代码的可读性和清晰性。虽然位运算`num >>= 1`在性能上可能略有优势,因为它直接在二进制层面操作,避免了一些除法的开销,但这种性能提升在现代编译器和处理器上通常是微不足道的。对于教学和示例代码而言,清晰地表达算法思想通常比微小的性能优化更为重要。
🦆
为什么在算法中选择了使用while循环而不是递归方式实现?
选择使用while循环而不是递归的主要原因是考虑到效率和堆栈安全。递归实现可能会导致深度很大的递归调用,特别是当输入的数字非常大时,这可能导致堆栈溢出错误。而while循环不涉及额外的调用栈,因此在处理大量数据时更加稳定和高效。此外,循环结构在这类简单递减或递增的逻辑中更直观易懂。
🦆
如果`num`的初始值为0,该算法是否仍然有效,是否有必要处理这种特殊情况?
如果`num`的初始值为0,该算法仍然有效,因为它将直接进入while循环并检查条件`num != 0`,发现不满足条件后立即退出循环。因此,算法将返回计数器的初始值0,这是正确的结果。这种情况无需特殊处理,因为算法已经能够正确处理`num`为0的情况,返回0步即符合预期。

相关问题