【LeetCode第 161 场周赛】回顾

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/shiliang97/article/details/102881733

现在13点33分花半个小时总结一下上午的考题~

评论区偷来的解析

交换字符使得字符串相同： 统计位置的匹配情况，一共只有4种可能，x-xx−x,x-yx−y,y-xy−x,y-yy−y，其中1和4是相同的情况，可以不管。我们统计两个字符串有多少对x-yx−y 以及 y-xy−x。 然后，我们可以根据匹配情况的统计进行贪心，如果我们同时有两对 x-yx−y 或者 y-xy−x，是可以通过一次交换使这两对相同的，最后会剩下只有一对不相同，这种情况是 -1−1；或者各有一对不相同，这时我们需要用两次操作将他们变成一样。总体时间复杂度为O(n)O(n)。 统计「优美子数组」： 遍历数组，记录从 00 位置到当前位置的奇数数量。我们用一个dict来记录历史的数量的总和，然后对于每个位置，如果我们知道到这个位置有 xx 个奇数，那么只需要去dict里查 x-kx−k 个奇数的数量就是以当前位置结尾的子数组数量了。总体时间复杂度为O(n)O(n)。 移除无效的括号： 经典的合法括号序列问题，只是这题需要我们记录方案。 还是用一个栈维护括号状态，对于左括号，入栈，对于右括号，如果栈中有左括号，左括号出栈，否则右括号不记入答案。 最后再把左括号栈中剩余的左括号从答案中删除就可以了，总体时间复杂度O(n)O(n)。 检查「好数组」： 唯一的结论是如果数组中所有数的最大公约数为 11，则存在解，否则不存在。所以只需要计算所有数最大公约数即可，时间复杂度O(nlog(m))O(nlog(m))，其中 mm 为数字大小。

第一题交换字符串

我第一题交换字符使得字符串相同，上来就看蒙了，也不知道这是干啥呢。。读了半天题，转到了第二题开始看看，A的时候已经四十分钟了。。。

回过头来继续看第一题，大概懂了就是，只看不同的部分，相同的部分就不用管了。

换位置的时候前面都是直接两两交换，如 XX 和YY直接一步换成XY和XY，XY和YX要先换成XX和YY再换XY和XY，要两步，所以情况里面，只要能凑出XX的情况都是一步，只看最后剩下的俩是XX还是XY，如果是XY就步数加一就行了~

考虑特殊情况，就是长度不一，或者不同的位数个数是奇数没法换，返回-1就行了

class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int num=0;
        int yi=0;
        for(int i=0;i<s1.size();i++){
            if(s1[i]!=s2[i]){
                num++;
                if(s1[i]=='y'){
                    yi++;
                }
            }
        }
        if(num==0){
            return 0;
        }
        if(num%2==1){
            return -1;
        }
        if(yi%2==1){
            return num/2+1;
        }return num/2;
    }
};

统计「优美子数组」

这个竟然是第一个做上来的题，当然这道题对于别人来说也是简单的狠。。。

只要找到奇数的位置，凑够K个，然后两边扩展组合就行了，比如测试样例3，左边3个偶数，右边3个偶数，组合个数就是（3+1）*（3+1）=16；so大概算法也就出来了；

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        vector<int>ji;
        for(int i=0;i<nums.size();i++){
            if(nums[i]%2==1){
                ji.push_back(i);
            }
        }
        if(ji.size()<k){
            return 0;
        }
        int sum=0;
        int l=0;
        for(int i=k-1;i<ji.size();i++,l++){
            int a=0,b=0;
            if(l==0){
                a=ji[0]+1;
            }else{
                a=ji[l]-ji[l-1];
            }
            if(i==ji.size()-1){
                b=nums.size()-ji[i];
            }else{
                b=ji[i+1]-ji[i];
            }
            sum+=a*b;
        }
        
        return sum;
    }
};

然后是没有A的第三题和第四题，

第三题我的写法有问题，第三题看着挺简单的，可我的方法。大数据就抄内存了。。。

第四题不太懂，为啥是找公约数就行了。。。虽然这么想过，但是很难懂这个是什么原理~。

考试出的问题很明显就是

1.读题，自己看半天读不懂第一题~

2.语法，自己还是敲得少，所以第二道题语法写的时候各种编译错误，多练就行了感觉~，

3.优化，第三题大概知道，就是自己不会用语言表达，不能过大数据，说明自己知识水平存在欠缺。

4.数学，没有数学背景，第四题就不会做吧，就像那个爬楼梯那道题，我就不知道他这是，斐波那契数列。。。。

抓紧时间多练练吧~下周继续努力~/