原文链接: https://leetcode-cn.com/problems/integer-replacement

英文原文

Given a positive integer n, you can apply one of the following operations:

1. If n is even, replace n with n / 2.
2. If n is odd, replace n with either n + 1 or n - 1.

Return the minimum number of operations needed for n to become 1.

 

Example 1:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

Example 2:

Input: n = 7
Output: 4
Explanation: 7 -> 8 -> 4 -> 2 -> 1
or 7 -> 6 -> 3 -> 2 -> 1

Example 3:

Input: n = 4
Output: 2

 

Constraints:

• 1 <= n <= 231 - 1

中文题目

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

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

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

 

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

通过代码

高赞题解

笔记本突然充不上电了，艰难用 iPad 写的题解 😭

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})$

---

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})$

---

贪心（位运算）

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

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

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

因此，对于 $x$ 为奇数所能执行的两种操作，+1 能够消除连续一段的 $1$，只要次低位为 $1$（存在连续段），应当优先使用 +1 操作，但需要注意边界 $x = 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(1)$

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
48057	111243	43.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言