【DP难题】力扣1611-使整数变为0的最少操作次数

  |  

摘要: 力扣 1611, 稀疏状态,带位运算的状态转移方程

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文是一个动态规划问题,状态转移方程中有位运算操作,状态取值非常稀疏。处理这种稀疏状态用哈希表维护状态,再结合记忆化搜索是常规的处理方法。


$1 题目

给你一个整数 n,你需要重复执行多次下述操作将其转换为 0 :

  • 翻转 n 的二进制表示中最右侧位(第 0 位)。
  • 如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0,则翻转 n 的二进制表示中的第 i 位。

返回将 n 转换为 0 的最小操作次数。

提示:

1
0 <= n <= 109

示例 1:
输入:n = 0
输出:0

示例 2:
输入:n = 3
输出:2
解释:3 的二进制表示为 “11”
“11” -> “01” ,执行的是第 2 种操作,因为第 0 位为 1 。
“01” -> “00” ,执行的是第 1 种操作。

示例 3:
输入:n = 6
输出:4
解释:6 的二进制表示为 “110”.
“110” -> “010” ,执行的是第 2 种操作,因为第 1 位为 1 ,第 0 到 0 位为 0 。
“010” -> “011” ,执行的是第 1 种操作。
“011” -> “001” ,执行的是第 2 种操作,因为第 0 位为 1 。
“001” -> “000” ,执行的是第 1 种操作。

示例 4:
输入:n = 9
输出:14

示例 5:
输入:n = 333
输出:393

$2 题解

算法1:动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
状态定义:
dp[x] := 格雷码 x 对应的二进制数

初始化:
dp[0] = 0, dp[1] = 1

答案:
dp[n]

状态转移:
y = high_bit(x)
y == x: return dp[x] = dp[x / 2] * 2 + 1;
y != x: return dp[x] = dp[y] - dp[x - y];

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int low_bit(int n)
{
return n & (-n);
}

int high_bit(int n)
{
int p = low_bit(n);
while(p != n)
{
n -= p;
p = low_bit(n);
}
return p;
}

class Solution {
public:
int minimumOneBitOperations(int n) {
if(n <= 1)
return n;
dp[1] = 1;
return solve(n);
}

private:
unordered_map<int, int> dp;

int solve(int x)
{
if(dp.count(x) != 0)
return dp[x];

int highbit = high_bit(x);
int y = x - highbit;
if(y == 0)
return dp[x] = solve(x / 2) * 2 + 1;
else
return dp[x] = solve(highbit) - solve(y);
}
};

算法2: 格雷码

参考文章 格雷码


Share