2844. 生成特殊數(shù)字的最少操作

給你一個(gè)下標(biāo)從 0 開(kāi)始的字符串 num ，表示一個(gè)非負(fù)整數(shù)。

在一次操作中，您可以選擇 num 的任意一位數(shù)字并將其刪除。請(qǐng)注意，如果你刪除 num 中的所有數(shù)字，則 num 變?yōu)?0。

返回最少需要多少次操作可以使 num 變成特殊數(shù)字。

如果整數(shù) x 能被 25 整除，則該整數(shù) x 被認(rèn)為是特殊數(shù)字。

示例 1：

輸入：num = "2245047"
輸出：2
解釋?zhuān)簞h除數(shù)字 num[5] 和 num[6] ，得到數(shù)字 "22450" ，可以被 25 整除。
可以證明要使數(shù)字變成特殊數(shù)字，最少需要?jiǎng)h除 2 位數(shù)字。
示例 2：

輸入：num = "2908305"
輸出：3
解釋?zhuān)簞h除 num[3]、num[4] 和 num[6] ，得到數(shù)字 "2900" ，可以被 25 整除。
可以證明要使數(shù)字變成特殊數(shù)字，最少需要?jiǎng)h除 3 位數(shù)字。
示例 3：

輸入：num = "10"
輸出：1
解釋?zhuān)簞h除 num[0] ，得到數(shù)字 "0" ，可以被 25 整除。
可以證明要使數(shù)字變成特殊數(shù)字，最少需要?jiǎng)h除 1 位數(shù)字。

提示

1 <= num.length <= 100
num 僅由數(shù)字 '0' 到 '9' 組成
num 不含任何前導(dǎo)零

解題思路：

見(jiàn)代碼注釋

code

class Solution {
public:
    //能被25整除的整數(shù)的規(guī)律
    //0 25 50 75 100 125 150 175 200....
    //可以看到能被25整除的數(shù)最后兩位都是00,25,50,75
    //那么最后兩位是00,25,50,75就一定能夠被25整除嗎？
    //x = 100k + 00
    //x = 100k + 25
    //x = 100k + 50
    //x = 100k + 75
    //也就是最后兩位是以上四種組合一定能夠被25整除并且能被25整除的整數(shù)最后兩位也是以上四種組合
    //找到得到最后兩位都是以上四種組合的最小刪除次數(shù)
    //00:從后向前查找，分別找到兩個(gè)零的idx
    //25:從后向前查找，分別找到二和五的idx
    //50:從后向前查找，分別找到五和零的idx
    //75:從后向前查找，分別找到七和五的idx
    
    //刪除全部結(jié)果為0，也就是最后一定會(huì)有一個(gè)結(jié)果：len(num)
    //并且從10上來(lái)看，如果存在一個(gè)零的話，那么最后并不用全部刪除，只需要?jiǎng)h除到只剩一個(gè)零即可，也就是len(num-1)
    
    //min函數(shù)語(yǔ)法學(xué)習(xí)
    //min<datatype>({several datas more than two})

    int match(string & num,string sub)
    {
        int len = num.size();

        int idx1 = num.rfind(sub[1]);
        if(idx1 == -1 || idx1 == 0) return len;
        int idx2 = num.rfind(sub[0],idx1 - 1);
        if(idx2 == -1) return len;

        return len - idx2 - 2;
    }
    int minimumOperations(string num) {
        int len = num.size();
        int ans = len;

        if(num.find('0') != -1) ans = len - 1;
        
        //cout<<match(num,"25")<<endl;
        return min({ans,match(num,"00"),match(num,"25"),match(num,"50"),match(num,"75")});

    }
};