生成特殊数字的最少操作

2024/7/25 力扣每日一题贪心

题目链接: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 不含任何前导零
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

这道题需要先观察之后才比较好做,需要发现后缀为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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Last Updated: 2024/10/7 15:51:07