欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 明星 > LeetCode 2844.生成特殊数字的最少操作(哈希表 + 贪心)

LeetCode 2844.生成特殊数字的最少操作(哈希表 + 贪心)

2025/8/2 11:19:13 来源:https://blog.csdn.net/AuRoRamth/article/details/140686515  浏览:    关键词:LeetCode 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 不含任何前导零

今天的力扣每日一题比较有意思,这个题的话还是需要有一些编程思维或者说数学思维才能想到的(应该需要每天自己推理实践日积月累),当然这个题如果在比赛中的话不算难题,顶多是:> 签到题  && <= 中档题,好了来一起看看吧

首先呢阅览一遍题目后我们可以发现的是,如果num中包含了一个'0',那么ans最多是n - 1(n是num长度),因为呢除了这个'0'其他全删了么

在来观察,被25整除,思考思考,你会发现25 * (1 ~ n)中的数他的后两位尾数是{25,50,75,00},只要能发现这个规律,那这道题也就结束了,当然想不到也没关系,慢慢积累

那接下来就是两个指针i和j去遍历就行了,把{25,50,75,00}存到哈希表里面,如果key = num[i] + num[j]在哈希表里面找到了,就去更新一次ans的值

代码:

class Solution {
public:int minimumOperations(string num) {int n = num.size(),ans = 0x3f3f3f3f,flag = 0;if(n == 1 && num[0] != '0') return 1;else if(n == 1 && num[0] == '0') return 0;unordered_map<string,int> hs;hs["00"] = 1,hs["25"] = 1,hs["50"] = 1,hs["75"] = 1;if(num.find('0') != string::npos) ans = min(ans,n - 1),flag = 1;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){string key = to_string(num[i] - '0') + to_string(num[j] - '0');// cout << key << endl;if(hs.count(key)){// cout << key << endl;ans = min(ans,n - i - 2);flag = 1;}}}if(!flag) ans = n;return ans;}
};

这个地方解释一个,像哈希表或者set之类用find函数一般找不到都是返回最后的那个空指针也就是.end(),在字符串中如果find函数没找到的话是返回string::npos的,也就是-1,代表找不到

加油

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词