题目描述
思路解析动画文字版
记牢这套口诀:连续 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题