整数替换 图解题解
这道题到底在问什么
- n
- 8
- 输出
- 3
- 路径
- 8 → 4 → 2 → 1
最优解：一步一步想明白
- 38 → 4 → 2 → 1思路：玄机全在二进制，/2 = 右移一位。先用纯偶数 8（二进制 01000，步数 0）热身，把数步数、右移的流程跑顺。下面一步步演给你看。
- 48 / 2 = 4末位的 0 被丢掉,1 整体右移。8 变 4,走了 1 步。
- 54 / 2 = 2还是偶数,再右移一位。4 变 2,第 2 步。
- 62 / 2 = 1 ✓再右移到只剩末位的 1,到达 1!8 共走 3 步。偶数全程一路 /2,毫无悬念。
- 7二进制里末位连续的 0 越多,接下来能连着 /2 的次数就越多。所以奇数时要选「让低位多出 0」的那一边——这就是全题的贪心核心。
- 8把奇数末两位 11 加 1,会像多米诺一样进位,低位连出好几个 0;末两位 01 减 1 直接得 0。盯住下面要演的末两位。
- 97 的二进制 00111换个奇数 7 走全程。7 的二进制是 00111,是奇数(末位 1),要决定 +1 还是 −1。
- 10末两位 11 → 选 +1把最右边两个格子圈出来:11。按口诀,末两位是 11 就 +1——加 1 会触发连续进位,低位一下清出两个 0。
- 11进位!00111 → 010007 + 1 = 8。看二进制:末尾 111 全进位翻成 000,只在高位冒出一个 1。低位三个 0意味着接下来能连 /2 三次!第 1 步。
- 128 / 2 = 4现在是偶数,右移一位。8 变 4,第 2 步。
- 134 / 2 = 2还是偶数,继续右移。4 变 2,第 3 步。
- 142 / 2 = 1 ✓最后一步右移到 1!7 全程 7→8→4→2→1,共 4 步。当初选 +1 制造的三个 0,直接换来三次连除。
- 157−1=6 路更长假如 7 偷懒选 −1 得 6(00110),只清出一个末位 0;接着 6→3 又是奇数还得抉择。绕一圈才到 1,印证了「末两位 11 该 +1」。
- 1615 的二进制 01111再看 15(01111)。奇数,末两位是 11——又该 +1,而且这次进位能清出一长串 0。
- 17末两位 11 → +1圈出末两位 11,按规则 +1。15 + 1 = 16,马上看二进制会变成什么样。
- 18全进位 → 1000016 = 10000:低位四个 0排成一排!接下来能一口气连除 4 次 /2。第 1 步。
- 19右移一位偶数右移。16 变 8,第 2 步。
- 20右移一位继续右移。8 变 4,第 3 步。
- 21右移一位再右移。4 变 2,第 4 步。
- 22到达 1 ✓最后右移到 1!15 全程 5 步。一次聪明的 +1 把后面铺成了 4 次连除——这就是末两位 11 选 +1 的威力。
- 23如 n=5 = 00101反过来,若奇数末两位是 01(如 5),−1 直接把末位的 1 抹成 0;若硬要 +1 反而得 6,低位只多一个 0、还更大。所以 01 选 −1。
- 24末两位 11 但要 −1唯一的例外:3 末两位也是 11,但它太小——−1 走 3→2→1 只要 2 步,+1 走 3→4→2→1 反而 3 步。所以规则要单独把 n==3 拦下来选 −1。
⚠️ 容易写错的地方
✗ 错：奇数无脑 −1
✓ 对：看末两位:11 → +1,01 → −1
11 时 −1 只清一个 0,+1 进位清一串 0,后面能连除更多次
✗ 错：忘了 n==3 的特例
✓ 对：n==3 强制 −1
3 末两位也是 11,但 +1 会绕远(3→4→2→1=3 步,3→2→1 只要 2 步)
✗ 错：用 int 存 n+1
✓ 对：C++/Java 用 long
n 可能 = INT_MAX(2147483647),+1 会整型溢出变负数
完整代码（Python / C++ / Java）
Python
class Solution:
def integerReplacement(self, n):
steps = 0
while n != 1:
if n % 2 == 0: # 偶数:右移
n //= 2
elif n == 3 or n % 4 == 1: # 末两位01 或 n=3 → -1
n -= 1
else: # 末两位11 → +1
n += 1
steps += 1
return stepsC++
class Solution {
public:
int integerReplacement(int n) {
long x = n; // 防 INT_MAX+1 溢出
int steps = 0;
while (x != 1) {
if (x % 2 == 0) x /= 2;
else if (x == 3 || x % 4 == 1) x -= 1;
else x += 1;
steps++;
}
return steps;
}
};Java
class Solution {
public int integerReplacement(int n) {
long x = n; // 防 INT_MAX+1 溢出
int steps = 0;
while (x != 1) {
if (x % 2 == 0) x /= 2;
else if (x == 3 || x % 4 == 1) x -= 1;
else x += 1;
steps++;
}
return steps;
}
}复杂度
时间复杂度
O(log n)
每步要么 /2(规模减半),要么 ±1 后下一步必 /2 → 大约 2log n 次操作,量级 O(log n)
空间复杂度
O(1)
只用了 steps 和当前值两个变量,没有额外结构
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 整数替换 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么贪心看末两位就对?+
目标是制造更多低位 0 以便连除。末两位 01 时 −1 直接把末位 1 变 0;末两位 11 时 +1 触发进位把一串 1 清成 0,比 −1 清得更多。唯一例外是 n=3(太小,+1 反而绕远)。
为什么是 O(log n)?+
每次 /2 规模减半;每次 ±1 之后下一步必然是偶数能 /2。所以大约每两步规模减半,总步数与 n 的二进制位数同量级。
为什么 C++/Java 要用 long?+
n 最大可为 INT_MAX=2147483647,奇数时 n+1 会超出 int 范围溢出成负数,用 long 存储避免。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 整数替换 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。