397. 整数替换
难度 中等
给定一个正整数 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 <= 231 - 1
题解
思路：递归
class Solution { public int integerReplacement(int n) { if(n==1){ return 0; } if(n%2==0){ n=n/2; return 1+integerReplacement(n); }else{ int l=n-1; int r=n+1; int rr=1+integerReplacement(r); int lr=1+integerReplacement(l); return Math.min(rr,lr); return lr; } } }
数入2147483647 会报错 java.lang.StackOverflowError
错误原因是 2147483647是2的31次方-1 它加一会变成2的32次方 超过了int所存储的数据范围[-2的32次方,2的32次方-1]
直接看官方解答吧
官方
方法一：枚举所有的情况
细节
n=2^31 −1 时，计算 n+1 会导致溢出，因此我们可以使用整数除法 ⌊n/2⌋+1 和 ⌊n/2⌋
(n+1)/2 或(n-1)/2，其中 ⌊⋅⌋ 表示向下取整。
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)); } }
方法二：记忆化搜索
思路与算法
我们给方法一的递归加上记忆化，这样递归树的每一层最多只会计算两个 n 值，时间复杂度降低为O(logn)。
因为对于奇数2n+1
(2n+1 +1)/2=n+1
(2n+1 -1)/2=n
对于下一次的n+1，它的-1会和n重复
对于下一次的n，它的+1会和n+1重复
所以需要记忆化搜素
代码
class Solution { Map<Integer, Integer> memo = new HashMap<Integer, Integer>(); 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); } }
方法三：贪心
思路与算法
实际上，方法一和方法二中的递归枚举中的「最优解」是固定的：
当 n 为偶数时，我们只有唯一的方法将 n 替换为 n/2；
当 n 为奇数时，n 除以 4 的余数要么为 1，要么为 3。
如果为 1，我们可以断定，应该将 n 变成 (n-1)/2。
如果为 3，我们可以断定，应该将 n 变成 (n+1)/2 。
这样做的好处是n会处理成4的倍数，那么它接下来的两次操作都是对偶数，可以直接连续除以2
例
8 4 2 1 7-------- 6 3 4 2 1
4 2 1 6 3 5-------- 4 2 1
因此，我们只需要根据上面的分类讨论，求出将 nn 变为 11 的操作次数即可。
代码
class Solution { public: int integerReplacement(int n) { int ans = 0; while (n != 1) { if (n % 2 == 0) { ++ans; n /= 2; } else if (n % 4 == 1) { ans += 2; n /= 2; } else { if (n == 3) { ans += 2; n = 1; } else { ans += 2; n = n / 2 + 1; } } } return ans; } };
复杂度分析
- 时间复杂度：O(logn)。
- 空间复杂度：O(1)。
