给定一个正整数 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^31 - 1
解题思路：
1、如果n 为偶数那就只有/2一种选项
2、如果n为奇数那么有 + 1和 - 1两种选择，这里用long因为2^31 - 1 + 1会爆掉int
3、利用HashMap存储值以免重复以空间换时间
代码：文章来源：https://www.toymoban.com/news/detail-615719.html
class Solution {
Map<Long, Integer> map = new HashMap<>();
public int integerReplacement(int n) {
return dfs(n * 1L);
}
public 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);//记得是先变到n/2或n + 1 或 n - 1的状态所以需要 + 1
return ans;
}
}
文章来源地址https://www.toymoban.com/news/detail-615719.html
到了这里，关于整数替换（力扣）HashMap + 递归 JAVA的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
