网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 397. 整数替换 ，难度为 中等。
Tag : 「DFS」、「BFS」、「贪心」
给定一个正整数 n ，你可以做如下操作：
- 如果
n是偶数，则用n / 2替换n。 - 如果
n是奇数，则可以用n + 1或n - 1替换n。
n 变为 11 所需的最小替换次数是多少？
示例 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 <= 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(logn)
- 空间复杂度：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(logn)
- 空间复杂度：O(\log{n})O(logn)
贪心（位运算）
上述两种做法，我们不可避免地在每个回合枚举了所有我们可以做的决策：主要体现在对 xx 为奇数时的处理，我们总是处理 x + 1x+1 和 x - 1x−1 两种情况。
我们可以从二进制的角度进行分析：给定起始值 nn，求解将其变为 (000...0001)_2(000...0001)2 的最小步数。
- 对于偶数（二进制最低位为 00）而言，我们只能进行一种操作，其作用是将当前值 xx 其进行一个单位的右移；
- 对于奇数（二进制最低位为11）而言，我们能够进行
+1或-1操作，分析两种操作为xx产生的影响：
- 对于
+1操作而言：最低位必然为 11，此时如果次低位为 00 的话，+1相当于将最低位和次低位交换；如果次低位为 11 的话，+1操作将将「从最低位开始，连续一段的 11」进行消除（置零），并在连续一段的高一位添加一个 11； - 对于
-1操作而言：最低位必然为 11，其作用是将最低位的 11 进行消除。
因此，对于 xx 为奇数所能执行的两种操作，+1 能够消除连续一段的 11，只要次低位为 11（存在连续段），应当优先使用 +1 操作，但需要注意边界 x = 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(logn)
- 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.397 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
