1. 项目概述从一道“特殊数字”题看算法思维的精妙最近在LeetCode上刷题又遇到了一道让我停下来琢磨了好一会儿的题目——生成特殊数字的最少操作。这道题被标记为“中等”难度乍一看题目描述感觉像是那种需要一些数学洞察力再结合字符串或动态规划技巧的典型问题。对于正在准备面试或者想巩固C算法功底的开发者来说这类题目往往比纯粹的“困难”题更有价值因为它考察的不是冷僻的知识点而是将基础数据结构、逻辑思维和问题转化能力融会贯通的水平。这道题的核心是给定一个由数字组成的字符串你可以执行一种操作——删除字符串中的任意一个字符。你的目标是通过最少的删除操作使得剩下的字符串所表示的数字能够被25整除。我们需要返回这个最少的操作次数。如果无法通过删除得到能被25整除的数字则返回-1。为什么是25这可不是随便选的。25是5的平方而判断一个数能否被25整除有一个非常简洁的规则一个数能被25整除当且仅当它的最后两位是00, 25, 50, 75。这个小学数学知识点就是解开本题的“钥匙”。一旦抓住这个关键问题就从“处理一个大整数”简化为了“在字符串中寻找特定的两位后缀”。整个解题的思维过程从暴力枚举的迷雾到清晰的双指针搜索充满了算法优化和边界条件处理的乐趣。接下来我就结合C的实现把这道题的思路掰开揉碎了讲清楚包括如何推导、如何编码以及那些容易踩坑的细节。2. 核心思路拆解为什么是“最后两位”在动手写代码之前我们必须把问题理解透彻。题目要求最终的数字能被25整除。在编程中直接处理大数取模固然可以但字符串可能很长操作次数有限我们需要一个更聪明的判定条件。2.1 数学原理25整除性的决定性条件这里用到的是数论中的一个基本性质对于任何整数N我们都可以将其表示为N 100 * k m其中m是N的最后两位数字组成的数00 m 99。因为100能被25整除100 25 * 4所以N能否被25整除完全取决于m能否被25整除。换句话说N % 25 0当且仅当m % 25 0。那么在00到99之间能被25整除的两位数有哪些呢很简单00255075只有这四种情况。因此我们的目标从“让整个数字能被25整除”精确地转化为了通过删除字符使得字符串的最后两位即剩下的数字的最末两位是00,25,50,75中的一个。注意这里有一个非常重要的隐含条件——“最后两位”。这意味着为了形成有效的两位数字符串在删除后至少需要保留两位数字。如果删除到只剩一位或零位即使那一位是0或5也无法满足条件因为一位数无法构成“最后两位”。这一点是许多解法初始时容易忽略的边界情况。2.2 问题转化从数学到字符串搜索现在问题变成了一个字符串搜索与删除问题对于一个给定的数字字符串num我们希望通过最少的删除操作使其末尾两位是上述四个目标对之一。我们可以这样思考对于每一个目标对例如25我们需要在原始字符串num中从右向左找到字符5和2并且2的位置必须在5的左边因为最终2要在5前面。找到这两个字符后删除它们之间以及它们右侧的所有无关字符就可以让它们成为字符串的最后两位。所需的删除次数就是找到这两个字符时需要移除的字符数量。更具体地说假设我们在字符串中找到了字符5的位置为j字符2的位置为i且i j。那么为了让5成为最后一位我们需要删除5之后的所有字符。删除次数为n - j - 1n是字符串长度。为了让2成为倒数第二位我们需要删除2和5之间的所有字符。删除次数为j - i - 1。因此总删除次数为(n - j - 1) (j - i - 1) n - i - 2。这个公式非常优美它告诉我们对于一组找到的(i, j)操作次数只与第一个字符的位置i和字符串总长度n有关。我们的任务就是为每个目标对找到最靠右的、满足顺序的(i, j)从而使得i尽可能大因为n是定值i越大操作次数n-i-2越小即找到最靠右的有效配对。2.3 算法选择贪心搜索与动态规划有了以上分析我们有两种主要的实现路径贪心搜索反向遍历这是本题最直观高效的解法。对于每个目标对(a, b)例如(‘2‘ ‘5’)我们从字符串末尾向前遍历先找到最后一个‘b‘即‘5‘记录其位置j然后从j-1的位置继续向前遍历找到最后一个‘a‘即‘2‘记录其位置i。如果都能找到且i j则这是一个有效配对计算操作次数n - i - 2。我们遍历所有四个目标对取操作次数的最小值。优点思路清晰时间复杂度为 O(n)只需要常数次的字符串遍历4个目标对 * 2次查找。缺点需要小心处理查找顺序和边界条件。动态规划DP可以定义状态dp[i][r]表示考虑前i个字符当前数字模25的余数为r时所需的最少删除次数。通过状态转移删除当前字符或不删除来求解。最终答案是dp[n][0]。优点是一种更为通用的解法如果除数改变比如变成125思路无需大改。缺点对于本题特定的除数25显得有些“杀鸡用牛刀”状态转移需要考虑字符转数字实现稍复杂且时间复杂度为 O(n * 25)。对于这道题贪心搜索无疑是更优雅、更高效的选择。它不仅运行快代码也相对简洁完美体现了“将复杂问题转化为简单观察”的算法之美。我们接下来的实现也将以贪心搜索为核心。3. C实现与代码精析理解了核心思路我们就可以着手用C实现了。我们的目标是写出一份既正确又健壮的代码能够处理各种边界情况。3.1 基础框架与函数签名首先我们根据LeetCode的题目要求定义函数。输入是一个字符串num输出是一个整数表示最少操作次数。class Solution { public: int minimumOperations(string num) { int n num.size(); int ans n; // 最坏情况删除所有字符但注意删除光也不满足条件 // ... 具体逻辑 return (ans n) ? -1 : ans; // 如果ans没被更新说明无法形成返回-1 } };这里初始化ans n表示最坏情况下的操作次数即删除所有字符。但根据题意删除光所有字符后数字不存在或视为0而0虽然能被25整除但题目要求的是“数字”通常至少有一位。所以我们需要检查是否真的能找到有效配对。3.2 贪心搜索的实现细节我们将对四个目标对(00, 25, 50, 75)分别进行搜索。对于每一对(a, b)从右向左遍历字符串找到最后一个等于b的字符记录下标j。如果找到了j再从j-1开始向左遍历找到最后一个等于a的字符记录下标i。如果i和j都找到了即i ! -1 j ! -1那么这就是一个有效配对。所需删除操作次数为n - i - 2。用这个次数更新全局最小答案ans。这里有一个关键的优化点我们寻找的是“最后一个”b和“在它之前的最后一个”a。这保证了我们找到的配对是所有可能配对中最靠右的从而使得i最大操作次数n-i-2最小。这是一种贪心思想。class Solution { public: int minimumOperations(string num) { int n num.size(); int ans n; // 初始化为最大值 // 定义四个需要搜索的目标对 vectorpairchar, char targets {{0, 0}, {2, 5}, {5, 0}, {7, 5}}; for (auto [a, b] : targets) { int j -1, i -1; // 第一步从右向左找最后一个 b for (int k n - 1; k 0; --k) { if (num[k] b) { j k; break; } } if (j -1) continue; // 没找到b这个目标对不可能 // 第二步从 j-1 向左找最后一个 a for (int k j - 1; k 0; --k) { if (num[k] a) { i k; break; } } if (i -1) continue; // 没找到a这个目标对不可能 // 计算操作次数并更新答案 ans min(ans, n - i - 2); } // 特殊情况处理如果整个字符串本身就是0或者删除后只剩0 // 我们的算法中目标对00会覆盖这种情况删除到只剩一个0不需要两位。 // 但题目可能允许最终数字就是单个0我们需要仔细审题。 // 常见理解至少需要两位数字。但有一种边界如果字符串中只有一个非零数字我们永远无法得到两位。 // 然而如果字符串中有‘0‘我们可以尝试删除其他所有字符只留一个‘0‘。此时数字0能被25整除。 // 这对应着寻找目标对‘00‘但只找到了一个‘0‘的情况。我们需要单独处理。 // 让我们检查是否能通过删除只得到一个‘0‘。 for (int k n - 1; k 0; --k) { if (num[k] 0) { // 找到了一个‘0‘删除它之前的所有字符即可 ans min(ans, k); // 删除前k个字符 (下标0到k-1) break; // 找最右边的一个0删除次数最少 } } // 注意如果字符串全是‘0‘上述循环找到最后一个‘0‘ans会被更新为n-1但我们的目标对00会给出n-2更优。 return (ans n) ? -1 : ans; } };3.3 边界条件与陷阱处理上面的代码已经比较完整但其中包含了几个至关重要的边界处理和容易出错的点单个‘0‘的情况这是本题最大的陷阱之一。我们的核心思路是找“最后两位”这隐含了字符串长度至少为2。但如果原始字符串是0或者我们可以通过删除只留下一个‘0‘数字0是能被25整除的。我们的目标对00无法处理这种情况因为需要两个0。因此必须在主循环之外单独处理“只留一个0”的情况。如代码所示我们找到最右边的一个‘0‘删除它左边所有的字符操作次数就是它的下标k。用这个次数去更新答案。全零字符串对于字符串000我们的算法会通过目标对00找到最右边两个0计算出操作次数为n - i - 2 3 - 0 - 2 1即删除第一个0。通过单独处理‘0‘找到最右边的0下标2计算出操作次数为k 2删除前两个0。min(1, 2) 1所以正确答案是1。这是对的因为删除第一个0后剩下00可以被25整除。找不到任何有效配对如果四个目标对都找不到并且字符串里也没有‘0‘或者有0但删除到只剩0的操作次数比删除所有字符还多实际上只要有一个0ans就会被更新为k而k n-1 n那么ans将保持初始值n。按照题目要求此时应返回-1。代码最后一句return (ans n) ? -1 : ans;正是处理这种情况。下标计算操作次数公式n - i - 2务必推导清楚。n是长度i是第一个字符目标对左字符的下标。删除i和j之间的字符以及j之后的字符总共删除的数量是(j - i - 1) (n - j - 1) n - i - 2。确保你的计算和这个一致。搜索顺序在寻找目标对(a, b)时必须先找b再在b的左边找a。顺序反了就会得到错误配对例如先找‘2‘再找‘5‘可能找到的‘5‘在‘2‘左边无法组成25。4. 逐步演算与测试用例分析为了确保完全理解我们拿几个典型的测试用例手动走一遍算法流程。用例1num 2245047长度n 7。遍历目标对(0,0): 找最后一个‘0‘位置j4(5047中的0)。在位置4左边找最后一个‘0‘找不到 (i-1)。跳过。(2,5): 找最后一个‘5‘位置j3(5047中的5)。在位置3左边找最后一个‘2‘找到i1(224中的第二个2)。有效配对操作次数 7 - 1 - 2 4。ans4。(5,0): 找最后一个‘0‘j4。在位置4左边找最后一个‘5‘找到i3。有效配对操作次数 7 - 3 - 2 2。ansmin(4,2)2。(7,5): 找最后一个‘5‘j3。在位置3左边找最后一个‘7‘找不到 (i-1)。跳过。单独处理‘0‘找最右边的‘0‘位置k4。操作次数k4。ansmin(2,4)2。ans已更新为2不等于初始值7返回2。验证删除下标为3和4的字符即‘5‘和‘0‘不对我们的配对是(5,0)i3,j4。公式n-i-22意味着要删除2个字符。实际上保留下标为3和4的字符‘5‘和‘0‘作为最后两位需要删除它们之间和之后的字符。它们之间没有字符 (j-i-10)之后有字符47(n-j-12)。所以删除最后两个字符47剩下22450最后两位是50正确。或者根据(2,5)配对删除4个字符也能得到25但不是最优。用例2num 10n2。遍历目标对(0,0): 找最后一个‘0‘j1。在位置1左边找最后一个‘0‘找不到 (i-1)。跳过。(2,5): 找不到‘5‘跳过。(5,0): 找最后一个‘0‘j1。在位置1左边找最后一个‘5‘找不到 (i-1)。跳过。(7,5): 找不到‘5‘跳过。单独处理‘0‘找最右边的‘0‘k1。操作次数k1。ans1。返回1。验证删除第一个字符‘1‘剩下0数字0能被25整除。正确。用例3num 999n3。所有目标对都找不到。单独处理‘0‘找不到任何‘0‘。ans保持为初始值3。返回-1。验证无论如何删除都无法得到以00, 25, 50, 75结尾的数字也无法得到单独的0。正确。通过这几个例子可以看到算法在各种情况下的行为尤其是对单个‘0‘的特殊处理是如何起作用的。5. 复杂度分析与优化探讨时间复杂度我们遍历了4个目标对每个目标对进行最多两次线性扫描找b和找a。单独处理‘0‘也是一次线性扫描。因此总的时间复杂度是O(4 * 2 * n) ≈ O(n)是线性时间非常高效。空间复杂度我们只使用了常数个额外变量ans, i, j, k等因此空间复杂度是O(1)。潜在优化上述实现已经足够好。一个微小的优化是可以将四个目标对的搜索合并到一次或两次遍历中。例如只遍历一次字符串记录每个数字最后出现的位置。然后对于每个目标对(a,b)检查last_pos[a]和last_pos[b]是否存在且last_pos[a] last_pos[b]。但这样做需要处理a和b相同的情况如00逻辑会稍微复杂一些对于本题而言清晰的四次独立扫描在可读性上更有优势。6. 常见错误与调试心得在实现和调试这道题时我总结了几类常见的错误遗漏单个‘0‘的情况这是最常见的错误。只考虑了两位数的结尾没有考虑到数字0本身能被25整除。导致对于10,105这样的用例返回错误答案应该是1却返回了-1或更大的数。下标计算错误操作次数的公式n - i - 2容易记错或算错。有的朋友可能会写成n - j - 2或者(n - j - 1) (j - i - 1)但计算错误。务必在纸上用例子推导一遍。搜索顺序错误对于目标对(a, b)必须先从右向左找b再在b的左边找a。如果先找a再找b可能会找到b在a左边的无效配对。初始化与返回值错误ans初始化为n是合理的代表最坏情况。但返回值时如果ans仍然是n需要返回-1。这里要注意如果字符串本身可以通过删除所有字符变成空串题目通常不允许或者我们单独处理‘0‘时ans可能被更新为n当最右边的0在位置n-1时k n-1小于n。所以条件ans n是判断是否找到任何有效方案的可靠方法。处理全零字符串对于0或00算法应该能正确工作。0会通过单独处理‘0‘分支ans0返回0。00会通过目标对00分支计算出操作次数为2-0-20同样返回0。调试建议当你觉得代码逻辑正确但提交不通过时不要急于看题解。自己构造一些边缘用例最小长度0,5,00,25包含单个010,101,1230包含多个可行解1250(可以留25或50)无解999,123全零000用这些用例在本地或心里模拟运行你的代码一步步跟踪变量往往能自己发现逻辑漏洞。这种调试能力比单纯记住一道题的解法更重要。这道“生成特殊数字的最少操作”题完美地展示了LeetCode中等题的魅力它不需要高深的数据结构但需要敏锐的观察力发现25整除的规律、严谨的逻辑思维问题转化与贪心证明和扎实的编码功底边界条件处理。把这类题目吃透对于提升在面试中解决实际问题的能力大有裨益。
2——ATLAS：模板约束 LLM Agent 实现可靠的 SAR ADC 自动化设计)
