算法leetcode

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

字数统计: 988字   |   阅读时长: 4分
, ,

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

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

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

本题有很强的组合数学的背景：

一方面我们知道，枚举 $n$ 元素集合的子集有很多算法，比如此前我们介绍过按字典序枚举 (文章 字典序法枚举组合 (r子集))、按 $n$ 位 2 进制数枚举 (文章 常见的枚举方式)，按照格雷码的顺序也可以枚举全排列，本题给出操作过程就是走了一遍格雷码的序列。

另一方面，在编码理论中，由于具有任意两个相邻的编码之间只有一位二进制数不同的特性，使得在数字转换过程中只需要进行一次位运算，有利于硬件实现，格雷码是信道纠错码中的一种常见的辅助编码，本题的过程暗含了这个编码过程。

再一个，n 维超立方体在一些理论分析中经常用到，格雷码对应了 n 维超立方体上的一条哈密顿回路，本题的过程自然也走了一遍这个哈密顿回路。

综上我们可以看到，格雷码将信道纠错码、n维超立方体、子集的枚举串联了起来，本题当然也就可以用格雷码的算法来解决，在文章 格雷码 中我们介绍过格雷码的相关算法。

$1 题目

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

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

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

提示：

1
0 <= n <= 1e9

示例 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