教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载本文基于 InterviewGuide 仓库「精选力扣 300 题目 / 01-数组 / Easy」栏目中阿秀的 914. 卡牌分组 解题笔记展开沿作者第一版 → 第二版的迭代过程完整复盘这道题从计数 最小值整除判断走向最大公约数GCD判定的求解路径。读完本文你将掌握把数组合组问题转化为数论问题、手写辗转相除法求 GCD、以及用 GCD 提前终止这三项笔试面试中高频出现的基础能力。题目描述给定一副牌每张牌上都写着一个整数。此时你需要选定一个数字X使我们可以将整副牌按下述规则分成 1 组或更多组每组都有X张牌。组内所有的牌上都写着相同的整数。仅当你可选的X 2时返回true。示例 1输入[1,2,3,4,4,3,2,1] 输出true 解释可行的分组是 [1,1][2,2][3,3][4,4]示例 2输入[1,1,1,2,2,2,3,3] 输出false 解释没有满足要求的分组。示例 3输入[1] 输出false 解释没有满足要求的分组。示例 4输入[1,1] 输出true 解释可行的分组是 [1,1]示例 5输入[1,1,2,2,2,2] 输出true 解释可行的分组是 [1,1][2,2][2,2]提示1 deck.length 100000 deck[i] 10000作者在本仓库 数组 Easy 目录 中给这道题的评语是这也是道好题其价值在于表面是数组题本质是一道频率统计 最大公约数的数论判定题。先想清楚这道题到底在判什么把题目翻译成数学语言先统计每张牌按牌面数字的出现频次。设不同牌面的频次数列为f1, f2, ..., fk。若选定X要求每组X张且组内数字相同则X必须能整除每一个fi——即X是全部频次的公因数。因此存在X 2等价于全部频次的最大公约数GCD(f1, ..., fk) 2。值得注意的是笔记第一版的思考中写道要算所有数量的共同最小公倍数且最小公倍数要为 X。数学上更精确的说法应该是X 必须是所有频次的公因数而全部频次的最大公约数 ≥ 2才是不依赖枚举 X 的判定标准。用 GCD 一步判定比枚举候选 X 再逐个验证要简洁得多。用这个视角先快速过一遍五个示例可以建立对答案的直觉示例频次序列全部频次的 GCD结果12, 2, 2, 22true23, 3, 21false311false422true52, 42true与题目给出的期望输出完全一致。下面按笔记的原始顺序看作者的两版实现是怎么一步步逼近这个结论的。笔记第一版计数 能否被最小值整除作者的直觉是取出现次数最小的频次作为候选 X然后检查其余频次是否都能被它整除。完整代码笔记原文bool hasGroupsSizeX(vectorint deck) { unordered_mapint, int res; for (auto a : deck) { res[a] 1; } int minCut (*(res.begin())).second; for (auto it res.begin(); it ! res.end(); it) { minCut min(minCut, (*it).second); } if (minCut 2) return false; for (auto a : res) { if (a.second % minCut ! 0) return false;//这里不能简单的判断当前值是否可以整除最小值 } return true; }思路拆解unordered_mapint, int res完成频次统计这是数组数数类问题的标准起手式本仓库 697. 数组的度、1128. 等价多米诺骨牌对的数量 同样以哈希计数为核心先求出最小频次minCut若minCut 2直接返回false任何 X 2 都不可能整除小于 2 的频次再检查所有频次是否都能被minCut整除能则返回true。每个频次都能被最小值整除其实是充分条件成立时取X minCut一定可行。但它不是必要条件——最小值只是众多公因数中碰巧最小的那一个而不是全部频次的最大公因数。反例作者笔记中自己给出的当输入为[1,1,1,1,2,2,2,2,2,2]时频次数列为1:4, 2:6。此时X 2是可行的正确输出true但代码取最小值 4 后判断6 % 4 ! 0直接返回false答案错误。这也是作者将该节标题标为第一版没想完全还有其他情况的原因代码注释里也留了一句这里不能简单的判断当前值是否可以整除最小值。失败模式的泛化只要存在形如{6, 10}的频次组合最小值 6 不整除 10但 2 是可行的 X最小值整除判断就会误判。问题根源已经呼之欲出——我们需要的是全部频次的公共因数而不是恰好等于最小值的那个因数。笔记第二版引入欧几里得算法的 GCD 提前终止第二版把判断工具从整除最小值换成了求最大公约数即在运行过程中一旦发现最小值小于 2或者当前频次与最小值的最大公约数为 1 时就直接返回false。作者记录的提交性能为执行用时 16 ms在所有 cpp 提交中击败了 92.34% 的用户内存消耗 9.9 MB在所有 cpp 提交中击败了 73.24% 的用户。完整代码笔记原文int greatestCommonDivisor(int a, int b) { int c 0; if (a b) swap(a, b); while (true) { c a % b; if (c 0) return b; else { a b; b c; } } } bool hasGroupsSizeX(vectorint deck) { unordered_mapint, int res; for (auto a : deck) { res[a] 1; } int minCut (*(res.begin())).second, greatestCommonDivisoreNum 0; for (auto it res.begin(); it ! res.end(); it) { greatestCommonDivisor_ 0; greatestCommonDivisor_ greatestCommonDivisor(minCut, it-second); minCut min(minCut, (*it).second); cout leastCommonMultipleNum greatestCommonDivisor_ minCut minCut endl; if (minCut 2 || greatestCommonDivisor_ 1) return false; } return true; }注为忠实保留笔记原貌上面按原文排版时统一了变量名拼写原文中调试用的cout输出语句在实际提交时应删除。greatestCommonDivisor是标准的辗转相除法欧几里得算法先swap保证a b循环取余c a % b若余数为 0则当前的b就是最大公约数否则令a b, b c进入下一轮。以gcd(6, 10)为例10 % 6 4 → gcd(6, 4)6 % 4 2 → gcd(4, 2)4 % 2 0返回 2。由于每轮被除数严格减小算法必然在 O(log min(a,b)) 步内结束。主函数的逻辑是用第一个键值对的第二项初始化minCut遍历所有频次把当前累计最小值与当前频次求 GCD一旦 GCD 为 1说明至少存在一对频次互素全体频次不可能再有 ≥ 2 的公因数或最小值跌破 2就提前终止。相比第一版这版能正确处理{4, 6}、{6, 10}这类最小值不整除其他值、但存在更小公因数的场景gcd(4, 6) 2、gcd(6, 10) 2都不会被误杀。但仍有一处残留缺陷代码每一步求的是滚动最小值与当前频次的 GCD而这两个值本身都不是全体频次的代表辗转求 GCD 并没有在迭代中把公因数信息累积起来。构造频次数列{6, 10, 15}例如 1 出现 6 次、2 出现 10 次、3 出现 15 次全体频次的真实 GCD 是gcd(6, 10, 15) 1正确答案应为false但无论unordered_map按何种顺序遍历滚动最小值与当前频次的 GCD 序列都形如6 → 2 → 3或10 → 5 → 2任意顺序下每一对的 GCD 都 ≥ 2没有任何一步触发 1的提前返回函数会错误地返回true。根因在于全体 GCD 为 1并不意味着相邻任意两数就互素——公因数1这个信息是被逐对求 GCD 的方式丢弃了。要修正它只需要把 GCD 的累积对象从滚动最小值改成到目前为止所有频次的 GCD。收敛到最终形态所有频次的 GCD 2正确的判定只有一个字累积。维护一个滚动 GCDg对每个频次执行g gcd(g, fi)最后返回g 2。正确性论证两个方向若全体频次的 GCDG 2取X GX 2且X整除每个频次分组必然可行若存在合法的X 2则X整除每个频次于是X也整除G从而G X 2。两个方向互为充要判定精确无漏洞。最终形态的代码int gcd(int a, int b) { while (b ! 0) { int r a % b; a b; b r; } return a; } bool hasGroupsSizeX(vectorint deck) { unordered_mapint, int cnt; for (int card : deck) cnt[card]; int g 0; // gcd(0, x) x作为滚动 GCD 的初始值 for (auto p : cnt) g gcd(g, p.second); return g 2; }几个工程细节利用gcd(0, x) x的性质滚动 GCD 可以从 0 起步无需特判第一个元素若编译器支持 C17可以直接用numeric头文件中的std::gcd替换手写实现题目约束0 deck[i] 10000给出了值域上界从源码结构看可以把哈希表换成int cnt[10000] {0}的计数数组省去哈希开销空间复杂度依然是 O(k)k 为不同牌面数整体时间复杂度为 O(n k·log n)n 为deck.length最大 10000空间 O(k)。用最终解法重验一遍关键用例示例 1 频次{2,2,2,2}→ GCD 2 →true示例 2 频次{3,3,2}→ GCD 1 →false示例 4{2}→true示例 5{2,4}→true全部与期望一致第一版反例{4,6}→ GCD 2 →true修正成功第二版反例{6,10,15}→ GCD 1 →false修正成功。面试表达要点与延伸如果面试官问这道题建议按三句话组织答案转化按牌面统计频次X 必须整除每个频次即 X 是全体频次的公因数判定存在 X 2 等价于全体频次的最大公约数 2因此问题退化为求一组数的 GCD实现辗转相除法求 GCD滚动累积中途 GCD 变为 1 可提前返回 false。这道题的辨析点也很适合展开聊GCD 与 LCM 在这类问题中各扮演什么角色判定用 GCD若要问最小可用分组数是多少则答案是 LCM、哈希表与计数数组在值域已知时如何选择、以及逐对求 GCD与滚动累积求 GCD的差别——这正是笔记从第一版走到第二版、再走到最终形态时踩过的完整路径。同仓库中可对照练习的相关题目均位于数组 Easy 分组697. 数组的度同样以频率统计为核心的数数问题1128. 等价多米诺骨牌对的数量哈希计数的计数问题变体941. 有效的山脉数组单趟线性扫描判定的数组题可与本题的提前终止思想对照。更多按难度分组的题目索引见 数组目录 与 LeetCode 300 题使用指南本仓库另有一版数组 Easy 全部题解合辑其中也收录了卡牌分组的完整笔记便于串联复习。赞分享教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载相关推荐InterviewGuide 刷题笔记LeetCode 914 卡牌分组 —— 从最小公倍数误区到最大公约数最优解的完整解题思路InterviewGuide 刷题笔记LeetCode 914 卡牌分组 —— 从最小公倍数误区到最大公约数最优解的完整解题思路 本篇技术指南源自 I文档教程知识库ROCm Ubuntu 24.04 安装失败排查apt 源 Release 报错如何快速定位并修好ROCm Ubuntu 24.04 安装失败排查apt 源 Release 报错如何快速定位并修好 在 Ubuntu 24.04 上装 ROCm跑 apt开发工具高性能计算文档四数相加 IILeetCode 0454题解哈希表分组计数法详解四数相加 IILeetCode 0454题解哈希表分组计数法详解 本篇技术指南基于「算法通关手册」AlgoNote 仓库的题解文档 docs/soluti教程文档知识库上一篇JNA Union终极指南高效处理联合体数据结构的完整教程下一篇up/up日志聚合与分析ELK Stack集成实战创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考