LeetCode 25双周赛
程序员文章站
2022-07-12 12:08:49
...
2
https://leetcode-cn.com/problems/max-difference-you-can-get-from-changing-an-integer/
- 这题数据量很小,一共也就8个数字(8位数),其实不用贪心(贪心要讨论很多情况),直接暴力枚举就可以了,a和b分别从0枚举至9,然后扫一下每位数字,只要等于a的全换成b。
- 然后时时更新max和min就好了,注意讨论一下前导0的问题:即目前扫到开头那位,且换成了0的时候。
class Solution {
public:
int maxDiff(int num) {
int ans=0,top=0;
int dig[9];
int v=num;
while(v){
dig[top++]=v%10;
v/=10;
}
int mx=num,mi=num;
for(int a=0;a<10;a++){
for(int b=0;b<10;b++){
int target=0;
for(int i=top-1;i>=0;i--){
int cur = dig[i];
if(cur == a) cur = b; //全部的a换成b
if(i == top-1 && cur==0){break;} //除去前导0的情况
target = target*10 + cur;
}
if(target == 0)continue; //除去结果是0的情况
mi=min(mi,target);
mx=max(mx,target);
}
}
return mx-mi;
}
};
3
https://leetcode-cn.com/problems/check-if-a-string-can-break-another-string/
- 如果想s1打破s2,可以选择贪心算法:拿s1中最小的char去压s2中最小的char,以便给s1留更多大的char去压s2的对应位置的字符。
- 反证法:如果s1中最小的char都压不了s2中的最小的,那么肯定打不破。
class Solution {
public:
bool checkIfCanBreak(string s1, string s2) {
sort(s1.begin(),s1.end());
sort(s2.begin(),s2.end());
//s1最小如果连s2最小的都压不过,那s1肯定打不破s2
int n = s1.size();
bool flag = true;
for(int i = 0;i < n;++i){
if(s1[i] < s2[i]){
flag = false; break;
}
}
if(flag) return true;
flag = true;
for(int i = 0;i < n;++i){
if(s1[i] > s2[i]){
flag = false; break;
}
}
if(flag) return true;
return false;
}
};
上一篇: 动态规划--左上角到右下角的最大收益问题
下一篇: LeetCode 第17双周赛