1.题目

给定一个正整数 n ,你可以做如下操作：
① 如果 n 是偶数,则用 n / 2 替换 n .
② 如果 n 是奇数,则可以用 n + 1或 n - 1 替换 n .
返回 n 变为 1 The minimum number of replacements required .

示例 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 为偶数时,The only way to replace is,即使用 n / 2 替换 n;
② 当 n 为奇数时,有两种替换方法,即使用 n + 1或 n - 1 替换 n,Regardless of which method is used,The result after substitution must be an even number,So the next replacement operation must be n / 2,So here we can think of using two operations,将 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）记忆化搜索 ==
Memoized search can be seen asrecursion after pruning.Add memoization to the recursion of method 1,这样递归树的每一层最多只会计算两个 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));
    }
}

//思路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);
    }
}