生成特殊数字的最少操作

难度: Medium

给你一个下标从 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 <= 100
num 仅由数字 '0' 到 '9' 组成
num 不含任何前导零

Submission

运行时间: 27 ms

内存: 16.1 MB

class Solution:
    def minimumOperations(self, num: str) -> int:
        n = len(num)
        res = n
        cnt = 0
        if num.find('0') >= 0:
            res = n - 1
        i = len(num) - 1
        while i >= 0 and num[i] != '5':
            i -= 1
        if i > 0:
            cnt = n - 1 - i
            j = i - 1
            while j >= 0:
                if num[j] == '2' or num[j] == '7':
                    res = min(res, cnt + i - 1 - j)
                    break
                j -= 1
        cnt = 0
        i = len(num) - 1
        while i >= 0 and num[i] != '0':
            i -= 1
        if i > 0:
            cnt = n - 1 - i
            j = i - 1
            while j >= 0:
                if num[j] == '5' or num[j] == '0':
                    res = min(res, cnt + i - 1 - j)
                    break
                j -= 1

        return res

Explain

该题解的基本思路是找到构成可以被25整除的数字的最少删除操作数。考虑到一个数字如果以00, 25, 50, 75结尾则可以被25整除。算法首先检查是否存在单个0，如果存在，则可以通过删除所有其他数字使其为0，这是删除最少的情况之一。然后，分别检查以5和0结尾的情况。对于以5结尾的情况，向前搜索直到找到2或7，对于以0结尾的情况，向前搜索直到找到另一个0或5。这样可以保证找到的数字是以25, 50, 75, 00结尾的。最后返回所有情况中删除数目最少的结果。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minimumOperations(self, num: str) -> int:
        n = len(num) # 字符串长度
        res = n # 初始化结果为n，即删除所有数字的最大操作数
        cnt = 0 # 辅助变量，用于计算删除的数字个数
        if num.find('0') >= 0: # 如果找到'0'，则可以将结果设置为n-1（因为至少留一个0）
            res = n - 1
        i = len(num) - 1
        while i >= 0 and num[i] != '5': # 从后向前找到第一个'5'
            i -= 1
        if i > 0: # 如果找到了'5'且不是最前面的数字
            cnt = n - 1 - i # 从'5'后面到末尾的数字都可以删除
            j = i - 1 # 从'5'前一个位置开始向前搜索
            while j >= 0: # 查找'2'或'7'
                if num[j] == '2' or num[j] == '7':
                    res = min(res, cnt + i - 1 - j) # 更新最小删除次数
                    break
                j -= 1
        cnt = 0 # 重置计数器
        i = len(num) - 1
        while i >= 0 and num[i] != '0': # 从后向前找到第一个'0'
            i -= 1
        if i > 0: # 如果找到了'0'且不是最前面的数字
            cnt = n - 1 - i # 从'0'后面到末尾的数字都可以删除
            j = i - 1 # 从'0'前一个位置开始向前搜索
            while j >= 0: # 查找另一个'0'或'5'
                if num[j] == '5' or num[j] == '0':
                    res = min(res, cnt + i - 1 - j) # 更新最小删除次数
                    break
                j -= 1

        return res # 返回最小删除次数

Explore

这种情况考虑的是最简单直接的解法。因为如果一个数字可以简单地通过删除其他所有数字只留下一个'0'，那么这个数字就能被25整除（因为0是25的倍数）。这种方法通常会涉及最少的删除操作，因为只需要保留一个字符，所以算法首先尝试这种简便的方式。

如果在字符串中以'5'结尾后向前搜索并未找到'2'或'7'，则这种情况下，以25或75结尾的组合不可能形成，算法将不会考虑以'5'结尾的数作为一个有效的结尾组合。在这种情况下，算法会继续探索其他可能的组合（如以'00', '50'结尾的情况）。

如果'5'或'0'位于字符串的最开始（即索引为0的位置），那么它前面没有其他数字可以形成有效的组合（如25, 50, 75）。在这种情况下，算法不会考虑这样的'5'或'0'作为有效的结尾组合。算法需要至少一个在'5'或'0'前面的数字来形成一个可以被25整除的两位数。

是的，如果原字符串只包含一个'0'，这实际上是最理想的情况之一，因为不需要进行任何删除操作。算法中提到的将所有其他数删除只留下一个'0'的操作是为了处理包含多个数字的情况，但如果字符串本来就只有一个'0'，则不需要任何删除，直接返回0即可。