Article / 文章
LeetCode第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
博客摘要：本文深入解析LeetCode第397题“整数替换”，这是一道中等难度的递归与动态规划题目。文章详细分析了贪心策略的数学原理，特别是对于奇数时选择+1还是-1的判断依据，并提供递归、记忆化递归和迭代三种解法。适合想要深入理解位运算优化和贪心算法的读者学习，帮助掌握此类优化问题的解题思路。
题目描述
给定一个正整数 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
题目链接：LeetCode 397. 整数替换
解题思路
这道题看似简单，但奇数情况下的选择策略是关键。我们需要找到一个贪心策略来决定何时选择+1，何时选择-1。
核心策略
对于偶数：直接除以2，没有选择余地。
对于奇数：需要选择+1或-1，关键在于选择后能更快到达1。
贪心判断依据
对于奇数n，我们分析(n+1)/2和(n-1)/2：
- 如果
(n+1)/2是偶数，选择+1更优 - 如果
(n-1)/2是偶数，选择-1更优
位运算判断：
n & 3 == 1时选择-1（等价于n % 4 == 1）n & 3 == 3时选择+1（等价于n % 4 == 3）- 特殊情况：
n == 3时选择-1
算法原理
数学分析
为什么n % 4 == 1时选择-1，n % 4 == 3时选择+1？
当n ≡ 1 (mod 4)时：
n = 4k + 1n - 1 = 4k，可以连续除以2两次n + 1 = 4k + 2 = 2(2k + 1)，只能除以2一次，然后又是奇数
当n ≡ 3 (mod 4)时：
n = 4k + 3n + 1 = 4k + 4 = 4(k + 1)，可以连续除以2两次n - 1 = 4k + 2 = 2(2k + 1)，只能除以2一次，然后又是奇数
特殊情况
n = 3是唯一的例外：
3 - 1 = 2 → 1（2步）3 + 1 = 4 → 2 → 1（3步）
所以n = 3时选择-1更优。
复杂度分析
递归解法
-
时间复杂度：O(log n)
- 每次操作都会使数字大约减半
- 递归深度为O(log n)
-
空间复杂度：O(log n)
- 递归调用栈的深度
迭代解法
-
时间复杂度：O(log n)
- 循环次数与递归深度相同
-
空间复杂度：O(1)
- 只使用常数额外空间
图解思路
示例：n = 7
方法1：7 -> 6 -> 3 -> 2 -> 1 (4次)
奇数 偶数 奇数 偶数
方法2：7 -> 8 -> 4 -> 2 -> 1 (4次)
奇数 偶数 偶数 偶数
贪心策略分析：
7 % 4 = 3，选择 +1
7 -> 8 -> 4 -> 2 -> 1决策过程
| 当前值 | 类型 | 操作选择 | 依据 | 下一步 |
|---|---|---|---|---|
| n=8 | 偶数 | /2 | 无选择 | 4 |
| n=7 | 奇数 | +1 | 7%4=3 | 8 |
| n=5 | 奇数 | -1 | 5%4=1 | 4 |
| n=3 | 奇数 | -1 | 特殊情况 | 2 |
代码实现
C# 实现
public class Solution {
public int IntegerReplacement(int n) {
// 递归解法
return Helper((long)n);
}
private int Helper(long n) {
if (n == 1) return 0;
if (n % 2 == 0) {
// 偶数直接除以2
return 1 + Helper(n / 2);
} else {
// 奇数采用贪心策略
if (n == 3 || n % 4 == 1) {
return 1 + Helper(n - 1);
} else {
return 1 + Helper(n + 1);
}
}
}
// 迭代解法
public int IntegerReplacementIterative(int n) {
long num = n;
int count = 0;
while (num != 1) {
if (num % 2 == 0) {
num /= 2;
} else {
if (num == 3 || num % 4 == 1) {
num--;
} else {
num++;
}
}
count++;
}
return count;
}
}Python 实现
class Solution:
def integerReplacement(self, n: int) -> int:
# 递归解法
if n == 1:
return 0
if n % 2 == 0:
return 1 + self.integerReplacement(n // 2)
else:
# 贪心策略：n==3或n%4==1时选择-1，否则选择+1
if n == 3 or n % 4 == 1:
return 1 + self.integerReplacement(n - 1)
else:
return 1 + self.integerReplacement(n + 1)
def integerReplacementIterative(self, n: int) -> int:
# 迭代解法
count = 0
while n != 1:
if n % 2 == 0:
n //= 2
else:
if n == 3 or n % 4 == 1:
n -= 1
else:
n += 1
count += 1
return count
def integerReplacementMemo(self, n: int) -> int:
# 记忆化递归
memo = {}
def dfs(num):
if num == 1:
return 0
if num in memo:
return memo[num]
if num % 2 == 0:
result = 1 + dfs(num // 2)
else:
if num == 3 or num % 4 == 1:
result = 1 + dfs(num - 1)
else:
result = 1 + dfs(num + 1)
memo[num] = result
return result
return dfs(n)C++ 实现
class Solution {
public:
int integerReplacement(int n) {
return helper((long long)n);
}
private:
int helper(long long n) {
if (n == 1) return 0;
if (n % 2 == 0) {
return 1 + helper(n / 2);
} else {
// 贪心策略
if (n == 3 || n % 4 == 1) {
return 1 + helper(n - 1);
} else {
return 1 + helper(n + 1);
}
}
}
public:
// 迭代解法
int integerReplacementIterative(int n) {
long long num = n;
int count = 0;
while (num != 1) {
if (num % 2 == 0) {
num /= 2;
} else {
if (num == 3 || (num & 3) == 1) { // 位运算优化
num--;
} else {
num++;
}
}
count++;
}
return count;
}
// 记忆化递归
unordered_map<long long, int> memo;
int integerReplacementMemo(int n) {
return dfsMemo((long long)n);
}
int dfsMemo(long long n) {
if (n == 1) return 0;
if (memo.count(n)) return memo[n];
int result;
if (n % 2 == 0) {
result = 1 + dfsMemo(n / 2);
} else {
if (n == 3 || (n & 3) == 1) {
result = 1 + dfsMemo(n - 1);
} else {
result = 1 + dfsMemo(n + 1);
}
}
return memo[n] = result;
}
};执行结果
C# 实现
- 执行用时：28 ms
- 内存消耗：27.1 MB
Python 实现
- 执行用时：36 ms
- 内存消耗：16.8 MB
C++ 实现
- 执行用时：0 ms
- 内存消耗：6.1 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C++ | 0 ms | 6.1 MB | 性能最优，位运算优化效果显著 |
| C# | 28 ms | 27.1 MB | 递归调用栈开销较大 |
| Python | 36 ms | 16.8 MB | 语法简洁，递归深度限制需注意 |
代码亮点
- 🎯 贪心策略优化：通过数学分析找到最优选择规律，避免暴力搜索
- 💡 位运算优化：使用
n & 3代替n % 4，提升运算效率 - 🔍 溢出处理：使用long long防止n+1时的整数溢出
- 🎨 多种实现：提供递归、记忆化递归、迭代三种解法供选择
常见错误分析
- 🚫 忽略整数溢出：当n接近INT_MAX时，n+1会溢出
- 🚫 贪心策略错误：没有理解为什么要选择特定的+1或-1操作
- 🚫 特殊情况遗漏：忘记处理n=3的特殊情况
- 🚫 递归深度过大：对于大数值可能导致栈溢出，应使用迭代
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 递归 | O(log n) | O(log n) | 代码简洁，思路清晰 | 可能栈溢出 |
| 记忆化递归 | O(log n) | O(log n) | 避免重复计算 | 空间开销大 |
| 迭代 | O(log n) | O(1) | 空间最优，无栈溢出风险 | 代码稍长 |
| 暴力BFS | O(2^log n) | O(2^log n) | 思路直观 | 时间空间都很差 |
相关题目
- LeetCode 326. 3的幂 - 简单
- LeetCode 342. 4的幂 - 简单
- LeetCode 365. 水壶问题 - 中等
- LeetCode 319. 灯泡开关 - 中等
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第397题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！