😃 2844.生成特殊数字的最少操作
给你一个下标从 0 开始的字符串 num ，表示一个非负整数。
在一次操作中，您可以选择 num 的任意一位数字并将其删除。请注意，如果你删除 num 中的所有数字，则 num 变为 0。
返回最少需要多少次操作可以使 num 变成特殊数字。
如果整数 x 能被 25 整除，则该整数 x 被认为是特殊数字。
思路
基本思想
看到题目第一想法就是将当前数变成至少有两个5的因子相乘的数，这样才能使得被25整除，或者说要有25的因子才可以，满足要求的数有以下五种情况：
- 结尾为00
- 结尾为25
- 结尾为50
- 结尾为75
- 本身是0
对于第五种很好理解，第一种是该数有100这个因子，而100又是25的倍数，故以00结尾的数是25的倍数，其余三种举例来说，例如9925可拆成9900+25，而9900有100的因子，转换成情况1，而25本身就是25的倍数
问题转换成如何将数转换成以上5种情况步数最少，现在有两种解法：
解法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
int ans;
public int minimumOperations(String num) {
ans=num.length();
if(num.contains("0"))
ans=ans-1;
index(num,"25");
index(num,"50");
index(num,"75");
index(num,"00");
return ans;
}
//找到指定尾部元素的位置
public void index(String num,String tail){
int i=num.lastIndexOf(tail.charAt(1));
if(i<0)
return;
i=num.lastIndexOf(tail.charAt(0),i-1);
if(i<0)
return;
ans=Math.min(ans,num.length()-i-2);
}
}
|
这种解法就是排除为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
| class Solution {
//从末尾开始找25,50,75,00
//谁先找到说明谁删除的少，此时直接返回
public int minimumOperations(String num) {
if(num=="0")
return 0;
int first0=-1,first5=-1;
for(int i=num.length()-1;i>=0;--i){
if(num.charAt(i)=='0'||num.charAt(i)=='5'){
//找到一个0或者5，并且第一个0也找到了，说明找到了00或者50
//先找到就先返回
if(first0!=-1){
return num.length()-i-2;
}
//到这里说明找到的是第一个0或者5，此时标记第一个0已经找到
if(num.charAt(i)=='0')
first0=i;
else
first5=i;
}
else if(num.charAt(i)=='2'||num.charAt(i)=='7'){
//找到2或者7，并且第一个5也找到了
if(first5!=-1){
return num.length()-i-2;
}
}
}
//到这里都没返回，说明没有构成25,50,75,00
//此时判断有没有0
return first0==-1?num.length():num.length()-1;
}
}
|
这种情况就是先出现哪种情况就直接返回，只需要统计一次，更加巧妙，从末尾开始向前查找，一旦出现第一个0并且后面又遇到了5或者0，此时就可以组成50或者00，由于是从后向前，所以遇到了就是最短路径直接返回
一旦出现第一个5并且后面又遇到了2或者7，此时也可以返回结果，遍历结束都没返回，说明形成不了00,25,50,75中的任何一种，此时判断内部到底有没有单独的0，有的话节省一步，否则全部删除才能获得0
总结
主要就是要知道题中所求特殊的数的性质，结尾必须是00,25,50,75或者本身就是0的这种性质，知道这个性质就比较好求出答案了