class Solution {
public:
int integerReplacement(int n) {
}
};
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原站题解
javascript 解法, 执行用时: 68 ms, 内存消耗: 40.9 MB, 提交时间: 2023-10-10 23:18:56
/**
* @param {number} n
* @return {number}
*/
var integerReplacement = function(n) {
if (n === 1) {
return 0;
}
if (n % 2 === 0) {
return 1 + integerReplacement(Math.floor(n / 2));
}
return 2 + Math.min(integerReplacement(Math.floor(n / 2)), integerReplacement(Math.floor(n / 2) + 1));
};
const memo = new Map();
var integerReplacement2 = function(n) {
if (n === 1) {
return 0;
}
if (!memo.has(n)) {
if (n % 2 === 0) {
memo.set(n, 1 + integerReplacement(Math.floor(n / 2)));
} else {
memo.set(n, 2 + Math.min(integerReplacement(Math.floor(n / 2)), integerReplacement(Math.floor(n / 2) + 1)));
}
}
return memo.get(n);
};
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-10-10 23:18:23
var memo map[int]int
func _integerReplacement(n int) (res int) {
if n == 1 {
return 0
}
if res, ok := memo[n]; ok {
return res
}
defer func() { memo[n] = res }()
if n%2 == 0 {
return 1 + _integerReplacement(n/2)
}
return 2 + min(_integerReplacement(n/2), _integerReplacement(n/2+1))
}
func integerReplacement(n int) (res int) {
memo = map[int]int{}
return _integerReplacement(n)
}
func integerReplacement1(n int) int {
if n == 1 {
return 0
}
if n%2 == 0 {
return 1 + integerReplacement(n/2)
}
return 2 + min(integerReplacement(n/2), integerReplacement(n/2+1))
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
python3 解法, 执行用时: 32 ms, 内存消耗: 16.1 MB, 提交时间: 2023-10-10 23:17:43
class Solution:
def integerReplacement1(self, n: int) -> int:
if n == 1:
return 0
if n % 2 == 0:
return 1 + self.integerReplacement(n // 2)
return 2 + min(self.integerReplacement(n // 2), self.integerReplacement(n // 2 + 1))
@cache
def integerReplacement(self, n: int) -> int:
if n == 1:
return 0
if n % 2 == 0:
return 1 + self.integerReplacement(n // 2)
return 2 + min(self.integerReplacement(n // 2), self.integerReplacement(n // 2 + 1))
java 解法, 执行用时: 0 ms, 内存消耗: 38 MB, 提交时间: 2023-10-10 23:17:10
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);
}
public int integerReplacement2(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));
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.5 MB, 提交时间: 2023-10-10 23:16:25
class Solution {
private:
unordered_map<int, int> memo;
public:
// 记忆化搜索
int integerReplacement(int n) {
if (n == 1) {
return 0;
}
if (memo.count(n)) {
return memo[n];
}
if (n % 2 == 0) {
return memo[n] = 1 + integerReplacement(n / 2);
}
return memo[n] = 2 + min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
}
// 枚举所有情况
int integerReplacement2(int n) {
if (n == 1) {
return 0;
}
if (n % 2 == 0) {
return 1 + integerReplacement(n / 2);
}
return 2 + min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
}
};