跳转至

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 位数字。

 

提示

  • 1 <= num.length <= 100
  • num 仅由数字 '0' 到 '9' 组成
  • num 不含任何前导零

解法

方法一：记忆化搜索

我们注意到，整数 \(x\) 要能被 \(25\) 整除，即 \(x \bmod 25 = 0\)。因此，我们可以设计一个函数 \(dfs(i, k)\)，表示从字符串 \(num\) 的第 \(i\) 位开始，且当前数字模 \(25\) 的结果为 \(k\) 的情况下，要使得数字变成特殊数字，最少需要删除多少位数字。那么答案为 \(dfs(0, 0)\)。

函数 \(dfs(i, k)\) 的执行逻辑如下：

  • 如果 \(i = n\)，即已经处理完字符串 \(num\) 的所有位，那么如果 \(k = 0\)，则当前数字可以被 \(25\) 整除，返回 \(0\)，否则返回 \(n\)；
  • 否则，第 \(i\) 位可以被删除，此时需要删除一位，即 \(dfs(i + 1, k) + 1\)；第 \(i\) 位不删除，那么 \(k\) 的值变为 \((k \times 10 + \textit{num}[i]) \bmod 25\)，即 \(dfs(i + 1, (k \times 10 + \textit{num}[i]) \bmod 25)\)。取这两者的最小值即可。

为了防止重复计算，我们可以使用记忆化的方法优化时间复杂度。

时间复杂度 \(O(n \times 25)\)，空间复杂度 \(O(n \times 25)\)。其中 \(n\) 是字符串 \(num\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minimumOperations(self, num: str) -> int:
        @cache
        def dfs(i: int, k: int) -> int:
            if i == n:
                return 0 if k == 0 else n
            ans = dfs(i + 1, k) + 1
            ans = min(ans, dfs(i + 1, (k * 10 + int(num[i])) % 25))
            return ans

        n = len(num)
        return dfs(0, 0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    private Integer[][] f;
    private String num;
    private int n;

    public int minimumOperations(String num) {
        n = num.length();
        this.num = num;
        f = new Integer[n][25];
        return dfs(0, 0);
    }

    private int dfs(int i, int k) {
        if (i == n) {
            return k == 0 ? 0 : n;
        }
        if (f[i][k] != null) {
            return f[i][k];
        }
        f[i][k] = dfs(i + 1, k) + 1;
        f[i][k] = Math.min(f[i][k], dfs(i + 1, (k * 10 + num.charAt(i) - '0') % 25));
        return f[i][k];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minimumOperations(string num) {
        int n = num.size();
        int f[n][25];
        memset(f, -1, sizeof(f));
        auto dfs = [&](this auto&& dfs, int i, int k) -> int {
            if (i == n) {
                return k == 0 ? 0 : n;
            }
            if (f[i][k] != -1) {
                return f[i][k];
            }
            f[i][k] = dfs(i + 1, k) + 1;
            f[i][k] = min(f[i][k], dfs(i + 1, (k * 10 + num[i] - '0') % 25));
            return f[i][k];
        };
        return dfs(0, 0);
    }
};

 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
func minimumOperations(num string) int {
    n := len(num)
    f := make([][25]int, n)
    for i := range f {
        for j := range f[i] {
            f[i][j] = -1
        }
    }
    var dfs func(i, k int) int
    dfs = func(i, k int) int {
        if i == n {
            if k == 0 {
                return 0
            }
            return n
        }
        if f[i][k] != -1 {
            return f[i][k]
        }
        f[i][k] = dfs(i+1, k) + 1
        f[i][k] = min(f[i][k], dfs(i+1, (k*10+int(num[i]-'0'))%25))
        return f[i][k]
    }
    return dfs(0, 0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function minimumOperations(num: string): number {
    const n = num.length;
    const f: number[][] = Array.from({ length: n }, () => Array.from({ length: 25 }, () => -1));
    const dfs = (i: number, k: number): number => {
        if (i === n) {
            return k === 0 ? 0 : n;
        }
        if (f[i][k] !== -1) {
            return f[i][k];
        }
        f[i][k] = dfs(i + 1, k) + 1;
        f[i][k] = Math.min(f[i][k], dfs(i + 1, (k * 10 + Number(num[i])) % 25));
        return f[i][k];
    };
    return dfs(0, 0);
}

 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
impl Solution {
    pub fn minimum_operations(num: String) -> i32 {
        let n = num.len();
        let bytes = num.as_bytes();

        let mut memo = vec![vec![-1; 25]; n];

        fn dfs(
            i: usize,
            k: usize,
            n: usize,
            bytes: &[u8],
            memo: &mut Vec<Vec<i32>>,
        ) -> i32 {
            if i == n {
                return if k == 0 { 0 } else { n as i32 };
            }

            if memo[i][k] != -1 {
                return memo[i][k];
            }

            // delete current digit
            let mut res = dfs(i + 1, k, n, bytes, memo) + 1;

            // keep current digit
            let digit = (bytes[i] - b'0') as usize;
            let nk = (k * 10 + digit) % 25;
            res = res.min(dfs(i + 1, nk, n, bytes, memo));

            memo[i][k] = res;
            res
        }

        dfs(0, 0, n, &bytes, &mut memo)
    }
}

 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
public class Solution {
    private int[,] memo;
    private string num;
    private int n;

    public int MinimumOperations(string num) {
        this.num = num;
        n = num.Length;
        memo = new int[n, 25];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 25; j++) {
                memo[i, j] = -1;
            }
        }

        return Dfs(0, 0);
    }

    private int Dfs(int i, int k) {
        if (i == n) {
            return k == 0 ? 0 : n;
        }

        if (memo[i, k] != -1) {
            return memo[i, k];
        }

        // delete current digit
        int res = Dfs(i + 1, k) + 1;

        // keep current digit
        int digit = num[i] - '0';
        int nk = (k * 10 + digit) % 25;
        res = Math.Min(res, Dfs(i + 1, nk));

        memo[i, k] = res;
        return res;
    }
}

评论