使整数变为 0 的最少操作次数
难度:
标签:
题目描述
代码结果
运行时间: 31 ms, 内存: 16.3 MB
/*
* 思路:
* 1. 使用 Java Stream 处理相同的逻辑。
* 2. 通过 while 循环遍历 n 的二进制位,使用 lambda 表达式执行翻转操作。
*/
import java.util.stream.IntStream;
public class SolutionStream {
public int minimumOperations(int n) {
int[] operations = {0};
IntStream.iterate(n, x -> x > 0, x -> {
int i = 0;
while ((x & (1 << i)) == 0) {
i++;
}
if ((x & (1 << (i + 1))) != 0) {
x ^= (1 << (i + 1));
} else {
x ^= (1 << i);
}
operations[0]++;
return x;
}).forEach(x -> {});
return operations[0];
}
}
解释
方法:
本题的解法采用了递归与记忆化搜索的方法。核心思想是动态规划,通过递归定义 dp 函数,dp(n) 表示将整数 n 变为 0 的最小操作次数。关键在于理解二进制数的转换过程,特别是怎样通过有限的操作达到目标状态。首先,如果 n 是 1 或者 0,直接返回 n (即 0 或 1 次操作)。然后对于更复杂的情况,计算最高位的位置,并使用位操作来确定需要转换的次数。递归的计算这些子问题,并利用 functools.lru_cache 来避免重复计算,提高效率。算法的核心在于递归的构建,以及如何利用二进制的性质减少计算次数。
时间复杂度:
O(log n)
空间复杂度:
O(log n)
代码细节讲解
🦆
如何确保递归函数dp不会陷入无限递归?特别是在调用dp(mask)和dp(n - (mask << 1))时。
▷🦆
您在解答中使用了动态规划的方法,为什么选择这种方法而不是迭代或其他方法?
▷🦆
lru_cache的最大容量设置为None时,可能会有什么潜在的风险或效率问题?
▷