题目描述
思路解析
一句话答案：LeetCode 2571 将整数减少到零需要的最少操作数：按位贪心从低位扫二进制，孤立的 1 直接减，连续一串 1 加一个 2 的幂整体进位更省，扫完补结算最高段。时间 O(log n)、空间 O(1)。
每次加减一个 2 的幂，怎样最快把 n 清零
给一个正整数 n，每次操作给它加上或减去一个 2 的幂——1、2、4、8 这些 2 自乘出来的数，问最少几次能把 n 变成 0。题面例子：39 加 1 到 40、减 8 到 32、再减 32 到 0，3 步；54 也是 3 步。
39 的二进制有 4 个 1，答案为什么不是 4
39 的二进制是 100111。二进制就是只用 0 和 1 记数，每一位分量从右往左依次是 1、2、4、8、16、32，最右那头叫低位；100111 里四个 1 的分量 32、4、2、1 正好凑成 39。
看着很对的答案：四个 1 各减自己那份要 4 次，可题面只要 3 次。差在低三位 111：逐个减要 3 次，而加 1 让整串逢二进一、一次归零，这一步叫进位。
一串连续的 1，为什么加一次比逐个减省
给两种手段各记个账。连续的 1 长度为 k：逐个减花 k 次；给最低位加它那份 2 的幂，让整段进位归零只花 1 次，代价是段顶多出一个 1、撑死再花 1 次。长度为 1 直接减最划算；到 2 及以上进位稳赚，5 个连续 1 逐减 5 次，进位加收尾只 2 次。
于是从低位往高位扫：遇 1 先攒着，cnt 记这段连续 1 攒了多长；遇 0 按段长结算。这是贪心（每步选当下更省的处理法），扫一遍出答案。
结算一段 1 时，cnt 为什么有时归 0 有时归 1
参考代码里 n & 1 取出最低位看是不是 1，n >>= 1 把 n 右挪一位、扔掉刚看过的那位。最低位是 1 就 cnt 加一；是 0 且 cnt 大于 0，一段连续 1 到头，ans 加 1 结算。
结算后 cnt 设成几有讲究：孤立的 1（cnt 为 1）直接减掉，cnt 归 0；连续 1（cnt 大于等于 2）走进位，顶出的新 1 落在这个 0 上、成为下段起点，cnt 归 1。
100111 扫六位，39 的 3 步从哪来
39 = 100111，cnt、ans 开局都是 0。第 0 位 1，cnt=1；第 1 位 1，cnt=2；第 2 位 1，cnt=3；第 3 位 0，段长 3 进位，ans=1、cnt 归 1，对应加 1 到 40；第 4 位 0，段长 1 直接减，ans=2、cnt 归 0，对应减 8 到 32；第 5 位 1，cnt=1。
六位扫完，手上还剩 cnt=1：最高段没有更高的 0 触发结算，循环外补 1 次，ans=3，减 32 清零，正是题面写的 3。54 = 110110 同一套：低处 11 进位记 1 次，顶上来的 1 和高处两个 1 汇成段长 3，扫完补 2 次，一共 3 次。
39 扫完就返回 ans，结果为什么只有 2
时间 O(log n)（大 O 是数据每多一位、操作量跟着长多少的记法），只扫 n 的二进制位，n 不超过 10 的 5 次方也就十七位；空间 O(1)，只有 cnt 和 ans 两个变量。
循环外那两行补结算最容易被删：扫完直接返回，39 输出 2、54 输出 1；cnt 剩 1 补 1 次、剩 2 个以上补 2 次。cnt 为 2 的段同样走进位、归 1；写成 3 个以上才进位，54 就答成 4。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这套口诀:连续 1 短就减、长就进位,进位会往高位带一个 1,扫完别忘了结算最高段。下面从 n = 39 开始,每一帧都在套它。
先把 39 写成二进制 100111。约定从最右边这一位(也就是最低位)往左看,一路维护两个数:cnt 记现在攒了几个连续的 1,ans 记一共花了几次操作。开局两个都是 0。
指针移到从右数第 0 位,这一位是 1。1 能接上前面那串连续的 1,把连续段拉长,先攒着不动手。
这一位是 1,连续段又长了一格,cnt 变成 1。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
指针移到从右数第 1 位,这一位是 1。1 能接上前面那串连续的 1,把连续段拉长,先攒着不动手。
这一位是 1,连续段又长了一格,cnt 变成 2。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
指针移到从右数第 2 位,这一位是 1。1 能接上前面那串连续的 1,把连续段拉长,先攒着不动手。
这一位是 1,连续段又长了一格,cnt 变成 3。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
指针移到从右数第 3 位,这一位是 0。它前面正攒着 cnt = 3 个连续的 1,这一段该结算了。
这一位是 0,前面攒了 3 个连续的 1。一串两个以上的 1,与其一个个减,不如加 1 让它整体进位,只花 1 次操作。进位产生的 1 顶到当前这个 0 的位置上,成为新连续段的起点,所以 cnt 归 1,ans 变成 1。绿色从那一长串挪到了这一格。
指针移到从右数第 4 位,这一位是 0。它前面正攒着 cnt = 1 个连续的 1,这一段该结算了。
这一位是 0,前面只攒了 1 个 1。孤零零一个 1,最划算的就是直接减掉它对应的那个 2 的幂,花 1 次操作,ans 变成 2,连续段清零。
指针移到从右数第 5 位,这一位是 1。1 能接上前面那串连续的 1,把连续段拉长,先攒着不动手。
这一位是 1,连续段又长了一格,cnt 变成 1。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
所有位都扫完了,但手上还攒着 cnt = 1 一个单独的 1。循环里只有碰到 0 才结算,最高位上面没有更高的 0 来触发,所以要在这里补一次:这个单独的 1 减掉,ans 变成 3。这就是最终答案。
换第二个例子 n = 54,二进制是 110110。套路你已经熟了,这一遍走快一点。重点看低位那段连续 1 进位后带上去的 1,会接上最高处的两个 1,在顶端汇成 cnt = 3 的一段,扫完再对这一段补 2 步。
这一位是 0,手上也没攒着连续段,什么都不做,指针继续往左移。
这一位是 1,连续段又长了一格,cnt 变成 1。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
这一位是 1,连续段又长了一格,cnt 变成 2。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
这一位是 0,前面攒了 2 个连续的 1。一串两个以上的 1,与其一个个减,不如加 1 让它整体进位,只花 1 次操作。进位产生的 1 顶到当前这个 0 的位置上,成为新连续段的起点,所以 cnt 归 1,ans 变成 1。绿色从那一长串挪到了这一格。
这一位是 1,连续段又长了一格,cnt 变成 2。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
这一位是 1,连续段又长了一格,cnt 变成 3。绿色就是当前这串连续的 1,攒着等碰到 0 再一次性算账。
所有位都扫完了,手上还攒着 cnt = 3 个连续的 1。这一段在最高处,先加 1 进位把它合并成更高位的一个 1(1 次),这个单独的 1 再减掉(1 次),一共补 2 次,ans 变成 3。这就是最终答案。
边界想清:单个 1 记 1、n 为 0 记 0、隔开的两个 1 各减一次记 2。
面试重点:连续段短就减长就进位取更省、时间 O(log n) 空间 O(1)、三语言同一套贪心。
参考代码
from __future__ import annotationsfrom 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 ans复杂度
- 时间：O(log n)，只遍历 n 的二进制位,位数是 log n 量级;n 最大 10 的 5 次方,也就十七位左右。循环外再补一次结算是常数,整体随位数线性,不随 n 的数值大小成比例增长
- 空间：O(1)，全程只用 cnt 和 ans 两个整数变量,不开数组、不用递归栈,占用与 n 无关,是常数空间
易错点
面试追问把动画讲成自己的话
追问这个按位贪心为什么是对的?
追问时间和空间复杂度是多少?
追问三种语言写法有区别吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
找到最大开销的子字符串
LeetCode 2606 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题