★ FEATURED ARTICLE 给你一副牌[1,2,3,4,4,3,2,1]问能否按X ≥ 2张一组分组且每组内数字相同。第一反应可能是搜索、回溯、枚举 X。但正解只有gcd(所有数字的计数)2为什么因为“能分组”这件事本质上是在问“这些计数有没有大于1的公共因子”。这就是数学类题目的典型形态代码只有两三行难点全在“看出它是 gcd”。今天的三道题都是这样——LC.914、LC.365、LC.1071每一道的解法代码都不超过十行但如果没认出背后的模型你可能会写出BFS水壶问题的经典错解或者一大段字符串处理。本周的立意正在于此先用数学消灭问题再写代码。 题目速览30秒读懂题目1卡牌分组LC.914给定一副牌选X ≥ 2使所有牌能分成若干组每组 X 张且数字相同。示例[1,2,3,4,4,3,2,1]→trueX2[1,1,1,2,2,2,3,3]→false题目2水壶问题LC.365两个容量为x、y升的水壶无限水。能否得到恰好z升示例x3, y5, z4→truex2, y6, z5→false题目3字符串的最大公因子LC.1071返回最长的同时能除尽str1和str2的字符串。示例ABCABCABC→ABCLEETCODE→ 核心思路欧几里得算法辗转相除gcd(a, b) gcd(b, a mod b) 直到b 0此时a即为最大公约数一行证明设d是a和b的任意公约数则d | a且d | b于是d | (a - ⌊a/b⌋·b) a mod b。反之若d | b且d | (a mod b)则d | a。两边的公约数集合完全相同所以最大公约数也相同。复杂度为什么是 O(log)每两步余数至少减半若a mod b b/2则下一步b mod (a mod b) b/2所以余数序列按指数衰减。最坏输入是相邻的斐波那契数——这正是“每步减得最慢”的情形。defgcd(a,b):whileb:a,bb,a%breturnaLC.914建模成“公共因子”设数字v出现了cᵥ次。要按X张一组分组就必须让每种数字的计数都能被X整除——否则某一组里会混入不同数字。于是问题变成存在X ≥ 2使得X | c₁且X | c₂且 … ⟺gcd(c₁, c₂, ...) ≥ 2注意是所有计数的总gcd不是成对gcd。好消息是gcd满足结合律用reduce累积即可且gcd(0, x) x让初始值0可以安全使用。LC.365建模成裴蜀定理这是三题里最需要洞察力的一道。每次操作装满、倒空、互倒之后两个水壶里的水量变化都可以表示为x和y的整数线性组合。所以能得到z升 ⟺ 存在整数a, b使得a·x b·y z而裴蜀定理给出方程a·x b·y z有整数解当且仅当gcd(x, y)整除z。再加上物理约束z ≤ x y两者合起来才是充要条件z 0 → true什么都不做 z x y → false装不下 z % gcd(x, y) 0 → true⚠️只写gcd条件而漏掉z ≤ x y是本题第一大错误——很多人只证了必要性就收手。裴蜀定理的直观解释所有能凑出的水量恰好是gcd(x,y)的所有倍数。以x3, y5为例gcd 1理论上能凑出任意整数升——比如4升装满5 → 倒进35剩2→ 倒空3 → 把2倒进3 → 装满5 → 倒满3需15剩4得到4升 ✓。对应的裴蜀等式是4 5×2 3×(-2)即a 2, b -2——系数允许为负物理上对应“倒掉水”。LC.1071拼接判定两个字符串存在公因子串当且仅当str1 str2 str2 str1。这个结论需要证明不能凭感觉必要性若str1 T 重复m次、str2 T重复n次则str1 str2与str2 str1都是T重复mn次必然相等。充分性若str1 str2 str2 str1则两个字符串循环同构可以证明它们都由同一个长度为gcd(len1, len2)的前缀重复构成。判定成立后答案长度就是gcd(len1, len2)直接取前缀即可。⚠️必须先做拼接校验。直接返回str1[:gcd(len1,len2)]是错的——反例str1 ABCABD、str2 ABC长度gcd是3但拼接不等答案应是而非ABC。️ 图解算法手把手走一遍LC.365 的实际操作步骤x3, y5目标4升步骤操作3升壶5升壶说明0初始00两壶皆空1装满5升壶0525 → 3倒满325升壶剩23倒空3升壶0245 → 3倒2进去205装满5升壶2565 → 3倒满需1升34得到4升✓把它翻译成裴蜀等式4 5 5 - 3 - 3 2×5 (-2)×3即a 2, b -2✓。而gcd(3,5) 11 | 4成立且4 ≤ 35 8两个条件都满足。反例核对x2, y6, z5。gcd(2,6) 2而2 ∤ 5所以false ✓——无论怎么倒能凑出的水量只能是0, 2, 4, 6, 82的倍数永远得不到5。LC.914 的三组数据deck各数字计数总gcd≥ 2答案[1,2,3,4,4,3,2,1]1→2, 2→2, 3→2, 4→22✅true[1,1,1,2,2,2,3,3]1→3, 2→3, 3→21❌false[1,1,2,2,2,2]1→2, 2→42✅true第二组为什么不行计数的gcd是1意味着找不到任何X ≥ 2能同时整除3、3、2。LC.1071 的拼接判定str1str2str1str2str2str1相等答案ABCABCABCABCABCABCABCABCABC✅ABC长度gcd3ABABABABABABABABABABABABABABAB✅AB长度gcd2LEETCODELEETCODECODELEET❌ 代码实现Python JavaPython版classSolution:# ---------- gcd欧几里得----------def_gcd(self,a:int,b:int)-int:whileb:a,bb,a%b# 每两步余数至少减半 → O(log min(a,b))returna# ---------- LC.914 卡牌分组 ----------defhasGroupsSizeX(self,deck:list[int])-bool:fromcollectionsimportCounteriflen(deck)2:returnFalseg0forcntinCounter(deck).values():gself._gcd(g,cnt)# 累积所有计数的总gcd不是成对returng2# ---------- LC.365 水壶问题 ----------defcanMeasureWater(self,x:int,y:int,z:int)-bool:ifz0:returnTrueifzxy:# 容量约束单靠gcd条件会漏判returnFalsereturnz%self._gcd(x,y)0# 裴蜀定理# ---------- LC.1071 字符串的最大公因子 ----------defgcdOfStrings(self,str1:str,str2:str)-str:# 拼接校验不能省长度gcd成立不代表真的存在公因子串ifstr1str2!str2str1:returnreturnstr1[:self._gcd(len(str1),len(str2))]Java版classSolution{privateintgcd(inta,intb){while(b!0){intta%b;ab;bt;}returna;}publicbooleanhasGroupsSizeX(int[]deck){if(deck.length2)returnfalse;int[]cntnewint[10000];for(intv:deck)cnt[v];intg0;for(intc:cnt){if(c0)ggcd(g,c);// gcd(0, x) x天然正确}returng2;}publicbooleancanMeasureWater(intx,inty,intz){if(z0)returntrue;if(zxy)returnfalse;// 漏掉这行会误判returnz%gcd(x,y)0;}publicStringgcdOfStrings(Stringstr1,Stringstr2){if(!(str1str2).equals(str2str1)){return;}returnstr1.substring(0,gcd(str1.length(),str2.length()));}}⚠️防坑提醒必看LC.365 漏掉z x y裴蜀定理只保证“存在整数解”但物理上两壶总容量只有x y。例如x1, y1, z3gcd1整除3但装不下必须返回false。LC.914 用成对gcd必须对所有计数做累积gcdg gcd(g, cnt)。LC.1071 不做拼接校验反例ABCABD/ABC长度gcd是3但拼接不等答案是。⏱️ 复杂度分析面试必问题目时间空间说明gcdO(log min(a,b))O(1)每两步余数至少减半LC.914O(n k logC)O(k)n 计数、k 种数字、C最大计数LC.365O(log min(x,y))O(1)只需一次 gcdLC.1071O(n m)O(n m)字符串拼接与比较对比一下“不建模”的代价题目建模后不建模的做法差距LC.914O(n)枚举X从2到 n → O(n²)从平方降到线性LC.365O(log)BFS搜索所有状态→ 状态数 O(x·y)从指数级降到对数级LC.1071O(nm)枚举所有可能的因子串长度 → O(n²)从平方降到线性LC.365 是最极端的例子网上大量题解用BFS把所有(水量1, 水量2)当作状态做搜索代码几十行、状态数O(x·y)而裴蜀定理的解法只需两行判断。认出模型比写出搜索重要得多。 举一反三6道高频变体题题号题目与本题的关系LC.914卡牌分组计数gcdLC.365水壶问题裴蜀定理最经典的建模题LC.1071字符串的最大公因子拼接判定 长度gcdLC.858镜面反射gcd/lcm建模LC.1979找出数组的最大公约数gcd的直接应用LC.1001网格照明lcm建模 面试追问模拟提前准备惊艳全场Q1欧几里得为什么是O(log)每两步余数至少减半设r₁ a mod b。若r₁ ≤ b/2一步就减半若r₁ b/2则下一步b mod r₁ b - r₁ b/2。所以余数每两步至少减半步数O(log min(a,b))。最坏输入是相邻斐波那契数——每步商都是1减得最慢。Q2裴蜀定理的“整数解”允许负数物理上是什么意思对应“倒掉水”。LC.365里4 2×5 (-2)×3b -2就是“倒掉了2个3升壶的水”。倒空操作让负系数变得可行。如果只允许“加水不允许倒水”模型就不成立了。Q3lcm(a,b) a / gcd(a,b) * b为什么要先除后乘防溢出。a * b可能远超int范围而a / gcd * b的中间结果最大是lcm本身。顺序不能颠倒。Q4模逆元怎么求若a × x ≡ 1 (mod m)则x是a的逆元等价于求a·x m·y 1的整数解——正是裴蜀定理且要求gcd(a, m) 1否则无解。两条路① 模为质数时用费马小定理a^(m-2)快速幂② 通用做法用扩展欧几里得算法——在辗转相除的同时回代求出系数x, y。 实战小技巧刷题党必备口诀辗转相除求gcd裴蜀定理判可解z ≤ xy不能漏拼接校验不能省。模板gcd(a,b)三行z % gcd(x,y) 0判裴蜀str1str2 str2str1判字符串。防坑LC.365漏容量判断会误判LC.914用成对gcd会错LC.1071不做拼接校验会错。 实际应用场景不止是刷题分数运算约分就是分子分母同除 gcd周期性对齐两个周期分别为a、b的任务重合周期是lcm(a,b)RSA与模运算扩展欧几里得求私钥、求模逆元图像缩放 / 网格对齐lcm与gcd决定最小可平铺单元 今日思考题评论区见LC.365水壶问题网上大量题解用 BFS。你觉得面试时应该直接写裴蜀定理两行还是先说BFS思路再升级到数学解提示先展示“我能做出来”再展示“我能做得更好”通常是更稳的表达顺序。欢迎评论区聊聊你的看法
阅读完成 · 觉得有帮助？
