397. 整数替换
题目描述
输入一个正整数 n。每一步可以这样变换：当 n 是偶数时，把它换成 n / 2；当 n 是奇数时，可以换成 n + 1，也可以换成 n - 1。
返回把 n 变成 1 最少需要多少步。
输入：n = 8 输出：3
解释：8 -> 4 -> 2 -> 1。
输入：n = 7 输出：4
解释：7 -> 8 -> 4 -> 2 -> 1 或 7 -> 6 -> 3 -> 2 -> 1，都需要 4 步。
输入：n = 4 输出：2
解释：4 -> 2 -> 1。
数据范围
1 <= n <= 2^31 - 1
解题思路：记忆化搜索
设 f(x) 为把 x 变成 1 的最少步数，f(1) = 0。偶数只有一种走法：f(x) = f(x/2) + 1；奇数要比较两条路：f(x) = min(f(x-1), f(x+1)) + 1。x-1 与 x+1 都是偶数，下一步立刻减半，所以递归深度只有 O(log n)。不同的子问题会反复出现（例如 (x-1)/2 和 (x+1)/2 的后代互相重叠），用记忆化缓存避免重复计算。
为什么正确
缓存里的每个 f(x) 都已经是 x 变成 1 的最少步数；任何一次调用只在所有子调用得到最优值后才写入缓存。
复杂度分析
时间 O(log n)：每一层最多出现两个相邻的数，状态数约 2 log n。空间 O(log n)，用于缓存和递归栈。
易错点
奇数时直接 n + 1 可能超出 32 位整数范围（n = 2^31 - 1），C++/Java 要用 long。另外 3 是特例：3 -> 2 -> 1 比 3 -> 4 -> 2 -> 1 少一步，贪心规则要单独处理它。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def integerReplacement(self, n: int) -> int:
@functools.lru_cache(None)
def f(x):
if x == 1:
return 0
if x % 2 == 0:
return f(x // 2) + 1
return min(f(x - 1), f(x + 1)) + 1
return f(n)class Solution {
Map<Long, Integer> memo = new HashMap<>();
int f(long x) {
if (x == 1) {
return 0;
}
if (memo.containsKey(x)) {
return memo.get(x);
}
int r;
if (x % 2 == 0) {
r = f(x / 2) + 1;
} else {
r = Math.min(f(x - 1), f(x + 1)) + 1;
}
memo.put(x, r);
return r;
}
public int integerReplacement(int n) {
return f(n);
}
}class Solution {
public:
unordered_map<long long, int> memo;
int f(long long x) {
if (x == 1) {
return 0;
}
if (memo.count(x)) {
return memo[x];
}
int r;
if (x % 2 == 0) {
r = f(x / 2) + 1;
} else {
r = min(f(x - 1), f(x + 1)) + 1;
}
memo[x] = r;
return r;
}
int integerReplacement(int n) {
return f(n);
}
};func integerReplacement(n int) int {
memo := map[int]int{}
var f func(x int) int
f = func(x int) int {
if x == 1 {
return 0
}
if v, ok := memo[x]; ok {
return v
}
var r int
if x%2 == 0 {
r = f(x/2) + 1
} else {
r = min(f(x-1), f(x+1)) + 1
}
memo[x] = r
return r
}
return f(n)
}var integerReplacement = function(n) {
const memo = new Map();
const f = (x) => {
if (x === 1) {
return 0;
}
if (memo.has(x)) {
return memo.get(x);
}
let r;
if (x % 2 === 0) {
r = f(x / 2) + 1;
} else {
r = Math.min(f(x - 1), f(x + 1)) + 1;
}
memo.set(x, r);
return r;
};
return f(n);
};function integerReplacement(n: number): number {
const memo = new Map<number, number>();
const f = (x: number): number => {
if (x === 1) {
return 0;
}
if (memo.has(x)) {
return memo.get(x)!;
}
let r: number;
if (x % 2 === 0) {
r = f(x / 2) + 1;
} else {
r = Math.min(f(x - 1), f(x + 1)) + 1;
}
memo.set(x, r);
return r;
};
return f(n);
}其他解法
记忆化搜索把两种选择都试一遍再取较小值；贪心直接根据二进制末两位做出最优选择，省掉了搜索和缓存。
解法 2：贪心（看二进制末两位） 时间 O(log n)，空间 O(1)
n 为偶数时直接除以 2。n 为奇数时看二进制末两位：末两位是 01 就减 1，末两位是 11 就加 1，这样下一步能连续除以 2 的次数更多。唯一例外是 n = 3，减 1 更优。循环到 n = 1 为止，统计步数。
不需要递归和哈希表，空间 O(1)。正确性依赖对末两位的分析，不如记忆化搜索直观。加 1 可能超出 32 位整数，需要用 64 位整数。
class Solution:
def integerReplacement(self, n):
ans = 0
while n != 1:
if n % 2 == 0:
n //= 2
elif n == 3 or n % 4 == 1:
n -= 1
else:
n += 1
ans += 1
return ansclass Solution {
public int integerReplacement(int n) {
long x = n;
int ans = 0;
while (x != 1) {
if (x % 2 == 0) x /= 2;
else if (x == 3 || x % 4 == 1) x--;
else x++;
ans++;
}
return ans;
}
}class Solution {
public:
int integerReplacement(int n) {
long long x = n;
int ans = 0;
while (x != 1) {
if (x % 2 == 0) x /= 2;
else if (x == 3 || x % 4 == 1) x--;
else x++;
ans++;
}
return ans;
}
};func integerReplacement(n int) int {
ans := 0
for n != 1 {
if n%2 == 0 {
n /= 2
} else if n == 3 || n%4 == 1 {
n--
} else {
n++
}
ans++
}
return ans
}var integerReplacement = function(n) {
let ans = 0;
while (n !== 1) {
if (n % 2 === 0) n /= 2;
else if (n === 3 || n % 4 === 1) n--;
else n++;
ans++;
}
return ans;
};function integerReplacement(n: number): number {
let ans = 0;
while (n !== 1) {
if (n % 2 === 0) n /= 2;
else if (n === 3 || n % 4 === 1) n--;
else n++;
ans++;
}
return ans;
}