LeetCode 2844.生成特殊数字的最少操作：模拟（分析）

【LetMeFly】2844.生成特殊数字的最少操作：模拟（分析）

力扣题目链接：https://leetcode.cn/problems/minimum-operations-to-make-a-special-number/

给你一个下标从 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的倍数，那么它要么是$0$，要么以：$00$、$25$、$50$或$75$结尾。

如果要将num变成0，最少需要移除多少个元素呢？

• 如果num中本来就包含数字0，则需要移除len(num) - 1个元素
• 否则，需要将num中的数字全部移除，即需移除len(num)个元素

如果要将num变成以25结尾呢？

首先找到num中最后一个以5结尾的元素的位置（记为i）。

接着在[0, i)范围内找以2结尾的元素的位置。

若都找到，则返回len(num) - i - 2，否则返回len(num)

找以$00$结尾、以$50$或$75$结尾同理。

其中所有的方案中，所需移除元素最少的一个记为所求。

• 时间复杂度$O(len(num))$
• 空间复杂度$O(1)$

AC代码

C++

class Solution { private:     int thisEnd(string& s, int n) {         int i = s.size() - 1;         char finding = n % 10 + '0';         while (i >= 0 && s[i] != finding) {             i--;         }         i--;         finding = n / 10 % 10 + '0';         while (i >= 0 && s[i] != finding) {             i--;         }         return i == -1 ? s.size() : s.size() - i - 2;     } public:     int minimumOperations(string& s) {         int ans = s.find('0') == string::npos ? s.size() : s.size() - 1;         ans = min(ans, min(             thisEnd(s, 0), min(                 thisEnd(s, 25), min(                     thisEnd(s, 50), thisEnd(s, 75)                 )             )         ));         return ans;     } }; 

Java

class Solution {     private int thisEnd(String num, int n) {         char finding = (char)(n % 10 + '0');         int i = num.lastIndexOf(finding);         finding = (char)(n / 10 % 10 + '0');         i = num.lastIndexOf(finding, i - 1);         return i == -1 ? num.length() : num.length() - i - 2;     }      public int minimumOperations(String num) {         int ans = num.indexOf('0') == -1 ? num.length() : num.length() - 1;         ans = Math.min(ans, Math.min(             thisEnd(num, 0), Math.min(                 thisEnd(num, 25), Math.min(                     thisEnd(num, 50), thisEnd(num, 75)                 )             )         ));         return ans;     } } 

Python

class Solution:     def thisEnd(self, num: str, n: int) -> int:         finding = chr(ord('0') + n % 10)         i = num.rfind(finding)         if i == -1:             return len(num)         finding = chr(ord('0') + n // 10 % 10)         i = num.rfind(finding, 0, i)         return len(num) - i - 2 if i != -1 else len(num)          def minimumOperations(self, num: str) -> int:         ans = len(num) if '0' not in num else len(num) - 1         for end in [0, 25, 50, 75]:             ans = min(ans, self.thisEnd(num, end))         return ans  

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/140695211