目录

力扣397. 整数替换

解析代码

---

力扣397. 整数替换

397. 整数替换

难度 中等

给定一个正整数 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 <= 2^31 - 1

class Solution {
public:int integerReplacement(int n) {}
};

---

解析代码1_递归改记忆化搜索

        此题的贪心策略很难想出来，先看看记忆化搜索的方法（记忆化搜索在之前专题已经学过）：用爆搜模拟也可以过，但是加上备忘录优化：

class Solution {unordered_map<int, int> memo;
public:int integerReplacement(int n) {// 时间O(logN) 空间O(logN)return dfs(n);}int dfs(long long n){if(n == 1)return 0;if(memo[n] != 0)return memo[n];if(n % 2 == 0){memo[n] = 1 + dfs(n / 2);return memo[n];}else{memo[n] = 1 + min(dfs(n - 1), dfs(n + 1));return memo[n];}}
};

---

解析代码2_贪心策略

贪心策略：任何选择都应该让这个数尽可能快的变成 1 。

• 对于偶数：只执行除 2 操作。
• 对于奇数：

1. 当 n== 1 的时候，不用执行任何操作。
2. 当 n == 3 的时候，变成 1 的最优操作数是 2 。
3. 当 n > 1 && n % 4 == 1的时候，那么它的二进制表示是 ......01 ，最优的方式应该选择 -1 ，这样就可以把末尾的 1 干掉，接下来执行除法操作，能够更快地变成1 。
4. 当 n > 3 && n % 4 == 3的时候，那么它的二进制表示是 ......11 ，最优的方式应该选择 +1 ，这样可以把一堆连续的 1 转换成 0 ，更快地变成 1 。

class Solution {
public:int integerReplacement(int n){// 时间O(logN) 空间O(1)int ret = 0;while(n != 1){if(n % 2 == 0){n =  n / 2;++ret;}else{ret += 2; // 下面操作都是两步if(n == 3)break;else if(n % 4 == 1) // ......01n /= 2; // 和减1除2结果一样else // ......01n = n / 2 + 1; // 和加1除2结果一样，防溢出}}return ret;}
};