如今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大概算法也就出来了；spa

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.数学，没有数学背景，第四题就不会作吧，就像那个爬楼梯那道题，我就不知道他这是，斐波那契数列。。。。

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