Leetcode-第161场周赛

1247. 交换字符使得字符串相同

解法：数学

签到题变成了数学题，写了20分钟。。

思路：

1.记录两个字符串总共的x和y字符，若出现奇数次直接返回-1

2.记录两个字符串对应位置不相同时，s1出现x的次数和出现y的次数，若x为奇次，交换次数为(x+y)/2+1;

若x为偶数交换次数为(x+y)/2;

原因:

例1：

s1=x y y x

s2=y x x y

交换 s1[1]和s2[2] ,s1[0]和s2[3]

得到y x y x

​ y x y x

例2:

s1=x y x y x y

s2=y x y x y x

-交换s1[0]和s2[2] ,s1[1]和s2[3] ,s1[4]和s2[4] 然后交换s1[4]和s2[5]

class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int n=s1.size();
        int x=0,y=0;
        int x1=0,y1=0;
        for(int i=0;i<n;i++)
        {
            if(s1[i]!=s2[i])
            {
                if(s1[i]=='x')
                    x++;
                else y++;
                x1++;y1++;
            }
            else
            {
                if(s1[i]=='x')
                    x1+=2;
                else y1+=2;
            }
        }
        if(x1%2||y1%2)
            return -1;
        int res=0;
        if(x%2)
        {
            res=(x+y)/2+1;
        }
        else res=(x+y)/2;
        return res;
    }
};

1248. 统计「优美子数组」

解法1：滑动窗口

思路：

1.记录每一个奇数在数组中的位置

2.遍历这个奇数所在位置数组v，从0到v.size()-k+1进行遍历，记录i,j=i+k-1即正好包含k个奇数的最小子数组的左右边界，然后通过i位置找到与前一奇数（或头部）所在位置中间的距离*j位置与后一奇数（或尾部）所在位置中间的距离，便得到了窗口在这个左右边界时能组成的优美子数组。将所有情况累加得到res

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int> v;
        for(int i=0;i<n;i++)
        {
            if(nums[i]%2)
                v.push_back(i);
        }
        if(v.size()<k)
            return 0;
        int size=v.size(),res=0;
        for(int i=0;i<size-k+1;i++)
        {
            int j=i+k-1;
            int l=i==0?v[i]+1:v[i]-v[i-1];
            int r=j==(size-1)?(n-v[j]):(v[j+1]-v[j]);
            res+=l*r;
        }
        return res;
    }
};

解法2：前缀数组

参考二哥的思路

思路：前缀和，把数组中所有奇数都变成 1，所有偶数变成 0，于是原数组中区间中奇数的个数就等于变换后数组中区间和用一个 map 统计前缀和等于 s 的个数，就可以统计区间和等于 k 的个数了。

sum[s]表示第s个奇数与第s+1个奇数间的距离

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int s = 0;
        map<int,int> sum;
        sum[s] ++;
        int ret = 0;
        for (int i = 0;i < nums.size();i++) {
            if (nums[i] % 2 == 1) {
                s++;
            }
            if (s - k >= 0) {
                ret += sum[s - k];
            }
            sum[s]++;
        }
        return ret;
    }
};

1249. 移除无效的括号

解法：栈

思路：

创建bool used数组，记录字符串中那些位置括号应删掉

1.用栈记录所有的右括号位置，扫描字符串，遇到’(‘,’)’时判断

1）若遇到’(‘将该位置添加进栈

2)若遇到’)’

•  若栈空，将该位置used[i]=true
  

• ​ 若栈不空，将栈顶元素出栈

2.扫描完毕，将栈中剩余元素对应的used值都设为true

3.再次扫描字符串，将对应used位置的字符都跳过即得到了目标字符串

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> st;
        int n=s.size();
        vector<bool> used(n,false);
        for(int i=0;i<n;i++)
        {
            if(s[i]=='(')
            {
                st.push(i);
            }
            else if(s[i]==')')
            {
                if(!st.empty())
                    st.pop();
                else used[i]=true;
            }
        }
        while(!st.empty())
        {
            used[st.top()]=true;
            st.pop();
        }
        string res="";
        for(int i=0;i<n;i++)
        {
            if(used[i])
                continue;
            res+=s[i];
        }
        return res;
    }
};

1250. 检查「好数组」

解法：数学

又是数学题。。经过二哥指点明白了，若数组的最大公因子为1，则为true，否则为false

定理链接：裴蜀定理

class Solution {
public:
    bool isGoodArray(vector<int>& nums) {
        int g=nums[0];
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            g=gcd(g,nums[i]);
        }
        return g==1;
    }
    int gcd(int a,int b)
    {
        if(a<b) return gcd(b,a);
        int r;
        while(b)
        {
            r=a%b;
            a=b;
            b=r;
        }
        return a;
    }
};