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 不包含前导零

提示：

  • 如果 num 包含单个零位数，则答案最多为 n - 1
  • 如果一个数的最后两位是 75、50、25 或 00，则该数能被 25 整除
  • 遍历所有可能的索引对 i < j，使得 num[i] * 10 + num[j] 在 [00,25,50,75] 中。然后，将答案设置为 min(answer, n - i - 2)

解题思路

解题思路

这道题的核心是理解能被25整除的数字规律：一个数能被25整除，当且仅当它的最后两位数是 00、25、50 或 75。

主要思路

  1. 特殊情况处理：如果原数字就是 “0”，直接返回 0；如果字符串中包含 ‘0’，最坏情况下可以删除所有数字只保留 ‘0’，操作数为 n-1。

  2. 枚举所有可能的结尾：我们需要找到能组成 00、25、50、75 的数字对，使得保留这两个数字作为结尾时，删除的数字最少。

  3. 贪心策略：对于每种可能的结尾组合，我们从右向左找到第一个符合条件的数字对。由于我们要保留的是最后两位，所以越靠右的数字对越好，删除的数字越少。

  4. 计算操作数：如果在位置 i 和 j（i < j）找到了符合条件的数字对，那么操作数就是 n - i - 2，因为我们保留了两个数字。

算法步骤

  1. 预处理特殊情况
  2. 遍历所有可能的数字对 (i, j)，其中 i < j
  3. 检查 num[i] 和 num[j] 组成的两位数是否在 {00, 25, 50, 75} 中
  4. 如果是，计算操作数并更新最小值
  5. 返回最小操作数

代码实现

class Solution {
public:
    int minimumOperations(string num) {
        int n = num.length();
        if (n == 1) return num[0] == '0' ? 0 : 1;
        
        int ans = n; // 最坏情况：删除所有数字变成0
        
        // 如果包含0，最坏情况是n-1（保留一个0）
        for (char c : num) {
            if (c == '0') {
                ans = n - 1;
                break;
            }
        }
        
        // 检查所有可能的两位结尾：00, 25, 50, 75
        vector<string> targets = {"00", "25", "50", "75"};
        
        for (const string& target : targets) {
            for (int i = 0; i < n; i++) {
                if (num[i] == target[0]) {
                    for (int j = i + 1; j < n; j++) {
                        if (num[j] == target[1]) {
                            ans = min(ans, n - i - 2);
                            break;
                        }
                    }
                }
            }
        }
        
        return ans;
    }
};

class Solution:
    def minimumOperations(self, num: str) -> int:
        n = len(num)
        if n == 1:
            return 0 if num[0] == '0' else 1
        
        ans = n  # 最坏情况：删除所有数字变成0
        
        # 如果包含0，最坏情况是n-1（保留一个0）
        if '0' in num:
            ans = n - 1
        
        # 检查所有可能的两位结尾：00, 25, 50, 75
        targets = ["00", "25", "50", "75"]
        
        for target in targets:
            for i in range(n):
                if num[i] == target[0]:
                    for j in range(i + 1, n):
                        if num[j] == target[1]:
                            ans = min(ans, n - i - 2)
                            break
        
        return ans

public class Solution {
    public int MinimumOperations(string num) {
        int n = num.Length;
        if (n == 1) return num[0] == '0' ? 0 : 1;
        
        int ans = n; // 最坏情况：删除所有数字变成0
        
        // 如果包含0，最坏情况是n-1（保留一个0）
        if (num.Contains('0')) {
            ans = n - 1;
        }
        
        // 检查所有可能的两位结尾：00, 25, 50, 75
        string[] targets = {"00", "25", "50", "75"};
        
        foreach (string target in targets) {
            for (int i = 0; i < n; i++) {
                if (num[i] == target[0]) {
                    for (int j = i + 1; j < n; j++) {
                        if (num[j] == target[1]) {
                            ans = Math.Min(ans, n - i - 2);
                            break;
                        }
                    }
                }
            }
        }
        
        return ans;
    }
}

var minimumOperations = function(num) {
    const n = num.length;
    let minOps = n; // worst case: delete all digits to get 0
    
    // Check for endings that make number divisible by 25: 00, 25, 50, 75
    const endings = ['00', '25', '50', '75'];
    
    for (let ending of endings) {
        let lastDigit = ending[1];
        let secondLastDigit = ending[0];
        
        let lastPos = -1;
        let secondLastPos = -1;
        
        // Find positions from right to left
        for (let i = n - 1; i >= 0; i--) {
            if (num[i] === lastDigit && lastPos === -1) {
                lastPos = i;
            } else if (num[i] === secondLastDigit && lastPos !== -1 && secondLastPos === -1) {
                secondLastPos = i;
                break;
            }
        }
        
        if (lastPos !== -1 && secondLastPos !== -1) {
            // Calculate operations: delete everything after lastPos + delete between secondLastPos and lastPos
            let operations = (n - 1 - lastPos) + (lastPos - secondLastPos - 1);
            minOps = Math.min(minOps, operations);
        }
    }
    
    // Special case: if we have at least one '0', we can make the number 0
    if (num.includes('0')) {
        minOps = Math.min(minOps, n - 1);
    }
    
    return minOps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要遍历所有可能的数字对，最坏情况下是O(n²)
空间复杂度O(1)只使用了常数级别的额外空间

相关题目