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

---

解题分析及思路：

方法：贪心

思路：

在所有的数字当中，存在五种情况能够被25整除：

• 第一种，尾缀为25的数字
• 第二种，尾缀为50的数字
• 第三种，尾缀为75的数字
• 第四种，尾缀为00的数字
• 第五种，数字0

如果一个数字通过删除某些数字后否和以上五种情况，那么这个数字一定能够被25整除。

贪心策略：

在以上五种情况中，除第五种，其他的情况数字尾缀都是0或者5，所以从尾部开始往前遍历，可以几下遍历过程中的所有数字：0的个数、5的个数、其他的个数

• 若符合第一种情况，当前遍历的数字为2，并且之前出现过5这个数字，则当前数字可以被25整除，返回 0的个数 + 5的个数 - 1 + 其他的个数（结果消耗了之前的一个5）
• 若符合第二种情况，当前遍历的数字为5，并且之前出现过0这个数字，则当前数字可以被25整除，返回 0的个数 - 1 + 5的个数 + 其他的个数（结果消耗了之前的一个0）
• 若符合第三种情况，当前遍历的数字为7，并且之前出现过5这个数字，则当前数字可以被25整除，返回 0的个数 + 5的个数 - 1 + 其他的个数（结果消耗了之前的一个5）
• 若符合第四种情况，当前遍历的数字为0，并且之前出现过0这个数字，则当前数字可以被25整除，返回 0的个数 - 1 + 5的个数 + 其他的个数（结果消耗了之前的一个0）

最后遍历完成未符合情况，则会有两种情况可以变成 让数字变成 0：

• 若之前出现过0，则返回 0 的个数 - 1 + 5的个数 + 其他的个数，只需要删掉除这个 0 外的所有数字
• 若之前没有出现过0，则返回 0 的个数 + 5的个数 + 其他的个数（这个字符串的所有数字）

func minimumOperations(num string) int {
	var zeroCount, fiveCount, otherCount int
	for i := len(num) - 1; i >= 0; i-- {
		switch num[i] {
		case '0':
			if zeroCount > 0 {
				return zeroCount - 1 + fiveCount + otherCount
			}
			zeroCount++
		case '5':
			if zeroCount > 0 {
				return zeroCount - 1 + fiveCount + otherCount
			}
			fiveCount++
		case '2', '7':
			if fiveCount > 0 {
				return zeroCount + fiveCount - 1 + otherCount
			}
			otherCount++
		default:
			otherCount++
		}
	}
	if zeroCount > 0 {
		return zeroCount - 1 + fiveCount + otherCount
	}
	return zeroCount + fiveCount + otherCount
}

复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:3 ms,击败了17.65% 的Go用户
• 内存消耗:2.2 MB,击败了100.00% 的Go用户