JZX轻语：简

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

发表于2024年07月25日

#字符串 #贪心

类似于5的倍数，25的倍数中，后缀永远是00，25，50以及75，反之依然(即当且仅当满足上述后缀的数，可以被25整除)。因此，我们可以使用贪心的做法，从后往前找到包含上述任一后缀顺序(具体而言，以25为例，如果该子串包含2和5，且2在5的前面)的最短后缀子串suffix，然后需要删除的字符数即为len(suffix) - 2。

# 25, 50, 75, 00
class Solution:
    def minimumOperations(self, num: str) -> int:
        n = len(num)
        find0 = find5 = False  # 用于标记是否已经找到了一个0或5
        for i in range(n - 1, -1, -1):
            if num[i] in ('0', '5'):
                if find0:  # 最快找到00或50
                    return n - i - 2
                if num[i] == '0':
                    find0 = True
                else:
                    find5 = True
            elif num[i] in ('2', '7') and find5:  # 最快找到25或75
                return n - i - 2
        return n - 1 if find0 else n

闪念标签：LC

题目链接：https://leetcode.cn/problems/minimum-operations-to-make-a-special-number/