题目描述
思路解析动画文字版
记牢:答案 = 所有数二进制里 1 的总个数(每个 1 要一次 +1)+ 最大数最高位的层数(每升一层一次共享的 ×2)。两块相加就是最少操作次数。
总览 · 目标数组与初始全 0 的 arr：先看清画面。上面这排格子是目标 nums = [4,2,5]。你手里的 arr 现在是 [0,0,0],要靠不停地 +1 和 ×2 把它拼成 nums。右边面板会一边拆二进制一边记两件事:用了多少次 +1,以及最高位爬到了第几层。我们先把每个数写成二进制来分析。
计划 · 数 1 的个数 + 找最高位层数：思路拆成两件事。第一件,把三个数全写成二进制,数一数总共有多少个 1,每个 1 都要花一次 +1。第二件,找出最大的数最高位落在第几层,从第 0 层往上每升一层要做一次全体 ×2,而这一步是所有数共享的。下面一个数一个数地拆。
拆 4 · 写成二进制 100：看第 0 个数 4。把它写成 3 位二进制是 100,右边表格记下这一行。接着从高位到低位扫一遍,凡是 1 的位都要记一次 +1,顺便留意它最高的那个 1 在第几层。
拆 4 · 第 2 位是 1：4 的第 2 位是 1,说明拼这个数时,这一层上有一个 1 要靠一次 +1 放上去,+1 的累计变成 1。第 2 层是目前最高的有 1 的层,把最高层记成 2。
拆 4 · 其余位是 0：4 的第 1 位、第 0 位都是 0,这些位上没有 1 要放,直接跳过,不增加 +1 的次数。4 这个数就拆完了,它一共贡献了 1 个 1。
拆 2 · 写成二进制 010：看第 1 个数 2。把它写成 3 位二进制是 010,右边表格记下这一行。接着从高位到低位扫一遍,凡是 1 的位都要记一次 +1,顺便留意它最高的那个 1 在第几层。
拆 2 · 第 1 位是 1：2 的第 1 位是 1,说明拼这个数时,这一层上有一个 1 要靠一次 +1 放上去,+1 的累计变成 2。第 1 层没有超过已有最高层 2,最高层仍记 2。
拆 2 · 其余位是 0：2 的第 2 位、第 0 位都是 0,这些位上没有 1 要放,直接跳过,不增加 +1 的次数。2 这个数就拆完了,它一共贡献了 1 个 1。
拆 5 · 写成二进制 101：看第 2 个数 5。把它写成 3 位二进制是 101,右边表格记下这一行。接着从高位到低位扫一遍,凡是 1 的位都要记一次 +1,顺便留意它最高的那个 1 在第几层。
拆 5 · 第 2 位是 1：5 的第 2 位是 1,说明拼这个数时,这一层上有一个 1 要靠一次 +1 放上去,+1 的累计变成 3。第 2 层跟当前最高层持平,最高层仍是 2。
拆 5 · 第 0 位是 1：5 的第 0 位是 1,说明拼这个数时,这一层上有一个 1 要靠一次 +1 放上去,+1 的累计变成 4。第 0 层没有超过已有最高层 2,最高层仍记 2。
拆 5 · 其余位是 0：5 的第 1 位都是 0,这些位上没有 1 要放,直接跳过,不增加 +1 的次数。5 这个数就拆完了,它一共贡献了 2 个 1。
结算 · +1 总次数 = 4：三个数都拆完了。4 有 1 个 1,2 有 1 个 1,5 有 2 个 1,加起来一共 4 个 1。每个 1 都要一次 +1,所以单独的 +1 操作总共要做 4 次。这是答案的第一块。
结算 · ×2 总次数 = 2：再看最高位。4 和 5 的最高位都落在第 2 层,这是所有数里最高的。要把某一层的 1 抬到第 2 层,得从第 0 层开始一层层往上乘,正好 2 次全体 ×2。这是答案的第二块。
结算 · 为什么 ×2 只数一遍：为什么 ×2 不用每个数各算一遍?因为一次 ×2 会把数组里所有数同时左移一位,是大家共享的一步,次数是全局只数一遍的。位数较低的数需要的 1,会在对应的那一层直接用一次 +1 补上,它并没有提前乘好、再一路跟着被抬高,所以不会被后面的 ×2 多抬。这样 ×2 的次数只由最高的那个数决定,取最高层就够了。
答案 · 4 + 2 = 6：两块加起来。4 次单独的 +1,加上 2 次共享的 ×2,最少操作次数就是 6。整道题没有真去一步步构造,只把每个数拆成二进制、数 1 加最高层就出答案。下面我们倒着减一遍来验算这个 6。
验算 · 从 nums 倒着减到全 0：换个方向验证。正着是从全 0 拼出 nums,倒着就是从 nums 一步步减到全 0。+1 的逆操作是给奇数减 1,×2 的逆操作是全体减半。我们反着走一遍,数一数减 1 用了几次、减半用了几次,应该和刚才的 4 加 2 完全对上。
第 1 轮 · 找奇数：当前数组是 [4,2,5]。先找奇数,因为奇数的个位是 1,这个 1 没法靠减半消掉,只能减 1。这一轮第 2 位是奇数,标红,准备逐个减 1。
第 1 轮 · 第 2 位减 1：给第 2 位减 1,数组变成 [4,2,4],减 1 的次数累计到 1。每一次减 1,对应正向时的一次 +1。
第 1 轮 · 整体减半：现在数组里全是偶数且还没归零,可以整体减半,变成 [2,1,2],减半次数累计到 1。每一次减半,对应正向时的一次全体 ×2,是所有数共享的一步。
第 2 轮 · 找奇数：当前数组是 [2,1,2]。先找奇数,因为奇数的个位是 1,这个 1 没法靠减半消掉,只能减 1。这一轮第 1 位是奇数,标红,准备逐个减 1。
第 2 轮 · 第 1 位减 1：给第 1 位减 1,数组变成 [2,0,2],减 1 的次数累计到 2。每一次减 1,对应正向时的一次 +1。
第 2 轮 · 整体减半：现在数组里全是偶数且还没归零,可以整体减半,变成 [1,0,1],减半次数累计到 2。每一次减半,对应正向时的一次全体 ×2,是所有数共享的一步。
第 3 轮 · 找奇数：当前数组是 [1,0,1]。先找奇数,因为奇数的个位是 1,这个 1 没法靠减半消掉,只能减 1。这一轮第 0 位、第 2 位是奇数,标红,准备逐个减 1。
第 3 轮 · 第 0 位减 1：给第 0 位减 1,数组变成 [0,0,1],减 1 的次数累计到 3。每一次减 1,对应正向时的一次 +1。
第 3 轮 · 第 2 位减 1：给第 2 位减 1,数组变成 [0,0,0],减 1 的次数累计到 4。每一次减 1,对应正向时的一次 +1。
验算完成 · 4 + 2 = 6：数组减到全 0,收工。数一数:减 1 一共做了 4 次,正好等于所有数二进制里 1 的个数;减半一共做了 2 次,正好等于最高位的层数。4 加 2 等于 6,和二进制法算出的 6 一模一样,验算通过。
边界:全 0 答案为 0;含 0 的数组里 0 不贡献 1、但 ×2 层数按最大值算([0,4] 得 3);全是 1 时最高位在第 0 层、不用 ×2([1,1] 得 2)。
面试重点:+1 管放 1 的个数、×2 管抬到第几层,两者互不影响所以可分别相加;每个 1 至少一次 +1、最高位至少要对应次数 ×2,下界上界对上即最少;全程不真构造大数,无溢出。
参考代码
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, nums: List[int]) -> int: return sum(v.bit_count() for v in nums) + max(0, max(nums).bit_length() - 1)复杂度
- 时间：O(n)，n 是数组长度。只从头到尾扫一遍,每个数做的是一次求 1 的个数、一次取最大值,都是字宽内的常数操作,所以总体是线性的 O(n)。本题 n 最大到 10 的 5 次方,线性扫描轻松通过。若按位宽更严格地算,是 O(n 乘以 log 最大值),但每个数不超过 10 的 9 次方、位宽固定在 30 位上下,实际就是常数,所以记 O(n) 即可
- 空间：O(1)，按峰值算。整个过程只用了答案计数器 ans 和记录最大值的 mx 两个变量,不随 n 增长,也不开任何额外数组,所以额外空间是常数 O(1)。三种语言都只是一遍遍历加几个标量变量
易错点
面试追问把动画讲成自己的话
追问为什么答案能拆成「1 的个数」加「最高位层数」这两块,不会互相影响?
追问不去真的构造 arr,怎么保证这个次数真的是最少的?
追问题目说每个数能到 10 的 9 次方,会不会有溢出风险?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
使绳子变成彩色的最短时间
LeetCode 1578 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题