LeetCode 397 整数替换

文章目录

• • 摘要
  • 描述
  • 题解答案
  • 题解代码分析
  • • 为什么偶数直接除以 2
    • 奇数时为什么看 n % 4
    • 为什么 n=3 要特殊处理
    • 用循环而不是递归
    • 示例 2 简要过程：n = 7
  • 示例测试及结果
  • • 示例 1：n = 8
    • 示例 2：n = 7
    • 示例 3：n = 4
    • 示例 4：n = 3
    • 示例 5：n = 1
  • 时间复杂度
  • 空间复杂度
  • 实际应用场景
  • 总结

摘要

这道题给一个正整数 n，每次可以：若 n 是偶数则用 n/2 替换；若 n 是奇数则用 n+1 或 n-1 替换。问最少几步能把 n 变成 1。

暴力可以做 BFS 或记忆化搜索，但 n 最大到 2^31-1，状态太多。用贪心：偶数一定除以 2；奇数时，希望下一步能多除几次 2，所以看 n 模 4——若 n=4k+1 选 n-1 得到 2k 能再除一次 2，若 n=4k+3 选 n+1 得到 2k+2 能再除一次 2。特例是 n=3：3→2→1 两步，3→4→2→1 三步，所以 3 要选 n-1。按这个规则迭代或递归即可在 O(log n) 内得到最少步数。下面用 Swift 实现并说明贪心依据。

描述

给定正整数 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

核心思路：偶数一律除以 2；奇数时用「下一步能多除 2」的贪心选 +1 或 -1，并单独处理 n=3。

题解答案

class Solution {
func integerReplacement(_ n: Int) -> Int {
var num = n
var steps = 0
while num != 1 {
if num % 2 == 0 {
num /= 2
steps += 1
} else {
if num == 3 {
num = 2
steps += 1
} else if num % 4 == 1 {
num -= 1
steps += 1
} else {
num += 1
steps += 1
}
}
}
return steps
}
}

题解代码分析

为什么偶数直接除以 2

偶数时只有一种操作：n/2。除以 2 能让数尽快变小，且不会「浪费」一步去做 +1/-1 再等下次除 2，所以偶数时一定选 n/2。

奇数时为什么看 n % 4

奇数只能 +1 或 -1，变成偶数后再除 2。我们希望「下一步能连续除 2 的次数尽量多」，这样更快接近 1。设 n=2k+1，则 n-1=2k、n+1=2k+2。再除一次 2 得到 k 和 k+1。若 k 是偶数，则 (n-1)/2 还能再除 2；若 k+1 是偶数，则 (n+1)/2 还能再除 2。n=4k+1 时：(n-1)/2=2k 为偶，(n+1)/2=2k+1 为奇，选 n-1 更有利。n=4k+3 时：(n-1)/2=2k+1 为奇，(n+1)/2=2k+2 为偶，选 n+1 更有利。所以规则是：n % 4 == 1 用 n-1，n % 4 == 3 用 n+1。

为什么 n=3 要特殊处理

n=3 时 3 % 4 == 3，按上面会选 n+1 得到 4，路径 3→4→2→1 共 3 步。但若选 n-1 得到 2，路径 3→2→1 只要 2 步。原因是 3 离 1 已经很近，+1 反而多绕一步。所以单独判断：若 n == 3 则用 n-1。

用循环而不是递归

n 最大 2^31-1，按上述规则步数约为 O(log n)，循环迭代 log n 次即可，避免递归栈。用 var num = n 和 while num != 1 每次按规则更新 num 并累加 steps，最后返回 steps。

示例 2 简要过程：n = 7

7 为奇且 7 % 4 == 3，选 +1 → 8；8 为偶 → 4 → 2 → 1。共 4 步，与输出一致。

示例测试及结果

示例 1：n = 8

8→4→2→1，3 步，输出 3。

示例 2：n = 7

7→8→4→2→1，4 步，输出 4。

示例 3：n = 4

4→2→1，2 步，输出 2。

示例 4：n = 3

3→2→1，2 步（若按 %4 选 +1 会得到 3 步，特例处理后为 2）。

示例 5：n = 1

已是 1，0 步，输出 0（题目 n>=1，若传入 1 则循环不执行，返回 0）。

时间复杂度

每次要么除以 2（n 至少减半），要么 ±1 后变成偶数再除，整体规模约每次减半或接近减半，步数 O(log n)，单次操作 O(1)，总时间 O(log n)。

空间复杂度

只用了若干变量，O(1)。

实际应用场景

类似「用最少步数把数变成 1」的规则在游戏步数、状态机最简路径、或某些编码/解码步数分析里会碰到。贪心「能除 2 就除、奇数时选下一步更能除」的思路，在规则简单、有明确「更优下一步」时常用。

总结

整数替换的最小步数可以用贪心：偶数一律 n/2；奇数时 n % 4 == 1 用 n-1，n % 4 == 3 用 n+1，并单独把 n=3 设为 n-1。按此规则迭代直到 n 变为 1，步数即为答案，时间 O(log n)、空间 O(1)。