文章目录摘要描述题解答案题解代码分析为什么偶数直接除以 2奇数时为什么看 n % 4为什么 n3 要特殊处理用循环而不是递归示例 2 简要过程n 7示例测试及结果示例 1n 8示例 2n 7示例 3n 4示例 4n 3示例 5n 1时间复杂度空间复杂度实际应用场景总结摘要这道题给一个正整数 n每次可以若 n 是偶数则用 n/2 替换若 n 是奇数则用 n1 或 n-1 替换。问最少几步能把 n 变成 1。暴力可以做 BFS 或记忆化搜索但 n 最大到 2^31-1状态太多。用贪心偶数一定除以 2奇数时希望下一步能多除几次 2所以看 n 模 4——若 n4k1 选 n-1 得到 2k 能再除一次 2若 n4k3 选 n1 得到 2k2 能再除一次 2。特例是 n33→2→1 两步3→4→2→1 三步所以 3 要选 n-1。按这个规则迭代或递归即可在 O(log n) 内得到最少步数。下面用 Swift 实现并说明贪心依据。描述给定正整数 n可以做两种操作若 n 为偶数用 n/2 替换 n若 n 为奇数用 n1 或 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并单独处理 n3。题解答案classSolution{funcintegerReplacement(_n:Int)-Int{varnumnvarsteps0whilenum!1{ifnum%20{num/2steps1}else{ifnum3{num2steps1}elseifnum%41{num-1steps1}else{num1steps1}}}returnsteps}}题解代码分析为什么偶数直接除以 2偶数时只有一种操作n/2。除以 2 能让数尽快变小且不会「浪费」一步去做 1/-1 再等下次除 2所以偶数时一定选 n/2。奇数时为什么看 n % 4奇数只能 1 或 -1变成偶数后再除 2。我们希望「下一步能连续除 2 的次数尽量多」这样更快接近 1。设 n2k1则 n-12k、n12k2。再除一次 2 得到 k 和 k1。若 k 是偶数则 (n-1)/2 还能再除 2若 k1 是偶数则 (n1)/2 还能再除 2。n4k1 时(n-1)/22k 为偶(n1)/22k1 为奇选 n-1 更有利。n4k3 时(n-1)/22k1 为奇(n1)/22k2 为偶选 n1 更有利。所以规则是n % 4 1 用 n-1n % 4 3 用 n1。为什么 n3 要特殊处理n3 时 3 % 4 3按上面会选 n1 得到 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 77 为奇且 7 % 4 3选 1 → 88 为偶 → 4 → 2 → 1。共 4 步与输出一致。示例测试及结果示例 1n 88→4→2→13 步输出3。示例 2n 77→8→4→2→14 步输出4。示例 3n 44→2→12 步输出2。示例 4n 33→2→12 步若按 %4 选 1 会得到 3 步特例处理后为 2。示例 5n 1已是 10 步输出0题目 n1若传入 1 则循环不执行返回 0。时间复杂度每次要么除以 2n 至少减半要么 ±1 后变成偶数再除整体规模约每次减半或接近减半步数 O(log n)单次操作 O(1)总时间O(log n)。空间复杂度只用了若干变量O(1)。实际应用场景类似「用最少步数把数变成 1」的规则在游戏步数、状态机最简路径、或某些编码/解码步数分析里会碰到。贪心「能除 2 就除、奇数时选下一步更能除」的思路在规则简单、有明确「更优下一步」时常用。总结整数替换的最小步数可以用贪心偶数一律 n/2奇数时 n % 4 1 用 n-1n % 4 3 用 n1并单独把 n3 设为 n-1。按此规则迭代直到 n 变为 1步数即为答案时间 O(log n)、空间 O(1)。