1611. 使整数变为 0 的最少操作次数

English Version

题目描述

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

解法

方法一：递归

通过找规律可以发现动态规划转移方程如下：

$$ dp[n] = dp[2^k] - dp[n - 2^k] $$

其中 $dp[2^k] = 2^{k+1}-1$，而 $k$ 表示小于等于 $n$ 的最大的 $2$ 的整数次幂的位数，即 $2^k$ 是小于等于 $n$ 的最大的 $2$ 的整数次幂。

Python3

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        if n <= 1:
            return n
        for i in range(64):
            if (n >> i) == 1:
                base = 1 << i
                break
        return 2 * base - 1 - self.minimumOneBitOperations(n - base)

Go

func minimumOneBitOperations(n int) int {
	if n <= 1 {
		return n
	}
	base := 0
	for i := 0; i < 64; i++ {
		if (n >> i) == 1 {
			base = 1 << i
			break
		}
	}
	return (base << 1) - 1 - minimumOneBitOperations(n-base)
}

...