欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
    }
};