当前位置：首页 > news >正文

LeetCode算法精解：利用25整除特性优化字符串操作问题

news 2026/8/1 18:06:23

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整除的两位数有哪些呢？很简单：

00
25
50
75

只有这四种情况。因此，我们的目标从“让整个数字能被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 - 1（n是字符串长度）。
为了让'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; // 初始化为最大值 // 定义四个需要搜索的目标对 vector<pair<char, 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的操作次数比删除所有字符还多？实际上，只要有一个0，ans就会被更新为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. 逐步演算与测试用例分析

为了确保完全理解，我们拿几个典型的测试用例，手动走一遍算法流程。

用例1：num = "2245047"

长度n = 7。
遍历目标对：
- ("0","0"): 找最后一个‘0‘，位置j=4("5047"中的0)。在位置4左边找最后一个‘0‘，找不到 (i=-1)。跳过。
- ("2","5"): 找最后一个‘5‘，位置j=3("5047"中的5)。在位置3左边找最后一个‘2‘，找到i=1("224"中的第二个2)。有效配对！操作次数 =7 - 1 - 2 = 4。ans=4。
- ("5","0"): 找最后一个‘0‘，j=4。在位置4左边找最后一个‘5‘，找到i=3。有效配对！操作次数 =7 - 3 - 2 = 2。ans=min(4,2)=2。
- ("7","5"): 找最后一个‘5‘，j=3。在位置3左边找最后一个‘7‘，找不到 (i=-1)。跳过。
单独处理‘0‘：找最右边的‘0‘，位置k=4。操作次数k=4。ans=min(2,4)=2。
ans已更新为2，不等于初始值7，返回2。
- 验证：删除下标为3和4的字符（即‘5‘和‘0‘）？不对，我们的配对是("5","0")，i=3,j=4。公式n-i-2=2意味着要删除2个字符。实际上，保留下标为3和4的字符‘5‘和‘0‘作为最后两位，需要删除它们之间和之后的字符。它们之间没有字符 (j-i-1=0)，之后有字符"47"(n-j-1=2)。所以删除最后两个字符"47"，剩下"22450"，最后两位是"50"，正确。或者，根据("2","5")配对，删除4个字符也能得到"25"，但不是最优。

用例2：num = "10"

n=2。
遍历目标对：
- ("0","0"): 找最后一个‘0‘，j=1。在位置1左边找最后一个‘0‘，找不到 (i=-1)。跳过。
- ("2","5"): 找不到‘5‘，跳过。
- ("5","0"): 找最后一个‘0‘，j=1。在位置1左边找最后一个‘5‘，找不到 (i=-1)。跳过。
- ("7","5"): 找不到‘5‘，跳过。
单独处理‘0‘：找最右边的‘0‘，k=1。操作次数k=1。ans=1。
返回1。
- 验证：删除第一个字符‘1‘，剩下"0"，数字0能被25整除。正确。

用例3：num = "999"

n=3。
所有目标对都找不到。
单独处理‘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‘分支，ans=0，返回0。"00"会通过目标对"00"分支，计算出操作次数为2-0-2=0，同样返回0。