将整数减少到零需要的最少操作数 图解题解
这道题到底在问什么
- 输入
- n = 39
- 输出
- 3 (加 1 到 40,减 8 到 32,减 32 到 0)
- 输入
- n = 54
- 输出
- 3 (加 2 到 56,加 8 到 64,减 64 到 0)
最优解：一步一步想明白
- 3记牢这套口诀:连续 1 短就减、长就进位,进位会往高位带一个 1,扫完别忘了结算最高段。下面从 n = 39 开始,每一帧都在套它。
- 4先把 39 写成二进制 100111。约定从最右边这一位(也就是最低位)往左看,一路维护两个数:cnt 记现在攒了几个连续的 1,ans 记一共花了几次操作。开局两个都是 0。
- 5指针移到从右数第 0 位,这一位是 1。1 能接上前面那串连续的 1,把连续段拉长,先攒着不动手。
- 6这一位是 1,连续段又长了一格,cnt 变成 1。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
- 7指针移到从右数第 1 位,这一位是 1。1 能接上前面那串连续的 1,把连续段拉长,先攒着不动手。
- 8这一位是 1,连续段又长了一格,cnt 变成 2。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
- 9指针移到从右数第 2 位,这一位是 1。1 能接上前面那串连续的 1,把连续段拉长,先攒着不动手。
- 10这一位是 1,连续段又长了一格,cnt 变成 3。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
- 11指针移到从右数第 3 位,这一位是 0。它前面正攒着 cnt = 3 个连续的 1,这一段该结算了。
- 12这一位是 0,前面攒了 3 个连续的 1。一串两个以上的 1,与其一个个减,不如加 1 让它整体进位,只花 1 次操作。进位产生的 1 顶到当前这个 0 的位置上,成为新连续段的起点,所以 cnt 归 1,ans 变成 1。绿色从那一长串挪到了这一格。
- 13指针移到从右数第 4 位,这一位是 0。它前面正攒着 cnt = 1 个连续的 1,这一段该结算了。
- 14这一位是 0,前面只攒了 1 个 1。孤零零一个 1,最划算的就是直接减掉它对应的那个 2 的幂,花 1 次操作,ans 变成 2,连续段清零。
- 15指针移到从右数第 5 位,这一位是 1。1 能接上前面那串连续的 1,把连续段拉长,先攒着不动手。
- 16这一位是 1,连续段又长了一格,cnt 变成 1。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
- 17所有位都扫完了,但手上还攒着 cnt = 1 一个单独的 1。循环里只有碰到 0 才结算,最高位上面没有更高的 0 来触发,所以要在这里补一次:这个单独的 1 减掉,ans 变成 3。这就是最终答案。
- 18换第二个例子 n = 54,二进制是 110110。套路你已经熟了,这一遍走快一点。重点看低位那段连续 1 进位后带上去的 1,会接上最高处的两个 1,在顶端汇成 cnt = 3 的一段,扫完再对这一段补 2 步。
- 19这一位是 0,手上也没攒着连续段,什么都不做,指针继续往左移。
- 20这一位是 1,连续段又长了一格,cnt 变成 1。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
- 21这一位是 1,连续段又长了一格,cnt 变成 2。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
- 22这一位是 0,前面攒了 2 个连续的 1。一串两个以上的 1,与其一个个减,不如加 1 让它整体进位,只花 1 次操作。进位产生的 1 顶到当前这个 0 的位置上,成为新连续段的起点,所以 cnt 归 1,ans 变成 1。绿色从那一长串挪到了这一格。
- 23这一位是 1,连续段又长了一格,cnt 变成 2。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
- 24这一位是 1,连续段又长了一格,cnt 变成 3。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
- 25所有位都扫完了,手上还攒着 cnt = 3 个连续的 1。这一段在最高处,先加 1 进位把它合并成更高位的一个 1(1 次),这个单独的 1 再减掉(1 次),一共补 2 次,ans 变成 3。这就是最终答案。
⚠️ 容易写错的地方
✗ 错：把每个 1 都单独减掉
✓ 对：连续 ≥ 2 个 1 用一次进位合并更省
三个连续的 1 单独减要 3 步,进位合并后只需 2 步,越长的连续段省得越多
✗ 错：忘了扫完还要结算最高处剩下的连续段
✓ 对：循环结束后按 cnt 是 1 还是 ≥ 2 补 1 步或 2 步
最高段上面没有更高的 0 来触发结算,漏掉这一步答案会偏小
✗ 错：以为答案就等于二进制里 1 的个数
✓ 对：连续的 1 会被进位合并,答案通常更小
39 的二进制有 4 个 1,答案却是 3,因为末尾三个连续 1 只花了 2 步
✗ 错：从高位往低位扫
✓ 对：必须从最低位起往高位扫
进位是往高位方向传的,方向反了,低位连续段对高位的影响就算不对
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def minOperations(self, n: int) -> int:
ans = cnt = 0
while n:
if n & 1:
cnt += 1
elif cnt:
ans += 1
cnt = 0 if cnt == 1 else 1
n >>= 1
if cnt == 1:
ans += 1
elif cnt > 1:
ans += 2
return ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int minOperations(int n) {
int ans = 0, cnt = 0;
for (; n > 0; n >>= 1) {
if ((n & 1) == 1) {
++cnt;
} else if (cnt > 0) {
++ans;
cnt = cnt == 1 ? 0 : 1;
}
}
ans += cnt == 1 ? 1 : 0;
ans += cnt > 1 ? 2 : 0;
return ans;
}
};Java
import java.util.*;
class Solution {
public int minOperations(int n) {
int ans = 0, cnt = 0;
for (; n > 0; n >>= 1) {
if ((n & 1) == 1) {
++cnt;
} else if (cnt > 0) {
++ans;
cnt = cnt == 1 ? 0 : 1;
}
}
ans += cnt == 1 ? 1 : 0;
ans += cnt > 1 ? 2 : 0;
return ans;
}
}复杂度
时间
O(log n)
只遍历 n 的二进制位,位数是 log n 量级;n 最大 10 的 5 次方,也就十七位左右。循环外再补一次结算是常数,整体随位数线性,不随 n 的数值大小成比例增长
空间
O(1)
全程只用 cnt 和 ans 两个整数变量,不开数组、不用递归栈,占用与 n 无关,是常数空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 将整数减少到零需要的最少操作数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这个按位贪心为什么是对的?+
关键在于对一段连续的 1。长度为 1 时只能减,花 1 步;长度 ≥ 2 时,加 1 进位把整段合并成更高位的一个 1,只花 1 步,还顺手缩小了问题。逐位从低到高处理,每一段都取更省的那种,合起来就是全局最优。这个结论也能用动态规划严格证明,但按位贪心足够拿下。
时间和空间复杂度是多少?+
时间 O(log n),只扫 n 的二进制位数,最多十几位;空间 O(1),只用了 cnt 和 ans 两个变量,没有额外数组,也没有递归栈。
三种语言写法有区别吗?+
思路完全一样。Python 用 while n 配合右移一位、判断 n 与 1;C++ 和 Java 用 for 循环,条件是 n 大于 0、每轮右移一位。结算连续段的三元判断,和循环外补操作数的两句,三家都一致。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 将整数减少到零需要的最少操作数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。