LeetCode 题解工作台
生成特殊数字的最少操作
给你一个下标从 0 开始的字符串 num ，表示一个非负整数。 在一次操作中，您可以选择 num 的任意一位数字并将其删除。请注意，如果你删除 num 中的所有数字，则 num 变为 0 。 返回最少需要多少次操作可以使 num 变成特殊数字。 如果整数 x 能被 25 整除，则该整数 x 被认为是…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们注意到，整数 要能被 整除，即 $x \bmod 25 = 0$。因此，我们可以设计一个函数 $dfs(i, k)$，表示从字符串 的第 位开始，且当前数字模 的结果为 的情况下，要使得数字变成特殊数字，最少需要删除多少位数字。那么答案为 $dfs(0, 0)$。 函数 $dfs(i, k)$ 的执行逻辑如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个下标从 0 开始的字符串 num ，表示一个非负整数。
在一次操作中，您可以选择 num 的任意一位数字并将其删除。请注意，如果你删除 num 中的所有数字，则 num 变为 0。
返回最少需要多少次操作可以使 num 变成特殊数字。
如果整数 x 能被 25 整除，则该整数 x 被认为是特殊数字。
示例 1：
输入：num = "2245047" 输出：2 解释：删除数字 num[5] 和 num[6] ，得到数字 "22450" ，可以被 25 整除。 可以证明要使数字变成特殊数字，最少需要删除 2 位数字。
示例 2：
输入：num = "2908305" 输出：3 解释：删除 num[3]、num[4] 和 num[6] ，得到数字 "2900" ，可以被 25 整除。 可以证明要使数字变成特殊数字，最少需要删除 3 位数字。
示例 3：
输入：num = "10" 输出：1 解释：删除 num[0] ，得到数字 "0" ，可以被 25 整除。 可以证明要使数字变成特殊数字，最少需要删除 1 位数字。
提示
1 <= num.length <= 100num仅由数字'0'到'9'组成num不含任何前导零
解题思路
方法一：记忆化搜索
我们注意到，整数 要能被 整除，即 。因此，我们可以设计一个函数 ，表示从字符串 的第 位开始，且当前数字模 的结果为 的情况下，要使得数字变成特殊数字，最少需要删除多少位数字。那么答案为 。
函数 的执行逻辑如下：
- 如果 ，即已经处理完字符串 的所有位，那么如果 ，则当前数字可以被 整除，返回 ，否则返回 ；
- 否则，第 位可以被删除，此时需要删除一位，即 ；第 位不删除，那么 的值变为 ，即 。取这两者的最小值即可。
为了防止重复计算，我们可以使用记忆化的方法优化时间复杂度。
时间复杂度 ，空间复杂度 。其中 是字符串 的长度。
class Solution:
def minimumOperations(self, num: str) -> int:
@cache
def dfs(i: int, k: int) -> int:
if i == n:
return 0 if k == 0 else n
ans = dfs(i + 1, k) + 1
ans = min(ans, dfs(i + 1, (k * 10 + int(num[i])) % 25))
return ans
n = len(num)
return dfs(0, 0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidates who optimize the search for valid digit pairs using greedy strategies show understanding of the problem's mathematical properties.
- question_mark
Look for candidates to validate their greedy approach by ensuring the fewest deletions are performed.
- question_mark
Candidates who struggle with identifying the valid divisibility conditions may need guidance on greedy algorithms.
常见陷阱
外企场景- error
Not considering the correct order of deletions can lead to extra operations. Ensure deletions are minimized by focusing on the last digits first.
- error
Overlooking edge cases such as the presence of a single zero digit. A single zero should result in at most n - 1 deletions.
- error
Incorrectly identifying valid divisibility endings. Ensure the number ends with '00', '25', '50', or '75' for divisibility by 25.
进阶变体
外企场景- arrow_right_alt
Consider handling numbers that already satisfy the divisibility condition to avoid unnecessary deletions.
- arrow_right_alt
Explore cases where the number has multiple valid digit pairs and ensure the minimal deletions are performed.
- arrow_right_alt
Handle large numbers efficiently, as the length of num can be up to 100 digits.