LeetCode 914 卡牌分组：用最大公约数解决数组分组问题 这次我们来看一个 LeetCode 算法题卡牌分组。这是力扣LeetCode上的第 914 题难度为简单但涉及的核心数学思想——最大公约数GCD——在算法面试和日常编程中都非常实用。题目本身不复杂但如何高效、清晰地用 Python 实现并理解其背后的数学原理是本文要解决的重点。对于正在准备算法面试或想巩固 Python 与数学结合应用的同学这篇文章会直接带你拆解问题、分析思路、编写代码并讨论多种解法的优劣和边界情况。我们不会空谈概念而是从“能不能解”到“怎么解好”一步步给出可运行的代码和测试用例。1. 核心能力速览在深入代码之前我们先快速了解这个题目的关键信息和解决它的核心“工具”。能力项说明问题类型数组处理、数学最大公约数、哈希计数题目编号LeetCode 914难度简单核心算法最大公约数 (GCD)数据结构数组、哈希表或字典时间复杂度目标O(n log m)其中 n 为卡牌数量m 为不同数字的种类数空间复杂度目标O(n) 或 O(m)适合读者算法初学者、准备笔试面试、希望提升 Python 编码能力的开发者验证环境本地 Python 环境、LeetCode 在线判题系统2. 适用场景与使用边界这道题虽然标为“简单”但它训练的是将实际问题抽象为数学模型的能力。它适合谁算法面试准备者这是高频考题之一考察对哈希表和最大公约数的应用。Python 初学者通过此题可以练习collections.Counter、math.gcd等内置库的用法。希望理解“数学思维解决编程问题”的开发者如何从“分组”的要求联想到“最大公约数”。它能解决什么问题给定一个卡牌数组判断是否能将其分成若干组使得每组牌的数量X 1且每组内的牌数字相同。抽象来看是判断一组计数值每种牌的数量是否拥有一个大于1的公共公约数。它的边界与局限输入数组可能包含负数吗根据 LeetCode 描述卡牌数字在[1, 10000]范围内。数组长度可能为 0 或 1 吗题目保证数组长度大于等于 2。纯暴力枚举所有分组可能性会超时必须使用数学优化。本题解法高度特化但其核心思想使用 GCD 判断分组可能性可以迁移到其他类似“均分”或“周期分配”的问题中。3. 环境准备与前置条件要运行和测试本题的解法你只需要一个最基本的 Python 环境。操作系统Windows, macOS, Linux 均可。Python 版本Python 3.6 或以上。推荐使用 Python 3.8以确保math.gcd函数稳定可用对于更早版本可能需要自己实现 GCD 或使用fractions.gcd。开发工具任意代码编辑器或 IDE如 VS Code, PyCharm。或者直接在 LeetCode 官网的代码编辑器中编写。无需额外安装库核心解法仅依赖 Python 标准库collections,math。验证环境是否就绪 打开终端或命令行输入以下命令python --version确认输出为 Python 3.x。然后可以进入 Python 交互环境测试关键函数是否可用 import math math.gcd(12, 8) 4 from collections import Counter Counter([1,1,2,2,2,2]) Counter({2: 4, 1: 2})如果都能正确执行说明环境已准备好。4. 问题分析与算法思路题目描述LeetCode 914 给定一副牌每张牌上都写着一个整数。此时你需要选定一个数字X使得我们可以将整副牌按下述规则分成 1 组或更多组每组都有X张牌。组内所有的牌上都写着相同的整数。仅当你可选的X 2时返回true。示例 1输入deck [1,2,3,4,4,3,2,1]输出true解释可行的分组是[1,1][2,2][3,3][4,4]示例 2输入deck [1,1,1,2,2,2,3,3]输出false解释没有满足要求的分组。关键点分析统计频率首先我们需要知道每种数字的牌有多少张。例如[1,1,2,2,2,2]中数字1出现 2 次数字2出现 4 次。寻找公共因子分组要求每组牌数X相同且每组内牌的数字相同。这意味着对于每种数字它的出现次数频率必须能被X整除。因为我们要把同数字的牌分成若干组每组X张。转化为数学问题设各种数字的频率值为[f1, f2, f3, ...]。我们需要找到一个X 2使得X能整除每一个频率值fi。换句话说所有频率值的最大公约数GCD必须大于 1。结论计算所有频率值的最大公约数g。如果g 2则存在这样的XX可以是g的任何一个大于1的因子返回true否则返回false。思路步骤使用哈希表Python 的Counter统计每个数字的出现次数。获取所有频率值存入一个列表。计算这些频率值的最大公约数。判断最大公约数是否大于等于 2。5. Python 代码实现与逐行解读有了清晰的思路我们来实现代码。这里提供两种风格一种简洁直观一种逐步分解。5.1 简洁高效版推荐这是利用 Python 标准库最直接的写法。from collections import Counter import math from functools import reduce class Solution: def hasGroupsSizeX(self, deck: List[int]) - bool: # 步骤1统计每种牌的数量 count Counter(deck) # 步骤2获取所有频率值 frequencies list(count.values()) # 步骤3计算所有频率值的最大公约数 # 使用 reduce 将 gcd 函数依次应用到 frequencies 列表上 gcd_all reduce(math.gcd, frequencies) # 步骤4判断最大公约数是否 2 return gcd_all 2逐行解读from collections import Counter导入计数器用于快速统计列表元素频率。import math导入数学库使用math.gcd函数。from functools import reduce导入reduce函数用于对列表进行累积计算。count Counter(deck)一行代码完成频率统计。例如deck[1,1,2,2,2]则count为{1:2, 2:3}。frequencies list(count.values())提取所有的频率值得到列表如[2, 3]。gcd_all reduce(math.gcd, frequencies)这是核心。reduce的工作过程是先计算gcd(2, 3)得到 1如果还有第三个频率值再计算gcd(1, 第三个值)以此类推。最终得到所有频率值的最大公约数。return gcd_all 2根据结论返回结果。5.2 逐步分解版便于理解如果你对reduce或Counter不熟悉可以看这个更基础的版本。import math class Solution: def hasGroupsSizeX(self, deck: List[int]) - bool: # 步骤1手动统计频率 freq_map {} for card in deck: freq_map[card] freq_map.get(card, 0) 1 # 步骤2将频率值放入列表 freq_list list(freq_map.values()) # 步骤3计算最大公约数 # 先取第一个频率值作为初始的 gcd current_gcd freq_list[0] for freq in freq_list[1:]: # 从第二个开始遍历 current_gcd math.gcd(current_gcd, freq) # 如果中途发现 gcd 已经降到 1可以提前结束优化 if current_gcd 1: return False # 步骤4判断最终结果 return current_gcd 2逐行解读使用普通的字典freq_map手动统计频率逻辑更透明。计算 GCD 时用循环代替reduce并加入了提前终止的优化一旦在计算过程中发现当前公约数已经为 1那么最终结果不可能大于 1可以直接返回False节省计算。6. 功能测试与效果验证写好了代码我们如何验证它是否正确不能只依赖 LeetCode 的测试用例自己设计测试用例是理解问题和巩固代码的关键。6.1 设计测试用例一个好的测试集应包含以下情况明显为 True 的情况所有频率值有明显的公共大于1的因子。明显为 False 的情况频率值互质最大公约数为1。边界情况数组长度很小、频率值很大、数字种类很多。特殊数字频率值包含质数的情况。下面我们编写一个简单的测试函数def test_hasGroupsSizeX(): solution Solution() # 测试用例1示例1应该为 True deck1 [1,2,3,4,4,3,2,1] assert solution.hasGroupsSizeX(deck1) True, f测试失败: deck{deck1} # 测试用例2示例2应该为 False deck2 [1,1,1,2,2,2,3,3] assert solution.hasGroupsSizeX(deck2) False, f测试失败: deck{deck2} # 测试用例3所有牌数字相同频率为8可以分成每组2/4/8张True deck3 [5,5,5,5,5,5,5,5] assert solution.hasGroupsSizeX(deck3) True, f测试失败: deck{deck3} # 测试用例4频率为 [3, 3]最大公约数3True deck4 [0,0,0,1,1,1] assert solution.hasGroupsSizeX(deck4) True, f测试失败: deck{deck4} # 测试用例5频率为 [2, 3]最大公约数1False deck5 [1,1,2,2,2] assert solution.hasGroupsSizeX(deck5) False, f测试失败: deck{deck5} # 测试用例6频率为 [4, 6]最大公约数2True (可分成每组2张) deck6 [1,1,1,1,2,2,2,2,2,2] assert solution.hasGroupsSizeX(deck6) True, f测试失败: deck{deck6} # 测试用例7频率列表只有一个值 [5]最大公约数5True (可分成每组5张其实就是一组) deck7 [9,9,9,9,9] assert solution.hasGroupsSizeX(deck7) True, f测试失败: deck{deck7} # 测试用例8LeetCode 边界最小输入频率为 [2]最大公约数2True deck8 [7,7] assert solution.hasGroupsSizeX(deck8) True, f测试失败: deck{deck8} print(所有测试用例通过) # 运行测试 test_hasGroupsSizeX()6.2 在 LeetCode 上提交验证将Solution类代码复制到 LeetCode 题目 914 的代码编辑器中点击“执行代码”或“提交”按钮。系统会运行一系列隐藏的测试用例。如果所有用例通过你会看到“通过”的提示并附有运行时间和内存消耗的统计。性能观察点时间复杂度统计频率 O(n)计算 GCD O(k log min(f))其中 k 是不同数字的种类数f 是频率值。总体是 O(n k log M)M 是最大频率值。对于本题数据范围完全足够。空间复杂度主要是哈希表存储频率O(k)在最坏情况下所有牌数字都不同为 O(n)。7. 算法深入为什么是最大公约数这是本题最核心的思维跳跃点。我们再用一个例子来强化理解。假设牌组为[1,1,1,1,2,2,2,2,2,2]。数字1的频率4数字2的频率6我们想找一个分组大小X使得4 % X 04张‘1’牌能正好分成若干组每组X张6 % X 06张‘2’牌能正好分成若干组每组X张X必须同时是 4 和 6 的公约数。4 和 6 的公约数有1, 2。 题目要求X 2所以X可以是 2。 验证4 / 2 2组‘1’牌6 / 2 3组‘2’牌总共5组每组2张牌符合要求。如果所有频率值的最大公约数g 1那么它们唯一的公约数就是1找不到满足X2的X直接返回False。 如果g 2那么g本身以及它的任何大于1的因子都可以作为X因此返回True。计算多个数的最大公约数 两个数的最大公约数gcd(a, b)可以用辗转相除法欧几里得算法快速计算。Python 的math.gcd就实现了这个算法。 对于多个数[a, b, c, d]它们的最大公约数可以通过连续计算得到gcd(gcd(gcd(a, b), c), d)。这正是reduce(math.gcd, list)所做的事情。8. 常见问题与排查方法在实现和调试过程中你可能会遇到以下问题问题现象可能原因排查方式解决方案代码在本地测试通过但 LeetCode 提交报错NameError: name ‘List‘ is not defined未导入typing模块中的List类型提示。检查代码顶部是否有from typing import List。在类定义前添加from typing import List。对于频率列表[1]只有一种牌且只有一张的情况返回了True逻辑错误。一张牌无法分组X2。但频率列表[1]的最大公约数是1应返回False。检查边界条件。题目保证输入数组长度 2所以频率列表至少有一个值且该值 2不[1,2]的频率是[1,1]公约数1。我们的算法gcd_all 2已经正确处理了这种情况。[1]的 gcd 是1返回 False。计算gcd时如果频率列表只有一个值[n]结果是什么gcd(n)在数学上定义为n本身。reduce(math.gcd, [n])返回n。测试math.gcd(8)会报错因为它需要两个参数。reduce对单元素列表会直接返回该元素。所以对于[n]gcd_all n。如果n2返回 True。这符合逻辑一种牌n张可以分成每组 X 张X 是 n 的大于1的因子。时间复杂度太高大数据超时可能使用了暴力枚举所有可能的 X从2到 min(freq)的方法。检查算法是否基于最大公约数。必须使用 GCD 方法其效率远高于暴力枚举。reduce函数不熟悉导致理解困难。functools.reduce是函数式编程概念。使用循环版本替代reduce逻辑更清晰。采用5.2 逐步分解版的代码它用显式循环计算 GCD。输入中包含 0 或负数题目明确卡牌数字在[1, 10000]但代码应具备一定健壮性。我们的统计逻辑Counter或字典不关心数字大小只关心计数。算法只依赖于频率值与数字本身无关。算法本身对数字正负不敏感但需注意题目约束。9. 最佳实践与扩展思考9.1 编码最佳实践善用标准库collections.Counter和math.gcd是 Python 解决此类问题的利器代码简洁高效。注意类型提示在 LeetCode 等现代 Python 环境中为函数添加类型提示如deck: List[int]-bool是良好的习惯虽然不影响运行但提高了代码可读性。考虑边界即使题目有约束思考极端情况如所有牌数字都不同、只有一种牌、频率值非常大有助于写出健壮的代码。提前终止优化在计算多个数的 GCD 时一旦中间结果变为 1就可以立即返回False这是一个有效的优化。9.2 算法扩展与变种理解了“卡牌分组”的核心是“判断一组正整数是否存在大于1的公约数”你可以尝试解决类似问题水桶分水问题给定几个水桶的容量判断能否量出任意整数体积的水本质是判断容量值的最大公约数是否为1。音乐节拍分组给定一组音符的时长判断能否将它们分组构成均匀的节拍。字符串的重复子串判断一个字符串是否可以由它的某个子串重复多次构成LeetCode 459。其核心思想与本题有相似之处都涉及“周期”或“分组”的判定。9.3 在面试中如何阐述如果面试中被问到这道题可以按以下步骤阐述理解题意复述问题确认分组规则。举例分析用一个小例子如[1,1,2,2,2]说明分组失败的根源在于频率 2 和 3 互质。提出核心洞察将问题转化为“寻找所有频率值的公共大于1的因子”进而等价于“判断所有频率值的最大公约数是否大于1”。给出算法步骤 a. 统计频率。 b. 计算频率列表的最大公约数。 c. 比较结果与2。分析复杂度时间 O(n k log M)空间 O(k)。编写代码写出清晰代码并提及可以使用Counter和math.gcd。测试用几个典型用例True/False/边界验证代码。10. 总结LeetCode 914 “卡牌分组”是一个经典的将实际问题转化为数学模型的题目。它的解决方案不复杂但体现了算法思维中“寻找问题本质”的关键一步——从分组要求联想到数的整除性再归结到计算最大公约数。最值得掌握的点问题转化能力将“能否分组”转化为“频率值是否有大于1的公约数”。Python 工具链熟练使用collections.Counter进行计数使用math.gcd结合functools.reduce计算多个数的最大公约数。边界处理理解频率列表长度为1的情况以及 GCD 为1时的快速判断。最先应该验证的功能自己编写测试用例覆盖频率值互质、有公因子、仅一种牌、最小输入等情况确保逻辑正确。最容易踩的坑忘记导入必要的模块typing.List,functools.reduce。使用暴力枚举法导致超时。对单元素频率列表的 GCD 计算理解有误。这道题的价值远不止于通过一道 LeetCode 简单题。它训练的是在面对“分组”、“分配”、“周期”类问题时迅速联想到数论中的“公约数”这一核心工具的能力。掌握这种思维在解决其他更复杂的问题时你将拥有更强大的分析武器。