目录
2844. 生成特殊数字的最少操作
题目描述:
实现代码与解析:
贪心
原理思路:
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
不含任何前导零
实现代码与解析:
贪心
class Solution {public int minimumOperations(String num) {int res = 0;// 00 25 50 75char[] cs = num.toCharArray();int n = cs.length;boolean pre0 = false;boolean pre5 = false;int cnt0 = 0;for (int i = n - 1; i >= 0; i--) {if (cs[i] == '0') {if (pre0) return n - i - 2;pre0 = true;cnt0++;}if (cs[i] == '2') {if (pre5) return n - i - 2;}if (cs[i] == '5') {if (pre0) return n - i - 2;pre5 = true;}if (cs[i] == '7') {if (pre5) return n - i - 2;}}return n - cnt0;}
}
原理思路:
究极大贪心,能被25整除就那么几种情况,后缀为00, 25, 50, 75的,所以从后向前遍历,判断那种情况先达成即可。
注意都不达成时,最后就只能为0,返回长度- 0的个数就是要去除的res。