【月度刷题活动同款】与位运算结合的简单贪心题

- 日理万妓 2023-10-04 21:54 12阅读 0赞

### 题目描述 ###

这是 LeetCode 上的 **[397. 整数替换][397.]** ，难度为 **中等**。

Tag : 「DFS」、「BFS」、「贪心」

给定一个正整数 `n` ，你可以做如下操作：

1.  如果 `n` 是偶数，则用 `n / 2` 替换 `n` 。
2.  如果 `n` 是奇数，则可以用 `n + 1` 或 `n - 1` 替换 `n` 。

`n` 变为 111 所需的最小替换次数是多少？

示例 1：

输入：n = 8
    
    输出：3
    
    解释：8 -> 4 -> 2 -> 1
    复制代码

示例 2：

输入：n = 7
    
    输出：4
    
    解释：7 -> 8 -> 4 -> 2 -> 1
    或 7 -> 6 -> 3 -> 2 -> 1
    复制代码

示例 3：

输入：n = 4
    
    输出：2
    复制代码

提示：

*  1<=n<=231−11 <= n <= 2^\{31\} - 11<=n<=231−1

### DFS ###

运用 `DFS` 进行求解。为防止重复处理某些数值，可以使用「哈希表」进行记忆化。

代码：

class Solution {
        Map<Long, Integer> map = new HashMap<>();
        public int integerReplacement(int n) {
            return dfs(n * 1L);
        }
        int dfs(long n) {
            if (n == 1) return 0;
            if (map.containsKey(n)) return map.get(n);
            int ans = n % 2 == 0 ? dfs(n / 2) : Math.min(dfs(n + 1), dfs(n - 1));
            map.put(n, ++ans);
            return ans;
        }
    }
    复制代码

*  时间复杂度：O(log⁡n)O(\\log\{n\})O(logn)
 *  空间复杂度：O(log⁡n)O(\\log\{n\})O(logn)

### BFS ###

同理，也可以使用 `BFS` 进行求解。同样使用「哈希表」记录步数，进行防止重复处理。

代码：

class Solution {
        public int integerReplacement(int n) {
            if (n == 1) return 0;
            Map<Long, Integer> map = new HashMap<>();
            Deque<Long> d = new ArrayDeque<>();
            d.addLast(n * 1L);
            map.put(n * 1L, 0);
            while (!d.isEmpty()) {
                long t = d.pollFirst();
                int step = map.get(t);
                long[] ns = t % 2 == 0 ? new long[]{t / 2} : new long[]{t + 1, t - 1};
                for (long x : ns) {
                    if (x == 1) return step + 1;
                    if (!map.containsKey(x)) {
                        map.put(x, step + 1);
                        d.addLast(x);
                    }
                }
            }
            return -1;
        }
    }
    复制代码

*  时间复杂度：O(log⁡n)O(\\log\{n\})O(logn)
 *  空间复杂度：O(log⁡n)O(\\log\{n\})O(logn)

### 贪心（位运算） ###

上述两种做法，我们不可避免地在每个回合枚举了所有我们可以做的决策：主要体现在对 xxx 为奇数时的处理，我们总是处理 x+1x + 1x+1 和 x−1x - 1x−1 两种情况。

我们可以从二进制的角度进行分析：**给定起始值 nnn，求解将其变为 (000...0001)2(000...0001)\_2(000...0001)2 的最小步数。**

*  对于偶数（二进制最低位为 000）而言，我们只能进行一种操作，其作用是将当前值 xxx 其进行一个单位的右移；
 *  对于奇数（二进制最低位为 111）而言，我们能够进行 `+1` 或 `-1` 操作，分析两种操作为 xxx 产生的影响：
    
     *  对于 `+1` 操作而言：最低位必然为 111，此时如果次低位为 000 的话， `+1` 相当于将最低位和次低位交换；如果次低位为 111 的话，`+1` 操作将将「从最低位开始，连续一段的 111」进行消除（置零），并在连续一段的高一位添加一个 111；
     *  对于 `-1` 操作而言：最低位必然为 111，其作用是将最低位的 111 进行消除。

因此，对于 xxx 为奇数所能执行的两种操作，`+1` 能够消除连续一段的 111，只要次低位为 111（存在连续段），应当优先使用 `+1` 操作，但需要注意边界 x=3x = 3x=3 时的情况（此时选择 `-1` 操作）。

代码：

class Solution {
        public int integerReplacement(int _n) {
            long n = _n;
            int ans = 0;
            while (n != 1) {
                if (n % 2 == 0) {
                    n >>= 1;
                } else {
                    if (n != 3 && ((n >> 1) & 1) == 1) n++;
                    else n--;
                }
                ans++;
            }
            return ans;
        }
    }
    复制代码

*  时间复杂度：O(log⁡n)O(\\log\{n\})O(logn)
 *  空间复杂度：O(1)O(1)O(1)

### 最后 ###

这是我们「刷穿 LeetCode」系列文章的第 `No.397` 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：[github.com/SharingSour…][github.com_SharingSour] 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

[397.]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Finteger-replacement%2Fsolution%2Fgong-shui-san-xie-yi-ti-san-jie-dfsbfs-t-373h%2F
[github.com_SharingSour]: https://link.juejin.cn?target=https%3A%2F%2Fgithub.com%2FSharingSource%2FLogicStack-LeetCode