难度: Hard
给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：
n 的二进制表示中最右侧位（第 0 位）。(i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。返回将 n 转换为 0 的最小操作次数。
示例 1：
输入：n = 3 输出：2 解释：3 的二进制表示为 "11" "11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。 "01" -> "00" ，执行的是第 1 种操作。
示例 2：
输入：n = 6 输出：4 解释：6 的二进制表示为 "110". "110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。 "010" -> "011" ，执行的是第 1 种操作。 "011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。 "001" -> "000" ，执行的是第 1 种操作。
提示：
0 <= n <= 109运行时间: 31 ms
内存: 16.3 MB
class Solution:
def minimumOneBitOperations(self, n: int) -> int:
# dp(1xxx)=dp(100)+1+dp(100)-dp(xxx)
# 类似1997. 访问完所有房间的第一天
# 对于二进制1xx来说, 要想使得最高位变成0, 必须将其转换成110, 这样才可能应用操作2将最高位变为0
# 设dp[1xx]是将1xx转成0的最少次数, 那么有:
# 首先从xx转成10, 这一步可以应用前缀和优化, 得到最少次数是dp[10]-dp[xx] (显然可见0到10一定比0到xx需要的次数多, 分xx的最高位是否是1两种情况, 很容易就能得出)
# 然后额外1次, 将110转成010
# 最后再转dp[10]次即可
# 也即dp[1xx]=dp[10]-dp[xx]+1+dp[10]=2*dp[10]-dp[xx]+1
# 注意这道题需要用记搜, 因为有的数字并不会被计算, 用dp的话会超时
@functools.lru_cache(None)
def dp(n):
if n <= 1:
return n
# mask即为1xx对应的10
mask = 1 << (len(bin(n)) - 4)
# 而xx则为n-(mask<<1)
return 2 * dp(mask) - dp(n - (mask << 1)) + 1
return dp(n)
本题的解法采用了递归与记忆化搜索的方法。核心思想是动态规划，通过递归定义 dp 函数，dp(n) 表示将整数 n 变为 0 的最小操作次数。关键在于理解二进制数的转换过程，特别是怎样通过有限的操作达到目标状态。首先，如果 n 是 1 或者 0，直接返回 n (即 0 或 1 次操作)。然后对于更复杂的情况，计算最高位的位置，并使用位操作来确定需要转换的次数。递归的计算这些子问题，并利用 functools.lru_cache 来避免重复计算，提高效率。算法的核心在于递归的构建，以及如何利用二进制的性质减少计算次数。
时间复杂度: O(log n)
空间复杂度: O(log n)
class Solution:
def minimumOneBitOperations(self, n: int) -> int:
import functools
# 使用缓存避免重复计算相同的值
@functools.lru_cache(None)
def dp(n):
if n <= 1:
return n # 如果 n 是 0 或 1，直接返回
# 找到最高位的1
mask = 1 << (len(bin(n)) - 4)
# 通过位操作计算子问题所需的值
return 2 * dp(mask) - dp(n - (mask << 1)) + 1 # 根据状态转移方程计算
return dp(n) # 计算并返回结果
为了避免递归函数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时，意味着缓存的大小是无限的，它将保存所有不同输入的结果。这样做的潜在风险包括占用过多的内存，尤其是在处理非常大的数据或长时间运行的程序时。如果输入的范围极广或变化多端，缓存可能会逐渐消耗大量内存资源，影响程序的性能并增加系统的负担。此外，一个无限大小的缓存可能在某些情况下使得垃圾回收工作更加复杂，延迟清理不再被需要的缓存项。因此，适当的容量限制可以帮助控制内存使用，确保缓存机制不会成为系统性能的瓶颈。