现在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.数学，没有数学背景，第四题就不会做吧，就像那个爬楼梯那道题，我就不知道他这是，斐波那契数列。。。。
抓紧时间多练练吧~下周继续努力~/
京公网安备 11010502036488号