生成特殊数字的最少操作

You are given a 0-indexed string num representing a non-negative integer.

In one operation, you can pick any digit of num and delete it. Note that if you delete all the digits of num, num becomes 0.

Return the minimum number of operations required to make num special.

An integer x is considered special if it is divisible by 25.

 

Example 1:

Input: num = "2245047"
Output: 2
Explanation: Delete digits num[5] and num[6]. The resulting number is "22450" which is special since it is divisible by 25.
It can be shown that 2 is the minimum number of operations required to get a special number.

Example 2:

Input: num = "2908305"
Output: 3
Explanation: Delete digits num[3], num[4], and num[6]. The resulting number is "2900" which is special since it is divisible by 25.
It can be shown that 3 is the minimum number of operations required to get a special number.

Example 3:

Input: num = "10"
Output: 1
Explanation: Delete digit num[0]. The resulting number is "0" which is special since it is divisible by 25.
It can be shown that 1 is the minimum number of operations required to get a special number.

 

Constraints:

• 1 <= num.length <= 100
• num only consists of digits '0' through '9'.
• num does not contain any leading zeros.

/*
 * 思路：
 * 1. 使用Java Stream来简化组合的生成。
 * 2. 枚举所有可能的数字组合并检查能否被25整除。
 * 3. 找到组合所需的最小删除次数。
 */
import java.util.stream.IntStream;

public class SpecialNumberStream {
    public int minDeletions(String num) {
        int n = num.length();
        return IntStream.range(0, n)
                .flatMap(i -> IntStream.range(i + 1, n)
                        .map(j -> {
                            String subNum = num.substring(0, i) + num.substring(i + 1, j) + num.substring(j + 1);
                            return subNum.length() > 0 && Integer.parseInt(subNum) % 25 == 0 ? 2 : n;
                        }))
                .min().orElse(n);
    }

    public static void main(String[] args) {
        SpecialNumberStream sn = new SpecialNumberStream();
        System.out.println(sn.minDeletions("2245047")); // 输出 2
        System.out.println(sn.minDeletions("2908305")); // 输出 3
        System.out.println(sn.minDeletions("10")); // 输出 1
    }
}

该题解的基本思路是找到构成可以被25整除的数字的最少删除操作数。考虑到一个数字如果以00, 25, 50, 75结尾则可以被25整除。算法首先检查是否存在单个0，如果存在，则可以通过删除所有其他数字使其为0，这是删除最少的情况之一。然后，分别检查以5和0结尾的情况。对于以5结尾的情况，向前搜索直到找到2或7，对于以0结尾的情况，向前搜索直到找到另一个0或5。这样可以保证找到的数字是以25, 50, 75, 00结尾的。最后返回所有情况中删除数目最少的结果。

O(n)

O(1)