leetcode
leetcode 1451 ~ 1500
使整数变为 0 的最少操作次数

使整数变为 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))时。
为了避免递归函数dp陷入无限递归,首先确保基础情况能够正确处理,即当n为0或1时,dp(n)直接返回n,这为递归提供了明确的终止条件。其次,在调用dp(mask)和dp(n - (mask << 1))时,算法通过位操作来计算次要问题的大小,确保它们都小于原问题的大小n。这里的mask是n的最高位,因此n - (mask << 1)始终小于n,而mask本身也小于n。这样的递归结构保证了每次递归调用处理的是一个更小的问题,从而避免了无限递归的风险。
🦆
您在解答中使用了动态规划的方法,为什么选择这种方法而不是迭代或其他方法?
选择动态规划方法是因为这种方法能够有效地处理重叠子问题,并且可以通过记忆化来优化递归计算,避免重复计算相同子问题的开销。递归结合记忆化的动态规划能够清晰地表达问题的状态转移逻辑,特别是在涉及复杂位操作和状态转移的问题中。而直接使用迭代或其他方法可能需要更复杂的状态管理或者不能直观地反映问题的本质。动态规划递归形式在理解和实现上都提供了优势,尤其是在结合lru_cache时,可以极大提高效率和实现简洁性。
🦆
lru_cache的最大容量设置为None时,可能会有什么潜在的风险或效率问题?
当lru_cache的最大容量设置为None时,意味着缓存的大小是无限的,它将保存所有不同输入的结果。这样做的潜在风险包括占用过多的内存,尤其是在处理非常大的数据或长时间运行的程序时。如果输入的范围极广或变化多端,缓存可能会逐渐消耗大量内存资源,影响程序的性能并增加系统的负担。此外,一个无限大小的缓存可能在某些情况下使得垃圾回收工作更加复杂,延迟清理不再被需要的缓存项。因此,适当的容量限制可以帮助控制内存使用,确保缓存机制不会成为系统性能的瓶颈。

相关问题