1.题目

给定一个正整数 n ，你可以做如下操作：
① 如果 n 是偶数，则用 n / 2 替换 n 。
② 如果 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 <= 2³¹ - 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/integer-replacement

2.思路

思路参考本题官方题解。
（1）递归 & 暴力穷举法
① 当 n 为偶数时，替换的方法唯一，即使用 n / 2 替换 n；
② 当 n 为奇数时，有两种替换方法，即使用 n + 1或 n - 1 替换 n，而无论使用哪种方法，替换后的结果必为偶数，所以下次替换操作一定是 n / 2，所以这里我们可以看成使用两次操作，将 n 变为 $\frac{n+1}{2}$ 和 $\frac{n-1}{2}$。
注意：当 n 去 int 类型的最大值，即 n = Integer.MAX_VALUE = 2³¹ 时，n + 1 会出现整数溢出的情况，所以可以通过 $\lfloor n/2\rfloor$ + 1 和 $\lfloor n/2\rfloor$ 来分别替换 $\frac{n+1}{2}$ 和 $\frac{n-1}{2}$，其中 $\lfloor x\rfloor$ 表示向下取整。

==（2）记忆化搜索 ==
记忆化搜索可以看作剪枝后的递归。给方法一的递归加上记忆化，这样递归树的每一层最多只会计算两个 n 值。

3.代码实现（Java）

//思路1————递归 & 暴力穷举法
class Solution {
    public int integerReplacement(int n) {
        if (n == 1) {
            return 0;
        }
        if (n % 2 == 0) {
            return 1 + integerReplacement(n / 2);
        }
        return 2 + Math.min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

//思路2————记忆化搜索
class Solution {
    
    Map<Integer, Integer> memo = new HashMap<>();
    
    public int integerReplacement(int n) {
        if (n == 1) {
            return 0;
        }
        if (!memo.containsKey(n)) {
            if (n % 2 == 0) {
                memo.put(n, 1 + integerReplacement(n / 2));
            } else {
                memo.put(n, 2 + Math.min(integerReplacement(n / 2), integerReplacement(n / 2 + 1)));
            }
        }
        return memo.get(n);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19