题目描述
思路解析
一句话答案:LeetCode 846 一手顺子:判断能否把 hand 全分成每组 groupSize 张的连续顺子。用计数表从最小牌起、每次以它为首连抽 groupSize 张,缺一张就分不成,时间 O(n log n)、空间 O(n)。
hand 这把牌能不能正好分成连续顺子
给一手牌 hand 和组大小 groupSize(题里也写成 W)。要判断能不能把牌全部分完,每组恰好 W 张、且这 W 张是连续递增的数,比如 2、3、4。全分完返回 true,剩下一张都算失败,返回 false。题面例子 hand=[3,2,1,8,2,3,4,6,7]、W=3,能拆成 [1,2,3]、[2,3,4]、[6,7,8],返回 true。
把牌硬凑成组,为什么试不过来
枚举所有分法是最容易想到的路:九张牌三张一组,谁和谁一组挨个搭,搭到某种分法全是连续顺子就算成。可这样的组合随牌数暴涨,十几张牌就有天文数字种拆法,一个个验根本跑不完。
最小的那张牌,队首只能是它
先盯住当前还没用过的牌里最小的那张。它前面再没有更小的牌,任何包含它的顺子都只能让它站开头——没有别的牌能接在它左边。所以这张最小牌只能当队首,没有第二种放法,接下来从它往上连抽 W 张连续牌。每一步都认准最小牌当队首、顺着账本逐张扣,扣定就不再回头——这就是贪心。抽完一组,再回到剩牌里最小那张,照同样的判断继续,那一大堆分法就整片省掉了。
从整除预判到用计数表连抽
落到代码,先做一票否决:牌的总数如果不能被 W 整除,无论怎么分都会剩牌,直接返回 false,省掉后面全部功夫。接着建一张计数表,也就是记下每个数字各有几张的小账本,免得反复翻找。
然后按数字从小到大扫这张账本。轮到值 s、它还剩 c 张(c>0)时,就从 s、s+1 一直到 s+W-1 逐个查账:每个值的存量都得不少于 c,因为 s 剩 c 张就意味着要同时开 c 个以 s 打头的顺子,后面每个值也得各扣掉 c 张;任一个值不够,就地返回 false。都够就把这几个值各减 c,继续往后。扫完一路没卡住,返回 true。
题面这把牌、W=3,三组是怎么落定的
先排好序:[1,2,2,3,3,4,6,7,8],九张,9 除以 3 整除,有机会分完。计数表里 2 和 3 各 2 张,1、4、6、7、8 各 1 张。
从最小值 1 起,它剩 1 张,抽 1、2、3 各一张,凑出 [1,2,3];此后 2、3 各剩 1 张,其余不变。轮到 2,还剩 1 张,抽 2、3、4,凑出 [2,3,4];剩 6、7、8 各 1 张。这时 3 和 4 都已扣到 0,扫到就跳过。到 6 剩 1 张,抽 6、7、8,凑出 [6,7,8],账本清空。三组连续顺子全部落定,返回 true。
开销落在哪、哪几步分错就全崩
整把牌里每个值只被抽走一次,抽牌这部分是线性的;把不同值按大小理顺那一步(排序,或建一张有序计数表)才顶到 O(n log n),复杂度的天花板就在这里。计数表最多存 n 个不同的值,空间 O(n)。
开头那句整除判断别省——总数不是 W 的整数倍,怎么分都剩牌,跳过它就会白跑一趟甚至误判成 true。起点也不能随手挑,必须是剩牌里最小的一张,换个起点就可能把本可成组的牌拆散、错报 false。还有个坑藏在重复值上:某个起点剩了好几张,只给它开一组,那些多的同值牌最后没有顺子接得住,一定凑不掉。
▶ 动画逐步走查(文字版)——想跟着上方动画一帧帧对照就展开
记住一句话:排序后,最左边没用过的牌必须当顺子开头,顺着它往上连 W 张。缺一张就崩。
先把手牌从小到大排好序。一共 12 张,能被 W=3 整除,所以有机会正好分完,开始一组一组抽顺子。
第 1 组:还没用过的牌里,最小的是下标 0 处的 1。没有更小的牌能带上它,所以它只能当这组顺子的开头。
这组第 1 张应当是 1。在未用牌里找到下标 0 处的 1,抽出来放进当前顺子(已凑 1/3 张)。
这组第 2 张应当是 2。在未用牌里找到下标 1 处的 2,抽出来放进当前顺子(已凑 2/3 张)。
这组第 3 张应当是 3。在未用牌里找到下标 3 处的 3,抽出来放进当前顺子(已凑 3/3 张)。
第 1 组凑齐了:1、2、3 正好是连续 3 张。这组牌打包收走(变灰),回头继续从剩下的最小牌开始下一组。
第 2 组:还没用过的牌里,最小的是下标 2 处的 2。没有更小的牌能带上它,所以它只能当这组顺子的开头。
这组第 1 张应当是 2。在未用牌里找到下标 2 处的 2,抽出来放进当前顺子(已凑 1/3 张)。
这组第 2 张应当是 3。在未用牌里找到下标 4 处的 3,抽出来放进当前顺子(已凑 2/3 张)。
这组第 3 张应当是 4。在未用牌里找到下标 6 处的 4,抽出来放进当前顺子(已凑 3/3 张)。
第 2 组凑齐了:2、3、4 正好是连续 3 张。这组牌打包收走(变灰),回头继续从剩下的最小牌开始下一组。
第 3 组:还没用过的牌里,最小的是下标 5 处的 3。没有更小的牌能带上它,所以它只能当这组顺子的开头。
这组第 1 张应当是 3。在未用牌里找到下标 5 处的 3,抽出来放进当前顺子(已凑 1/3 张)。
这组第 2 张应当是 4。在未用牌里找到下标 7 处的 4,抽出来放进当前顺子(已凑 2/3 张)。
这组第 3 张应当是 5。在未用牌里找到下标 8 处的 5,抽出来放进当前顺子(已凑 3/3 张)。
第 3 组凑齐了:3、4、5 正好是连续 3 张。这组牌打包收走(变灰),回头继续从剩下的最小牌开始下一组。
第 4 组:还没用过的牌里,最小的是下标 9 处的 5。没有更小的牌能带上它,所以它只能当这组顺子的开头。
这组第 1 张应当是 5。在未用牌里找到下标 9 处的 5,抽出来放进当前顺子(已凑 1/3 张)。
这组第 2 张应当是 6。在未用牌里找到下标 10 处的 6,抽出来放进当前顺子(已凑 2/3 张)。
这组第 3 张应当是 7。在未用牌里找到下标 11 处的 7,抽出来放进当前顺子(已凑 3/3 张)。
第 4 组凑齐了:5、6、7 正好是连续 3 张。这组牌打包收走(变灰),回头继续从剩下的最小牌开始下一组。
所有牌都被打包进了 4 个连续顺子,一张不剩。正好分完,返回 true。
三个高频追问:贪心为何对、重复值靠计数器、以及堆的等价写法。
参考代码
from collections import Counterdef isNStraightHand(hand, groupSize): if len(hand) % groupSize: # 张数不是整数倍 return False cnt = Counter(hand) # 每个值剩几张 for s in sorted(cnt): # 从最小的值开始当起点 c = cnt[s] if c > 0: # 还有 c 组要以 s 开头 for x in range(s, s + groupSize): if cnt[x] < c: # 接不上这么多 → 失败 return False cnt[x] -= c # 抽走 c 张 return True复杂度
- 时间:O(n log n),排序/建有序计数器是主开销;之后每张牌只被抽走一次
- 空间:O(n),计数器最多存 n 个不同的值
易错点
面试追问把动画讲成自己的话
追问为什么排序后从最小值贪心一定对?
追问hand 里有重复值怎么办?
追问能不能不排序、用最小堆?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
合并三元组以形成目标三元组
LeetCode 1899 · 中等 · 沿着 贪心 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题