LeetCode-day25-2844. 生成特殊数字的最少操作

题目描述

给你一个下标从 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 位数字。

思路

枚举末尾 + 一次遍历

从右往左遍历的过程中：

• 在之前找到 0 的情况下，如果当前数字 num[i] 是 0 或者 5，则立刻返回 n−i−2。
• 在之前找到 5 的情况下，如果当前数字num[i] 是 2 或者 7，则立刻返回 n−i−2。
• 否则，如果 num[i] 是 0，标记我们找到了 0。
• 否则，如果 num[i]是 5，标记我们找到了 5。
• 如果循环中没有返回，则最后返回 n 或者 n−1，取决于我们是否找到了 0。

代码

class Solution:
    def minimumOperations(self, num: str) -> int:
        n = len(num)
        found0 = found5 = False
        for i in range(n-1,-1,-1):
            c = num[i]
            if found0 and c in '05' or found5 and c in '27':
                return n-i-2
            if c== '0':
                found0=True
            elif c == '5':
                found5=True
        return n-found0
1
2
3
4
5
6
7
8
9
10
11
12
13