生成特殊数字的最少操作

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

难度：中等

给你一个下标从 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 不含任何前导零

这道题需要先观察之后才比较好做，需要发现后缀为00，25，50，75可以整除，然后用贪心就比较简单了。

/**
 * @param {string} num
 * @return {number}
 */
var minimumOperations = function(num) {
    // 后缀为00，25，50，75可以整除
    // 删除最后的数字，直到出现0或者5
    // 再删除倒数第一位，如果最后一位是0，则倒数第一位可以是0或者5；如果最后一位是5，则倒数第一位可以是5或7
    // 若出现多个0和5需要记录每一位最后整除需要删除得个数，取最小值
    // 如果删除的个数大于等于最小值了，则直接返回最小值

    // 优化：
    // 后缀为00，25，50，75可以整除
    // 从后往前找0或者5，找到之后记录后面删除的个数，再往前找，找到能组成00，25，50，75即可，记录中间删除的个数
          
    const len = num.length
    let m = len
    for(let i = len - 1; i >= 0; i--) {
        const c = num[i]
        if(c == '0' || c == '5') {
            let t = len - i - 1
            let flag = false
            for(let j = i-1; j >= 0; j--) {
                const cc = num[j]
                if(c == '0' && (cc == '0' || cc == '5')) {
                    flag = true
                    break
                } else if (c == '5' && (cc == '2' || cc == '7')) {
                    flag = true
                    break
                } else {
                    t++
                }
            }
            if (flag || (!flag && c == '0')) {
                m = Math.min(m, t)
            }
        }
    }
    return m;
};