1. 赛况速览与个人复盘视角又一场LeetCode周赛结束了这次是第326场日期是2023年1月1日。新年第一赛题目难度和风格都挺有意思既有考验基础数据结构熟练度的送分题也有需要一点巧思的中等题还有一道能拉开差距的、对思维缜密度要求比较高的题目。我习惯在赛后立刻复盘把解题思路、踩过的坑以及代码实现上的优化点都记录下来这比单纯看题解要有效得多。今天这篇复盘我就从一个普通参赛者的视角分享一下这四道题的解题过程、关键思路以及一些个人在实战中的体会。无论你是想了解这场比赛的概况还是想学习如何更高效地应对这类算法竞赛希望这篇内容都能给你带来一些直接的参考价值。2. 第一题统计能整除数字的位数这道题是典型的签到题考察的是对整数逐位处理的基本功。题目要求给定一个整数num返回num中能被其自身每一位上的数字整除的位数。换句话说我们需要取出num的每一位数字然后判断num是否能被这个数字整除注意题目明确说明数字0不能作为除数因此遇到某一位是0时直接跳过不计入结果。2.1 核心思路与实现细节这道题的思路非常直接保存原始值因为我们需要用原始的num去对每一位数字取模而在循环中我们可能会修改num的值比如通过除以10来取位所以必须先保存一份原始值original_num。循环取位使用while循环每次通过num % 10获取当前最低位的数字digit然后通过num // 10去掉最低位直到num变为 0。判断与计数对于每一位digit首先判断是否为 0。如果为 0根据题意original_num % 0会导致运行时错误且 0 不能整除任何数所以直接跳过。如果digit不为 0则判断original_num % digit 0是否成立。如果成立则结果计数器加一。返回结果循环结束后返回计数器的值。这里有一个非常容易疏忽的坑点直接在循环中修改num并用于取模判断。比如下面这段错误代码def countDigits(num: int) - int: count 0 while num 0: digit num % 10 if digit ! 0 and num % digit 0: # 错误这里的num已经被修改了 count 1 num // 10 return count当num是 1248 时第一次循环digit8,num1248判断1248%80正确。但第二次循环时num已经变成了 124此时digit4判断的是124%40这依然是正确的巧合。但如果num是 121第一次循环后num变成 12第二次循环判断12%20而实际上应该判断121%2!0这就出错了。所以务必保存原始值。正确的实现如下def countDigits(num: int) - int: original_num num count 0 while num 0: digit num % 10 if digit ! 0 and original_num % digit 0: count 1 num // 10 return count时间复杂度O(log₁₀(num))即数字的位数。空间复杂度O(1)。2.2 实战技巧与变体思考这道题虽然简单但可以引申出一些有用的编程习惯和思考。防御性编程处理数字和除法时永远要考虑除数为 0 的情况。即使题目描述可能隐含了这一点在代码中显式判断也能让逻辑更清晰、更健壮。字符串转换法另一种常见的解法是将整数转换为字符串然后遍历每个字符再转回整数进行判断。例如for digit_char in str(num): digit int(digit_char); ...。这种方法代码更简洁但性能略低于数学方法因为涉及字符串转换和创建。在竞赛中对于这种数据范围很小的题目两种方法都可以但知道数学方法更体现基本功。扩展思考如果题目改为“统计数字中能整除该位数字的位数”即digit % original_num 0或者统计的是“各位数字之和”等核心的取位和判断框架是不变的只是判断条件不同。这提醒我们要抽象出问题的通用部分。3. 第二题数组乘积中的不同质因数数目这道题开始需要一些数学知识。题目给出一个正整数数组nums要求返回数组所有元素乘积中不同质因数的数目。例如nums [2,4,3,7]乘积是2*4*3*7168。168的质因数分解是2^3 * 3 * 7其中不同的质因数是 {2, 3, 7}所以答案是 3。3.1 问题转化与高效解法最直接的想法是先算出所有数的乘积然后对这个乘积进行质因数分解最后统计不同的质因数。但这样做有两个问题乘积可能非常大数组长度和元素值都可能很大直接相乘会导致整数溢出即使在Python中不会溢出但大数运算效率低且分解大质因数非常困难。分解大数质因数很耗时这是一个经典的难题。因此我们必须转换思路。关键洞察整个数组乘积的质因数必然来自于每个数组元素的质因数。反之每个数组元素的质因数也必然是最终乘积的质因数。所以我们不需要计算乘积只需要分别找出每个数组元素的所有质因数然后求这些质因数的并集即可。那么如何高效地求一个数x的所有质因数呢这里用到经典的试除法。从i 2开始循环到sqrt(x)。如果x % i 0说明i是x的一个因数。此时i一定是质数吗不一定但我们可以通过循环将x中的所有i因子除尽while x % i 0: x // i。这样操作后后续的i就不会是合数因子了因为合数因子已经被它的质因数提前分解掉了。例如x12i2时12%20我们一直除到x3。下一个i33%30。i4时x已经是3不会进入判断。所以我们收集到的i就是质因数。循环结束后如果x 1那么剩下的x本身也是一个质因数例如x13循环i从2到3都没有整除最后x13113就是质因数。实现时我们用一个集合set来存储所有出现过的质因数避免重复。def distinctPrimeFactors(nums: List[int]) - int: prime_factors set() def get_prime_factors(x): i 2 # 只需要试除到 sqrt(x) while i * i x: if x % i 0: prime_factors.add(i) # 除尽所有i因子 while x % i 0: x // i i 1 # 处理剩余的大于sqrt(x)的质因数 if x 1: prime_factors.add(x) for num in nums: get_prime_factors(num) return len(prime_factors)时间复杂度O(N * sqrt(M))其中 N 是数组长度M 是数组中最大的数。对于每个数我们最多试除到其平方根。空间复杂度O(P)P 是所有不同质因数的个数这个集合通常不会很大。3.2 优化与边界情况处理试除法的优化在get_prime_factors函数中i每次加1。一个常见的优化是当i2处理完后i可以从3开始每次加2只检查奇数因为除了2以外的偶数都不是质数。可以进一步优化为i2, 3后每次加6检查i和i2即6k±1的形式但这对于竞赛环境通常不是必需的。去重时机我们是在处理每个数字的过程中直接向全局集合prime_factors中添加质因数。也可以先为每个数字生成一个质因数列表最后再合并去重但这样空间开销稍大。大数处理这个算法能够有效处理较大的数字因为分解是逐个数字独立进行的避免了计算巨大乘积。这是解决此类问题的标准且安全的方法。4. 第三题将字符串分割成值不超过 K 的子字符串这道题是一个不错的字符串分割问题带有贪心或动态规划的色彩。题目给定一个字符串s由数字组成和一个整数k。我们需要将s分割成若干连续子串使得每个子串表示的整数值小于等于k同时要求子串不能有前导零除非这个子串就是单个字符‘0’。要求返回满足条件的最少分割次数。如果无法分割则返回 -1。示例s “165462”, k 60。我们可以分割成“16” | “54” | “6” | “2”。子串对应的数字分别是16, 54, 6, 2都 60且没有前导零。分割了3次产生了4个子串。更少的分割方式可能不存在。4.1 动态规划思路解析求“最少分割次数”这是一个最优化问题通常可以用动态规划DP来解决。定义dp[i]表示字符串前i个字符即s[0:i]分割成合法子串的最少分割次数。我们最终要求的是dp[n]其中n是字符串长度。状态转移方程 为了计算dp[i]我们需要考虑最后一个子串可能是什么。假设最后一个子串是s[j:i]即从索引j到i-1那么前j个字符的分割方案数就是dp[j]。因此我们需要检查所有可能的j0 j i使得子串s[j:i]是合法的无非前导零且值 k然后取所有合法情况下的最小值dp[i] min(dp[j] 1)其中s[j:i]合法。初始化dp[0] -1。这是一个技巧性的初始化。表示空字符串不需要分割。为什么是 -1因为当我们从j0开始分割最后一个子串是s[0:i]时这意味着前0个字符已经处理完分割次数是dp[0]然后加上当前这次分割1。我们希望dp[0] 1 0所以dp[0]初始化为 -1。其他dp[i]初始化为一个很大的数比如inf表示暂时无法分割。合法性检查 对于一个子串sub s[j:i]不能有前导零即sub[0] ! ‘0’除非sub的长度为1且就是‘0’。换句话说如果i - j 1且s[j] ‘0’则非法。数值不超过 k将子串转换成整数判断是否 k。这里要注意k最大可达 10^9子串长度最多为 10因为如果长度超过10即使是全1数值也至少是10^10 10^9肯定超过k所以转换成整数不会溢出。但为了效率我们可以在转换过程中一旦超过 k 就提前终止剪枝。4.2 代码实现与细节处理def minimumPartition(s: str, k: int) - int: n len(s) INF 10**9 dp [INF] * (n 1) dp[0] -1 # 空串的基础分割次数为-1 for i in range(1, n 1): # 尝试所有可能的最后一个子串的起点j # 从后往前找方便做数值剪枝 val 0 # j从i-1递减到0这样val是累加 s[j] * 10^(i-j-1) # 但为了清晰我们也可以从j开始正向构建子串 for j in range(i-1, -1, -1): # 检查前导零如果子串长度1且首字符是0非法 if i - j 1 and s[j] 0: # 如果已经有前导零更短的子串j更小也一定以0开头直接break # 但这里我们简单跳过本次循环 continue # 构建子串 s[j:i] 对应的数值同时判断是否超过k # 从j开始逐位构建 sub_val 0 valid True for t in range(j, i): sub_val sub_val * 10 (ord(s[t]) - ord(0)) if sub_val k: valid False break if valid: dp[i] min(dp[i], dp[j] 1) else: # 如果当前子串已经超过k那么更长的子串j更小数值更大肯定也超过k可以提前break # 因为j是从i-1往左遍历子串在变长 break return dp[n] if dp[n] INF else -1时间复杂度O(n^2)在字符串长度最大为 1000 的情况下最坏情况是 10^6 级别可以接受。内层循环有剪枝优化数值超过k就break。空间复杂度O(n)。4.3 贪心思路的可行性探讨看到“最少分割”可能有人会想用贪心从左到右尽可能取长的合法子串。例如对于s”165462”, k60贪心会取”165”16560不行然后缩短为”16”合法接着从’5’开始取”54”合法接着取”6”最后取”2”。结果也是分割3次。这个贪心策略正确吗我们需要构造反例。考虑s”123456”, k129。贪心”123”123129合法剩余”456””456”129无法分割失败。但实际上存在分割”12”|”34”|”56”值分别为12,34,56都129。所以贪心策略尽可能取长是错误的。因为当前取一个较短的合法子串可能为后面留下更“好分”的余地。因此这道题必须使用动态规划来保证找到全局最优解。个人踩坑点在竞赛中我一开始也想到了贪心但很快意识到需要证明。尝试举反例是验证贪心策略的快速方法。当举不出反例时也要小心可能只是例子不够刁钻。对于分割、子序列类的最值问题DP通常是更可靠的选择。5. 第四题范围内最接近的两个质数这是本次周赛的压轴题难度明显提升。题目给定两个整数left和right你需要找到在闭区间[left, right]中的所有质数然后返回其中差值最小的两个质数。如果有多个答案返回数值较小的那一对。题目保证left和right之间至少有两个质数。示例left 10, right 19区间内的质数有 [11, 13, 17, 19]。差值分别是13-112, 17-134, 19-172。最小差值是2有两对(11,13)和(17,19)。返回数值较小的 (11,13)。数据范围1 left right 10^6。5.1 算法核心筛法与线性扫描问题的关键分为两步找出区间内所有质数区间最大跨度可达 10^6直接对每个数用试除法判断质数O(n√n)会超时。必须使用高效的质数筛法最经典的是埃拉托斯特尼筛法埃氏筛。在质数列表中找最小差值对得到有序的质数列表后只需要遍历一次计算相邻质数的差值并记录最小值及其对应的质数对即可。埃氏筛Sieve of Eratosthenes原理初始化一个布尔数组is_prime[0…right]全部标记为True。将is_prime[0]和is_prime[1]标记为False。从p 2开始遍历到sqrt(right)。如果is_prime[p]为True那么p是一个质数。然后将p的所有倍数从p*p开始到right结束步长为p标记为False。因为小于p*p的倍数如2p,3p, …,(p-1)p已经在之前更小的质数如2,3,…的筛选中被标记过了。遍历结束后数组中仍为True的下标就是质数。针对本题的优化 我们只需要[left, right]区间内的质数。但筛法通常需要从2开始筛到right才能正确标记出区间内的合数。一个常见的空间优化是只创建长度为right-left1的数组表示区间内的每个数。然后对于每个质数p找到第一个大于等于left的p的倍数从这个倍数开始标记。这需要知道小于等于sqrt(right)的所有质数所以需要先筛出[2, sqrt(right)]的质数。这种方法区间筛更省空间但实现稍复杂。对于right 10^6直接筛到right的内存开销约1MB布尔数组和时间开销都是可以接受的。5.2 详细实现步骤与代码我们采用标准的埃氏筛然后收集[left, right]内的质数最后扫描找最小差值对。def closestPrimes(left: int, right: int) - List[int]: # 1. 埃氏筛筛出[0, right]内的所有质数标记 is_prime [True] * (right 1) if right 0: is_prime[0] False if right 1: is_prime[1] False # 只需筛到 sqrt(right) import math for i in range(2, int(math.sqrt(right)) 1): if is_prime[i]: # 从 i*i 开始标记因为更小的倍数已经被之前的质数标记过了 for j in range(i * i, right 1, i): is_prime[j] False # 2. 收集[left, right]区间内的质数 primes_in_range [] for num in range(left, right 1): if is_prime[num]: primes_in_range.append(num) # 3. 寻找最小差值对 if len(primes_in_range) 2: # 根据题意不会发生但保持健壮性 return [-1, -1] min_diff float(inf) ans [-1, -1] for i in range(len(primes_in_range) - 1): diff primes_in_range[i1] - primes_in_range[i] if diff min_diff: min_diff diff ans [primes_in_range[i], primes_in_range[i1]] # 如果差值相等题目要求返回数值较小的对由于我们是顺序遍历第一次遇到的最小差值对就是数值较小的所以无需额外判断 return ans时间复杂度埃氏筛的时间复杂度是 O(n log log n)其中 n right。后续收集和扫描是 O(n)。对于 n10^6完全可行。空间复杂度O(n)用于布尔数组。5.3 性能优化与边界陷阱筛法的内层循环起点从i*i开始标记非常重要。如果从2*i开始会做大量重复工作。例如i5时10、15、20已经被i2和i3标记过了。sqrt(right)的计算循环终止条件是i sqrt(right)。在代码中我们预先计算int(math.sqrt(right)) 1作为上限避免在循环条件中重复计算平方根。区间筛的考虑当left和right非常大比如10^12但区间长度right-left1相对较小比如10^6时就需要用区间筛法来避免创建巨大的数组。其核心是先筛出[2, sqrt(right)]的所有质数然后用这些质数去标记[left, right]区间内的合数。本题数据范围不需要但这是一个重要的进阶知识点。结果初始化在寻找最小差值时min_diff初始化为无穷大ans初始化为[-1, -1]。由于题目保证有解最后ans一定会被更新。差值为1的情况质数对差值为1的只有 (2,3)。如果区间包含2和3答案就是它们。我们的算法能正确处理。这道题综合考察了数论质数筛法和基础算法线性扫描是质量很高的一道题。在竞赛中能够快速回忆起埃氏筛的模板并正确实现是解决此题的关键。 LeetCode周赛326复盘：从整数处理、质因数到动态规划与质数筛的实战解析
1. 赛况速览与个人复盘视角又一场LeetCode周赛结束了这次是第326场日期是2023年1月1日。新年第一赛题目难度和风格都挺有意思既有考验基础数据结构熟练度的送分题也有需要一点巧思的中等题还有一道能拉开差距的、对思维缜密度要求比较高的题目。我习惯在赛后立刻复盘把解题思路、踩过的坑以及代码实现上的优化点都记录下来这比单纯看题解要有效得多。今天这篇复盘我就从一个普通参赛者的视角分享一下这四道题的解题过程、关键思路以及一些个人在实战中的体会。无论你是想了解这场比赛的概况还是想学习如何更高效地应对这类算法竞赛希望这篇内容都能给你带来一些直接的参考价值。2. 第一题统计能整除数字的位数这道题是典型的签到题考察的是对整数逐位处理的基本功。题目要求给定一个整数num返回num中能被其自身每一位上的数字整除的位数。换句话说我们需要取出num的每一位数字然后判断num是否能被这个数字整除注意题目明确说明数字0不能作为除数因此遇到某一位是0时直接跳过不计入结果。2.1 核心思路与实现细节这道题的思路非常直接保存原始值因为我们需要用原始的num去对每一位数字取模而在循环中我们可能会修改num的值比如通过除以10来取位所以必须先保存一份原始值original_num。循环取位使用while循环每次通过num % 10获取当前最低位的数字digit然后通过num // 10去掉最低位直到num变为 0。判断与计数对于每一位digit首先判断是否为 0。如果为 0根据题意original_num % 0会导致运行时错误且 0 不能整除任何数所以直接跳过。如果digit不为 0则判断original_num % digit 0是否成立。如果成立则结果计数器加一。返回结果循环结束后返回计数器的值。这里有一个非常容易疏忽的坑点直接在循环中修改num并用于取模判断。比如下面这段错误代码def countDigits(num: int) - int: count 0 while num 0: digit num % 10 if digit ! 0 and num % digit 0: # 错误这里的num已经被修改了 count 1 num // 10 return count当num是 1248 时第一次循环digit8,num1248判断1248%80正确。但第二次循环时num已经变成了 124此时digit4判断的是124%40这依然是正确的巧合。但如果num是 121第一次循环后num变成 12第二次循环判断12%20而实际上应该判断121%2!0这就出错了。所以务必保存原始值。正确的实现如下def countDigits(num: int) - int: original_num num count 0 while num 0: digit num % 10 if digit ! 0 and original_num % digit 0: count 1 num // 10 return count时间复杂度O(log₁₀(num))即数字的位数。空间复杂度O(1)。2.2 实战技巧与变体思考这道题虽然简单但可以引申出一些有用的编程习惯和思考。防御性编程处理数字和除法时永远要考虑除数为 0 的情况。即使题目描述可能隐含了这一点在代码中显式判断也能让逻辑更清晰、更健壮。字符串转换法另一种常见的解法是将整数转换为字符串然后遍历每个字符再转回整数进行判断。例如for digit_char in str(num): digit int(digit_char); ...。这种方法代码更简洁但性能略低于数学方法因为涉及字符串转换和创建。在竞赛中对于这种数据范围很小的题目两种方法都可以但知道数学方法更体现基本功。扩展思考如果题目改为“统计数字中能整除该位数字的位数”即digit % original_num 0或者统计的是“各位数字之和”等核心的取位和判断框架是不变的只是判断条件不同。这提醒我们要抽象出问题的通用部分。3. 第二题数组乘积中的不同质因数数目这道题开始需要一些数学知识。题目给出一个正整数数组nums要求返回数组所有元素乘积中不同质因数的数目。例如nums [2,4,3,7]乘积是2*4*3*7168。168的质因数分解是2^3 * 3 * 7其中不同的质因数是 {2, 3, 7}所以答案是 3。3.1 问题转化与高效解法最直接的想法是先算出所有数的乘积然后对这个乘积进行质因数分解最后统计不同的质因数。但这样做有两个问题乘积可能非常大数组长度和元素值都可能很大直接相乘会导致整数溢出即使在Python中不会溢出但大数运算效率低且分解大质因数非常困难。分解大数质因数很耗时这是一个经典的难题。因此我们必须转换思路。关键洞察整个数组乘积的质因数必然来自于每个数组元素的质因数。反之每个数组元素的质因数也必然是最终乘积的质因数。所以我们不需要计算乘积只需要分别找出每个数组元素的所有质因数然后求这些质因数的并集即可。那么如何高效地求一个数x的所有质因数呢这里用到经典的试除法。从i 2开始循环到sqrt(x)。如果x % i 0说明i是x的一个因数。此时i一定是质数吗不一定但我们可以通过循环将x中的所有i因子除尽while x % i 0: x // i。这样操作后后续的i就不会是合数因子了因为合数因子已经被它的质因数提前分解掉了。例如x12i2时12%20我们一直除到x3。下一个i33%30。i4时x已经是3不会进入判断。所以我们收集到的i就是质因数。循环结束后如果x 1那么剩下的x本身也是一个质因数例如x13循环i从2到3都没有整除最后x13113就是质因数。实现时我们用一个集合set来存储所有出现过的质因数避免重复。def distinctPrimeFactors(nums: List[int]) - int: prime_factors set() def get_prime_factors(x): i 2 # 只需要试除到 sqrt(x) while i * i x: if x % i 0: prime_factors.add(i) # 除尽所有i因子 while x % i 0: x // i i 1 # 处理剩余的大于sqrt(x)的质因数 if x 1: prime_factors.add(x) for num in nums: get_prime_factors(num) return len(prime_factors)时间复杂度O(N * sqrt(M))其中 N 是数组长度M 是数组中最大的数。对于每个数我们最多试除到其平方根。空间复杂度O(P)P 是所有不同质因数的个数这个集合通常不会很大。3.2 优化与边界情况处理试除法的优化在get_prime_factors函数中i每次加1。一个常见的优化是当i2处理完后i可以从3开始每次加2只检查奇数因为除了2以外的偶数都不是质数。可以进一步优化为i2, 3后每次加6检查i和i2即6k±1的形式但这对于竞赛环境通常不是必需的。去重时机我们是在处理每个数字的过程中直接向全局集合prime_factors中添加质因数。也可以先为每个数字生成一个质因数列表最后再合并去重但这样空间开销稍大。大数处理这个算法能够有效处理较大的数字因为分解是逐个数字独立进行的避免了计算巨大乘积。这是解决此类问题的标准且安全的方法。4. 第三题将字符串分割成值不超过 K 的子字符串这道题是一个不错的字符串分割问题带有贪心或动态规划的色彩。题目给定一个字符串s由数字组成和一个整数k。我们需要将s分割成若干连续子串使得每个子串表示的整数值小于等于k同时要求子串不能有前导零除非这个子串就是单个字符‘0’。要求返回满足条件的最少分割次数。如果无法分割则返回 -1。示例s “165462”, k 60。我们可以分割成“16” | “54” | “6” | “2”。子串对应的数字分别是16, 54, 6, 2都 60且没有前导零。分割了3次产生了4个子串。更少的分割方式可能不存在。4.1 动态规划思路解析求“最少分割次数”这是一个最优化问题通常可以用动态规划DP来解决。定义dp[i]表示字符串前i个字符即s[0:i]分割成合法子串的最少分割次数。我们最终要求的是dp[n]其中n是字符串长度。状态转移方程 为了计算dp[i]我们需要考虑最后一个子串可能是什么。假设最后一个子串是s[j:i]即从索引j到i-1那么前j个字符的分割方案数就是dp[j]。因此我们需要检查所有可能的j0 j i使得子串s[j:i]是合法的无非前导零且值 k然后取所有合法情况下的最小值dp[i] min(dp[j] 1)其中s[j:i]合法。初始化dp[0] -1。这是一个技巧性的初始化。表示空字符串不需要分割。为什么是 -1因为当我们从j0开始分割最后一个子串是s[0:i]时这意味着前0个字符已经处理完分割次数是dp[0]然后加上当前这次分割1。我们希望dp[0] 1 0所以dp[0]初始化为 -1。其他dp[i]初始化为一个很大的数比如inf表示暂时无法分割。合法性检查 对于一个子串sub s[j:i]不能有前导零即sub[0] ! ‘0’除非sub的长度为1且就是‘0’。换句话说如果i - j 1且s[j] ‘0’则非法。数值不超过 k将子串转换成整数判断是否 k。这里要注意k最大可达 10^9子串长度最多为 10因为如果长度超过10即使是全1数值也至少是10^10 10^9肯定超过k所以转换成整数不会溢出。但为了效率我们可以在转换过程中一旦超过 k 就提前终止剪枝。4.2 代码实现与细节处理def minimumPartition(s: str, k: int) - int: n len(s) INF 10**9 dp [INF] * (n 1) dp[0] -1 # 空串的基础分割次数为-1 for i in range(1, n 1): # 尝试所有可能的最后一个子串的起点j # 从后往前找方便做数值剪枝 val 0 # j从i-1递减到0这样val是累加 s[j] * 10^(i-j-1) # 但为了清晰我们也可以从j开始正向构建子串 for j in range(i-1, -1, -1): # 检查前导零如果子串长度1且首字符是0非法 if i - j 1 and s[j] 0: # 如果已经有前导零更短的子串j更小也一定以0开头直接break # 但这里我们简单跳过本次循环 continue # 构建子串 s[j:i] 对应的数值同时判断是否超过k # 从j开始逐位构建 sub_val 0 valid True for t in range(j, i): sub_val sub_val * 10 (ord(s[t]) - ord(0)) if sub_val k: valid False break if valid: dp[i] min(dp[i], dp[j] 1) else: # 如果当前子串已经超过k那么更长的子串j更小数值更大肯定也超过k可以提前break # 因为j是从i-1往左遍历子串在变长 break return dp[n] if dp[n] INF else -1时间复杂度O(n^2)在字符串长度最大为 1000 的情况下最坏情况是 10^6 级别可以接受。内层循环有剪枝优化数值超过k就break。空间复杂度O(n)。4.3 贪心思路的可行性探讨看到“最少分割”可能有人会想用贪心从左到右尽可能取长的合法子串。例如对于s”165462”, k60贪心会取”165”16560不行然后缩短为”16”合法接着从’5’开始取”54”合法接着取”6”最后取”2”。结果也是分割3次。这个贪心策略正确吗我们需要构造反例。考虑s”123456”, k129。贪心”123”123129合法剩余”456””456”129无法分割失败。但实际上存在分割”12”|”34”|”56”值分别为12,34,56都129。所以贪心策略尽可能取长是错误的。因为当前取一个较短的合法子串可能为后面留下更“好分”的余地。因此这道题必须使用动态规划来保证找到全局最优解。个人踩坑点在竞赛中我一开始也想到了贪心但很快意识到需要证明。尝试举反例是验证贪心策略的快速方法。当举不出反例时也要小心可能只是例子不够刁钻。对于分割、子序列类的最值问题DP通常是更可靠的选择。5. 第四题范围内最接近的两个质数这是本次周赛的压轴题难度明显提升。题目给定两个整数left和right你需要找到在闭区间[left, right]中的所有质数然后返回其中差值最小的两个质数。如果有多个答案返回数值较小的那一对。题目保证left和right之间至少有两个质数。示例left 10, right 19区间内的质数有 [11, 13, 17, 19]。差值分别是13-112, 17-134, 19-172。最小差值是2有两对(11,13)和(17,19)。返回数值较小的 (11,13)。数据范围1 left right 10^6。5.1 算法核心筛法与线性扫描问题的关键分为两步找出区间内所有质数区间最大跨度可达 10^6直接对每个数用试除法判断质数O(n√n)会超时。必须使用高效的质数筛法最经典的是埃拉托斯特尼筛法埃氏筛。在质数列表中找最小差值对得到有序的质数列表后只需要遍历一次计算相邻质数的差值并记录最小值及其对应的质数对即可。埃氏筛Sieve of Eratosthenes原理初始化一个布尔数组is_prime[0…right]全部标记为True。将is_prime[0]和is_prime[1]标记为False。从p 2开始遍历到sqrt(right)。如果is_prime[p]为True那么p是一个质数。然后将p的所有倍数从p*p开始到right结束步长为p标记为False。因为小于p*p的倍数如2p,3p, …,(p-1)p已经在之前更小的质数如2,3,…的筛选中被标记过了。遍历结束后数组中仍为True的下标就是质数。针对本题的优化 我们只需要[left, right]区间内的质数。但筛法通常需要从2开始筛到right才能正确标记出区间内的合数。一个常见的空间优化是只创建长度为right-left1的数组表示区间内的每个数。然后对于每个质数p找到第一个大于等于left的p的倍数从这个倍数开始标记。这需要知道小于等于sqrt(right)的所有质数所以需要先筛出[2, sqrt(right)]的质数。这种方法区间筛更省空间但实现稍复杂。对于right 10^6直接筛到right的内存开销约1MB布尔数组和时间开销都是可以接受的。5.2 详细实现步骤与代码我们采用标准的埃氏筛然后收集[left, right]内的质数最后扫描找最小差值对。def closestPrimes(left: int, right: int) - List[int]: # 1. 埃氏筛筛出[0, right]内的所有质数标记 is_prime [True] * (right 1) if right 0: is_prime[0] False if right 1: is_prime[1] False # 只需筛到 sqrt(right) import math for i in range(2, int(math.sqrt(right)) 1): if is_prime[i]: # 从 i*i 开始标记因为更小的倍数已经被之前的质数标记过了 for j in range(i * i, right 1, i): is_prime[j] False # 2. 收集[left, right]区间内的质数 primes_in_range [] for num in range(left, right 1): if is_prime[num]: primes_in_range.append(num) # 3. 寻找最小差值对 if len(primes_in_range) 2: # 根据题意不会发生但保持健壮性 return [-1, -1] min_diff float(inf) ans [-1, -1] for i in range(len(primes_in_range) - 1): diff primes_in_range[i1] - primes_in_range[i] if diff min_diff: min_diff diff ans [primes_in_range[i], primes_in_range[i1]] # 如果差值相等题目要求返回数值较小的对由于我们是顺序遍历第一次遇到的最小差值对就是数值较小的所以无需额外判断 return ans时间复杂度埃氏筛的时间复杂度是 O(n log log n)其中 n right。后续收集和扫描是 O(n)。对于 n10^6完全可行。空间复杂度O(n)用于布尔数组。5.3 性能优化与边界陷阱筛法的内层循环起点从i*i开始标记非常重要。如果从2*i开始会做大量重复工作。例如i5时10、15、20已经被i2和i3标记过了。sqrt(right)的计算循环终止条件是i sqrt(right)。在代码中我们预先计算int(math.sqrt(right)) 1作为上限避免在循环条件中重复计算平方根。区间筛的考虑当left和right非常大比如10^12但区间长度right-left1相对较小比如10^6时就需要用区间筛法来避免创建巨大的数组。其核心是先筛出[2, sqrt(right)]的所有质数然后用这些质数去标记[left, right]区间内的合数。本题数据范围不需要但这是一个重要的进阶知识点。结果初始化在寻找最小差值时min_diff初始化为无穷大ans初始化为[-1, -1]。由于题目保证有解最后ans一定会被更新。差值为1的情况质数对差值为1的只有 (2,3)。如果区间包含2和3答案就是它们。我们的算法能正确处理。这道题综合考察了数论质数筛法和基础算法线性扫描是质量很高的一道题。在竞赛中能够快速回忆起埃氏筛的模板并正确实现是解决此题的关键。