CS-Notes LeetCode 数学专题题解：数论分解、进制转换、阶乘与多数投票等经典算法精讲

CS-Notes LeetCode 数学专题题解数论分解、进制转换、阶乘与多数投票等经典算法精讲【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes数学类题目是 LeetCode 与算法面试中绕不开的高频考点它们往往代码量不大但非常考验对质因数分解、整除性质、进制表示、溢出与边界条件等基础功底的掌握。本文以 CS-Notes 仓库 中「Leetcode 题解 - 数学」篇为主体将其中精选的十几道数学经典题数论、最大公约数、进制转换、阶乘、字符串加法、相遇问题、多数投票等逐一展开精讲并在原文档基础上结合仓库其他笔记剑指 Offer 题解 - 目录、Leetcode 题解 - 位运算、算法 - 排序给出源码级佐证与进阶指引。读完本文你将掌握数学题中最高频的几种「套路」及其代码实现并能直接迁移到同类面试题中。本文是 Leetcode 题解系列「算法思想」板块中的数学篇全仓库共精选约 200 道高频题数学专题强调以数论规律替代暴力枚举是刷题体系中性价比最高的板块之一。数论基础素数分解、整除与最大公约数素数分解每一个数都可以分解成素数的乘积例如 84 22* 31* 50* 71* 110* 130* 170* …素数分解算术基本定理是许多数论问题的逻辑起点一个数之所以能被另一个数整除、两个数的最大公约数GCD与最小公倍数LCM为什么可以表示成各质因子指数的最小值/最大值都源于这一条性质。整除令 x 2m0* 3m1* 5m2* 7m3* 11m4* …令 y 2n0* 3n1* 5n2* 7n3* 11n4* …如果 x 整除 y即y % x 0则对所有 i都有 mi ≤ ni。也就是说整除关系等价于「被除数每个质因子的指数都不小于除数」。最大公约数与最小公倍数结合上面的质因子表示可以直观得出两个经典结论x 与 y 的最大公约数gcd(x,y) 2min(m0,n0)* 3min(m1,n1)* 5min(m2,n2)* ...x 与 y 的最小公倍数lcm(x,y) 2max(m0,n0)* 3max(m1,n1)* 5max(m2,n2)* ...实际编码中并不会真正去做质因数分解而是借助下述三种经典算法。1. 生成素数序列埃拉托斯特尼筛法204. Count Primes (Easy)统计小于非负整数 n 的质数个数。埃拉托斯特尼筛法Sieve of Eratosthenes在每次找到一个素数时将能被该素数整除的数排除掉。原始朴素做法是对每个数做O(√n)的试除而筛法只遍历一次即可完成标记public int countPrimes(int n) { boolean[] notPrimes new boolean[n 1]; int count 0; for (int i 2; i n; i) { if (notPrimes[i]) { continue; } count; // 从 i * i 开始因为如果 k i那么 k * i 在之前就已经被去除过了 for (long j (long) (i) * i; j n; j i) { notPrimes[(int) j] true; } } return count; }关键细节拆解为何从i * i开始标记任何形如k * i其中 k i的合数都必然含有比 i 更小的质因子此前早已被更小的质数筛掉重复标记只会浪费操作。为何用long存i * i当 i 接近 n例如 i 约为 4.6 万以上时i * i可能超过int上界2147483647发生溢出变成负数导致notPrimes[j]数组越界或死循环。先强转为long再参与比较是防溢出的关键这也是该实现中最容易被忽略的一个坑。从整体实现看外层线性扫描 内层倍数标记算法复杂度约为O(n log log n)额外空间O(n)。2. 欧几里得算法求最大公约数辗转相除法Euclidean Algorithm是最经典、最高效的 GCD 求法基于性质gcd(a, b) gcd(b, a % b)int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); }最小公倍数为两数的乘积除以最大公约数int lcm(int a, int b) { return a * b / gcd(a, b); }注意lcm中a * b可能溢出工程上更稳妥的写法是先除后乘a / gcd(a, b) * b。3. 使用位操作和减法求解最大公约数出处《编程之美》2.7。当数据规模极大、对取模运算%的性能敏感时可以用减法与移位代替取模来求解 GCD。对于 a 和 b 的最大公约数 f(a, b)有如果 a 和 b 均为偶数f(a, b) 2*f(a/2, b/2)如果 a 是偶数 b 是奇数f(a, b) f(a/2, b)如果 b 是偶数 a 是奇数f(a, b) f(a, b/2)如果 a 和 b 均为奇数f(a, b) f(b, a-b)。乘 2 和除 2 都可以转换为移位操作因此整个算法可以只用位运算与减法完成规避了%的开销public int gcd(int a, int b) { if (a b) { return gcd(b, a); } if (b 0) { return a; } boolean isAEven isEven(a), isBEven isEven(b); if (isAEven isBEven) { return 2 * gcd(a 1, b 1); } else if (isAEven !isBEven) { return gcd(a 1, b); } else if (!isAEven isBEven) { return gcd(a, b 1); } else { return gcd(b, a - b); } }其中isEven可用(x 1) 0实现。需要指出这个版本在 a、b 相差悬殊时会递归较深通常面试中更推荐直接给出欧几里得写法位运算版可作为加分拓展仓库 Leetcode 题解 - 位运算 整理了更多与移位、补码相关的基础可配合复习。进制转换进制转换属于「模拟」类问题核心是用目标基数反复取余并逆序拼接结果。1. 十进制转 7 进制504. Base 7 (Easy)。手动模拟「不断除 7、余数拼接后反转」即可注意处理 0 与负数public String convertToBase7(int num) { if (num 0) { return 0; } StringBuilder sb new StringBuilder(); boolean isNegative num 0; if (isNegative) { num -num; } while (num 0) { sb.append(num % 7); num / 7; } String ret sb.reverse().toString(); return isNegative ? - ret : ret; }实际上 Java 标准库已经封装好了通用进制转换能力Integer.toString(int num, int radix)可以将一个整数转换为 radix 进制表示的字符串因此该题也可一行解决public String convertToBase7(int num) { return Integer.toString(num, 7); }2. 十进制转 16 进制补码形式405. Convert a Number to Hexadecimal (Easy)。题目要求负数以其补码形式输出例如Input: 26 Output: 1a Input: -1 Output: ffffffff负数要用它的补码形式也就是说不能像 7 进制那样先取绝对值。正确做法是每次取num 0b1111低 4 位然后执行无符号右移num 4public String toHex(int num) { char[] map {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f}; if (num 0) return 0; StringBuilder sb new StringBuilder(); while (num ! 0) { sb.append(map[num 0b1111]); num 4; // 因为考虑的是补码形式因此符号位就不能有特殊的意义需要使用无符号右移左边填 0 } return sb.reverse().toString(); }为什么必须用而不是算术右移在负数时会高位补 1导致死循环无符号右移高位补 0让负数的 32 位补码能逐 4 位地自然右移直到归零从而正确产出ffffffff这类结果。从仓库源码结构看负数的补码处理与 Leetcode 题解 - 位运算 中大量使用掩码与移位的技巧一脉相承可交叉复习。3. 十进制转 26 进制Excel 列名168. Excel Sheet Column Title (Easy)。规则如下1 - A 2 - B 3 - C ... 26 - Z 27 - AA 28 - AB普通进制转换是从 0 开始计数的而 Excel 列名从 1 开始计算因此需要对 n 先执行-1操作再进入转换逻辑public String convertToTitle(int n) { if (n 0) { return ; } n--; return convertToTitle(n / 26) (char) (n % 26 A); }递归写法非常精炼n % 26 A计算出当前位字符并转为charn / 26处理更高位递归天然完成了「逆序拼接」高位在前。反向题目「Excel 列名转数字」同样是模拟题思想完全对称。阶乘相关统计尾部 0 与二进制最低位 11. 统计阶乘尾部有多少个 0172. Factorial Trailing Zeroes (Easy)。尾部的 0 由因子 2 × 5 得来而 2 的数量明显多于 5 的数量因此只要统计 n! 的质因子分解里有多少个 5 即可。对于一个数 N它所包含 5 的个数为N/5 N/52 N/53 ...其中 N/5 表示不大于 N 的数中 5 的倍数贡献一个 5N/52表示不大于 N 的数中 52的倍数再贡献一个 5依次类推。代码可用递归表达public int trailingZeroes(int n) { return n 0 ? 0 : n / 5 trailingZeroes(n / 5); }这等价于循环写法int count 0; while (n 0) { count n / 5; n / 5; }。核心思想是「把计数 5 的个数转化为不断除以 5 累加」类似的分治计数思想在仓库 剑指 Offer 题解 - 目录 的「43. 从 1 到 n 整数中 1 出现的次数」等题目中也有体现。2. 扩展统计 N! 的二进制表示中最低位 1 的位置如果统计的是 N! 的二进制表示中最低位 1 的位置只要统计质因子中有多少个 2 即可该思路出自《编程之美》2.2。和上面统计 5 的个数同理2 的个数为 N/2 N/22 N/23 ...也就是N!中因子 2 的总数最低位 1 的位数 因子 2 的个数 1。这样「阶乘问题」就转化成了纯计数问题无需真正计算大数阶乘。字符串大数加法当两个数超出long可表示范围时只能以字符串形式模拟竖式加法。1. 二进制加法67. Add Binary (Easy)a 11 b 1 Return 100.实现思路从最低位字符串末尾逐位向前用carry同时充当「进位」与「当前位累加值」两个角色——遇到1就carry写入carry % 2作为当前位再carry / 2保留进位public String addBinary(String a, String b) { int i a.length() - 1, j b.length() - 1, carry 0; StringBuilder str new StringBuilder(); while (carry 1 || i 0 || j 0) { if (i 0 a.charAt(i--) 1) { carry; } if (j 0 b.charAt(j--) 1) { carry; } str.append(carry % 2); carry / 2; } return str.reverse().toString(); }循环条件carry 1 || i 0 || j 0保证即使两个串都扫描完若仍有进位也能再补一轮charAt(i--) 1巧妙地把「取值 指针前移」合并在一次判断里。2. 字符串加法415. Add Strings (Easy)。字符串的值为非负整数不能直接转成整数相加。与二进制加法结构一致只是基数从 2 变成 10并需要通过char - 0将字符还原为数字public String addStrings(String num1, String num2) { StringBuilder str new StringBuilder(); int carry 0, i num1.length() - 1, j num2.length() - 1; while (carry 1 || i 0 || j 0) { int x i 0 ? 0 : num1.charAt(i--) - 0; int y j 0 ? 0 : num2.charAt(j--) - 0; str.append((x y carry) % 10); carry (x y carry) / 10; } return str.reverse().toString(); }两个模板非常相似尾部对齐、逐位累加、统一在循环条件里兜底进位、最后整体反转。掌握了二进制与十进制两个版本后任意基数如 36 进制的大数加法都只是改一个数字的问题。相遇问题把数组元素变成全等值的最小移动次数462. Minimum Moves to Equal Array Elements II (Medium)Input: [1,2,3] Output: 2 Explanation: Only two moves are needed (remember each move increments or decrements one element): [1,2,3] [2,2,3] [2,2,2]题意每次可以对一个数组元素加一或者减一求使所有元素相等所需的最小改变次数。这是典型的相遇问题移动距离最小的方式是让所有元素都移动到中位数。理由如下设 m 为中位数。a 和 b 是 m 两边的两个元素且 b a。要使 a 和 b 相等它们总共移动的次数为 b - a这个值等于 (b - m) (m - a)也就是把这两个数移动到中位数的移动次数。设数组长度为 N则可以找到 N/2 对这样的 a、b 组合使它们都移动到 m 的位置。正是因为两两配对时中位数是总距离的全局最小点而不是平均数此题的最优解才对标中位数。解法 1先排序再对撞配对时间复杂度 O(NlogN)public int minMoves2(int[] nums) { Arrays.sort(nums); int move 0; int l 0, h nums.length - 1; while (l h) { move nums[h] - nums[l]; l; h--; } return move; }解法 2快速选择找中位数时间复杂度 O(N)借助快速排序的partition()切分可以在不完全排序的情况下找到第 k 小元素快速选择算法拿到中位数后统一累加绝对差public int minMoves2(int[] nums) { int move 0; int median findKthSmallest(nums, nums.length / 2); for (int num : nums) { move Math.abs(num - median); } return move; } private int findKthSmallest(int[] nums, int k) { int l 0, h nums.length - 1; while (l h) { int j partition(nums, l, h); if (j k) { break; } if (j k) { l j 1; } else { h j - 1; } } return nums[k]; } private int partition(int[] nums, int l, int h) { int i l, j h 1; while (true) { while (nums[i] nums[l] i h) ; while (nums[--j] nums[l] j l) ; if (i j) { break; } swap(nums, i, j); } swap(nums, l, j); return j; } private void swap(int[] nums, int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; }仓库佐证partition()切分法正是仓库 算法 - 排序 中「基于切分的快速选择算法」的同款实现在 剑指 Offer 题解 - 目录 的「40. 最小的 K 个数」中同样用快速选择拿到第 K 个元素来求解 Top-K说明这是贯穿整个题集的高频通用模板值得熟练掌握。多数投票问题找出现次数多于 n/2 的元素169. Majority Element (Easy)。给定大小为 n 的数组找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊n/2⌋ 的元素。思路 1排序后取中位。先对数组排序最中间那个数出现次数一定多于 n / 2public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length / 2]; }思路 2Boyer-Moore 多数投票算法时间复杂度 O(N)、额外空间 O(1)。该算法的直观理解如下使用 cnt 来统计一个元素出现的次数当遍历到的元素和统计元素相等时令 cnt不相等时令 cnt--。如果前面已经查找了 i 个元素且 cnt 0说明前 i 个元素中没有 majority或者虽然有 majority 但出现次数少于 i / 2——因为若其出现次数多于 i / 2cnt 一定不会归零。此时剩下的 n - i 个元素中majority 的数目依然多于 (n - i) / 2因此继续用同样的策略查找就能找出 majoritypublic int majorityElement(int[] nums) { int cnt 0, majority nums[0]; for (int num : nums) { majority (cnt 0) ? num : majority; cnt (majority num) ? cnt 1 : cnt - 1; } return majority; }代码巧妙地用三元表达式同时完成「cnt 归零时更换候选人」与「计数增减」。注意该写法成立的前提是题目保证 majority 一定存在若不保证存在则需要像仓库 剑指 Offer 题解 - 目录 的「39. 数组中出现次数超过一半的数字」那样在投票结束后再遍历一遍校验候选者的真实出现次数是否超过 n / 2否则返回 0。其它经典数学技巧1. 平方数判定367. Valid Perfect Square (Easy)Input: 16 Returns: True平方序列为 1, 4, 9, 16, ...其相邻间隔为 3, 5, 7, ...奇数列等差递增。利用「间隔为等差数列」这个特性可以从 1 开始构造平方数序列并逐项扣除无需使用浮点sqrtpublic boolean isPerfectSquare(int num) { int subNum 1; while (num 0) { num - subNum; subNum 2; } return num 0; }推导依据第 k 个奇数 2k-1 恰好是 k2与 (k-1)2之差所以不断累减奇数列就能判断 num 是否能被完整「减尽」。2. 3 的 n 次方326. Power of Three (Easy)。判断一个整数是否是 3 的幂次不使用循环与递归的巧解是取模法public boolean isPowerOfThree(int n) { return n 0 (1162261467 % n 0); }关键点在于常数1162261467它是 319也就是 32 位有符号 int 范围内最大的 3 的幂。若 n 是 3 的某次幂它一定能整除 319反过来若 n 含有 2、5 等其他质因子则必然除不尽3 的幂的因数只能是 3 的幂。约束n 0排除了 0 与负数因为取模结果对负数也可能为 0。3. 除自身以外数组的乘积238. Product of Array Except Self (Medium)For example, given [1,2,3,4], return [24,12,8,6].给定一个数组创建一个新数组新数组的每个元素为原始数组中除了该位置元素之外所有元素的乘积。要求时间复杂度为 O(N)并且不能使用除法。解法分两趟扫描分别累乘「左侧前缀积」与「右侧后缀积」两者相乘即为结果public int[] productExceptSelf(int[] nums) { int n nums.length; int[] products new int[n]; Arrays.fill(products, 1); int left 1; for (int i 1; i n; i) { left * nums[i - 1]; products[i] * left; } int right 1; for (int i n - 2; i 0; i--) { right * nums[i 1]; products[i] * right; } return products; }第一趟从左到右products[i]累积nums[0..i-1]的乘积即左侧所有元素之积第二趟从右到左再用右侧所有元素之积nums[i1..n-1]乘回products[i]两趟各 O(N)总时间复杂度 O(N)、空间 O(N)若忽略输出数组则为 O(1) 额外空间。同一道题的剑指 Offer 版本出现在仓库 剑指 Offer 题解 - 目录 的「66. 构建乘积数组」那里把两趟循环精简成for的累乘子句写法语义相同可对照学习。4. 找出数组中的乘积最大的三个数628. Maximum Product of Three Numbers (Easy)Input: [1,2,3,4] Output: 24如果只是取最大的三个数相乘会漏掉负数情况当数组含负数时两个绝对值很大的负数相乘会得到很大的正数。因此要同时维护最大的三个数与最小的两个数最终答案在max1*max2*max3与max1*min1*min2中取较大者public int maximumProduct(int[] nums) { int max1 Integer.MIN_VALUE, max2 Integer.MIN_VALUE, max3 Integer.MIN_VALUE, min1 Integer.MAX_VALUE, min2 Integer.MAX_VALUE; for (int n : nums) { if (n max1) { max3 max2; max2 max1; max1 n; } else if (n max2) { max3 max2; max2 n; } else if (n max3) { max3 n; } if (n min1) { min2 min1; min1 n; } else if (n min2) { min2 n; } } return Math.max(max1*max2*max3, max1*min1*min2); }实现上不做完整排序只用 5 个变量在单次 O(N) 遍历中维护 Top3 与 Bottom2用else if链完成变量「顺次顶替」与「滑动窗口/堆顶替换」的思路异曲同工。这里涉及负数参与比较的边界讨论可结合仓库 算法 - 排序 中对选择类问题的总结进一步理解。小结数学专题解题模式一览题型代表题目核心套路素数/数论204. Count Primes埃拉托斯特尼筛法注意i*i防溢出最大公约数GCD / LCM欧几里得%或位运算 减法lcm 防溢出进制转换504 / 405 / 168取余反转负数用补码 无符号右移1 基减一阶乘172数质因子 5 的个数N/5N/5²...大数加法67 / 415尾部对齐模拟竖式进位兜底最后反转相遇问题462全部元素移到中位数移动距离最小多数投票169Boyer-Moore 投票不保证存在时需二次校验其它技巧367 / 326 / 238 / 628等差间隔、最大 3 幂取模、前缀积×后缀积、Top3Bottom2数学专题的共同特点是「先推导规律再设计算法」代码量普遍不大但对正确性证明和边界条件的把握要求很高。建议按上表顺序逐题手写实现并对照 Leetcode 题解 - 目录 中算法思想板块的其他专题排序、位运算、二分查找 等交叉训练快速选择、前缀积、投票算法等通用模板在剑指 Offer 系列中还会反复出现掌握本文即掌握了这批高频数学题的骨架。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考