十-二进制数的最少数目 图解题解
这道题到底在问什么
- 输入
- n = "32"
- 输出
- 3
- 输入
- n = "82734"
- 输出
- 8
- 输入
- 本节演示 n = "27340681"
- 输出
- 8
最优解：一步一步想明白
- 3记牢这套:答案 = n 里最大的那一位数字。逐位扫,拿当前数字去刷新「见过的最大数字」,扫完它就是答案。下面每帧都在套它。
- 4上面这排是 "27340681" 拆开的 8 位数字。开扫前,记最大数字的 curMax 先清成 0。我们要做的就是从最左第 0 位往右走,每看到一位,就拿它跟 curMax 比一比,谁大留谁。扫到头,curMax 就是答案。
- 5先看第 0 位,是数字 2。手里的 curMax 还是 0,拿 2 跟它比一下。
- 62 比 0 大,curMax 更新成 2,把这位标成绿色,它是眼下的「最大数字冠军」。这位处理完变蓝,接着往右。
- 7第 1 位是 7,明显比手里的 2 大。拿它跟 curMax 比。
- 87 把 2 顶下去,curMax 升到 7,绿色冠军位从第 0 位挪到第 1 位。记住这个 7,后面就看谁还能超过它。
- 9第 2 位是 3,看着不算小,可手里的 curMax 已经是 7 了,先比一比再说。
- 103 比 7 小,curMax 一动不动,还是 7,冠军位仍停在第 1 位的 7。这位看完直接变蓝。
- 11第 3 位是 4,比刚才的 3 大一点,但还得跟 curMax 的 7 较量。
- 124 没干过 7,curMax 照旧是 7。这一路你会发现,只要没碰到更大的数字,curMax 就稳稳不动。
- 13第 4 位是 0,这是最小的数字。标成红色提醒你:0 是绝不可能成为最大数字的,但流程一视同仁,照样拿它比一下。
- 140 当然比 7 小,curMax 纹丝不动。顺带说一句:这一位是 0,意味着所有加数在这一位都放 0 就行,它对答案没有任何压力。
- 15第 5 位是 6,离 7 只差一点点,是个很像样的挑战者。拿它跟 curMax 比。
- 166 比 7 小,就差这么一口气,curMax 还是 7。可见相等或更小都不刷新,必须严格更大才行。
- 17第 6 位是 8,这是全题最关键的一位。它比手里的 7 还大,盯紧了。
- 188 把 7 顶下去,curMax 升到 8,绿色冠军位跳到第 6 位。这个 8 就是后面再也无人超越的最大数字,也就是最终答案。
- 19最后一位是 1,很小。例行公事拿它跟 curMax 比一下。
- 201 远小于 8,curMax 稳稳停在 8。整串也就扫到头了。
- 218 位数字全看过一遍,整排都变蓝了。现在 curMax 里攥着的,就是整串里最大的那位数字。
- 22curMax 定格在 8,来自绿色标出的第 6 位那个 8。它就是把 n 拆成十-二进制数所需要的最少个数。前面虽有 7、有 6 紧追,但都没能超过它。
- 23为什么这个 8 真能凑成?准备 8 个十-二进制数,对 n 的每一位 d,就让其中 d 个数在这一位放 1、其余放 0,这一位的和正好是 d。每一位都这么配,8 个数加起来就是 n。位上最大的数字是 8,8 个数刚好够用,所以 8 就是最少个数,既不能再少,也用不着更多。
⚠️ 容易写错的地方
✗ 错：真的动手去把 n 拆成一个个十-二进制数,再数用了几个
✓ 对：根本不用拆,答案就是 n 里最大的那一位数字
每一位独立来看,凑出数字 d 需要 d 个加数在这位放 1;全局瓶颈是最大的那位,直接取最大数字即可,拆数纯属白费力气
✗ 错：把这些数字加起来或者求平均当答案
✓ 对：要的是逐位取最大值,不是求和也不是平均
加数个数由「最难凑的那一位」决定,也就是最大数字这一个瓶颈;其它位都能在同样多的加数里顺带凑齐,跟总和无关
✗ 错：比较时把「相等」也当成要刷新
✓ 对：只有严格更大才更新,相等不动
相等更不更新都不影响最终最大值,但养成「严格大于才刷新」的习惯,逻辑最干净,演示里第 5 位的 6 差一点、第 1 位之后的 7 才是真冠军
完整代码（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 minPartitions(self, n: str) -> int:
return int(max(n))C++
#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 minPartitions(string n) {
int ans = 0;
for (char& c : n) {
ans = max(ans, c - '0');
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int minPartitions(String n) {
int ans = 0;
for (int i = 0; i < n.length(); ++i) {
ans = Math.max(ans, n.charAt(i) - '0');
}
return ans;
}
}复杂度
时间
O(n)
n 为字符串长度。每一位只看一遍,做一次比较和取最大,整体是一遍线性扫描;扫到 9 时其实可以提前收手,但最坏仍是看完全串
空间
O(1)
自始至终只用一个整数记最大数字,峰值占用是常数,跟串多长无关;并没有真去构造那些十-二进制数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 十-二进制数的最少数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题为什么不用真的去构造那些十-二进制数?+
因为问的是「最少个数」这一个数字,而它只由最难凑的那一位决定。每一位非 0 即 1,凑出数字 d 至少要 d 个加数在这位放 1;全串最大的那位就是瓶颈,其它位都能在同样多的加数里顺带凑齐。所以扫一遍取最大数字就够,真去构造反而把简单题做复杂了。
Python 直接 max(n) 在字符串上比,会不会出问题?+
不会。n 只由数字字符组成,而数字字符 0 到 9 的编码顺序跟它们代表的数值顺序完全一致,所以在字符串上取 max 拿到的就是最大的那个数字字符,外面套个 int 转成整数即可。C++ 和 Java 没有这种字符串直接取 max 的便利写法,就老实用循环逐位减 "0" 再取最大。
这题的时间和空间复杂度是多少?+
时间 O(n),n 是串长,每位只看一遍做一次比较。空间 O(1),全程只有一个整数在记最大数字,不开数组也不构造任何加数。理论上扫到数字 9 就能提前返回,但最坏还是要看完整串。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 十-二进制数的最少数目 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。