讨论/题目交流/🏆 第 161 场力扣周赛/
🏆 第 161 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

4 分 - 交换字符使得字符串相同
4 分 - 统计「优美子数组」
5 分 - 移除无效的括号
6 分 - 检查「好数组」

展开讨论

第一题:

数学题,统计两个字符串相同位置的对比,x->x 和 y->y 不需要处理,忽略

如果出现两个 x->y,或者出现两个 y->x,他们可以转移一次x 和 y 就可以消掉

最后再判断是否剩下一个 x->y 和一个 y->x,这俩需要转移两次,见 样例 2

至于 -1 的情况,只需要判断是否只剩下一个 x->y 或者只剩下y->x

class Solution {
public:
    int minimumSwap(string s1, string s2) {  
        int a1 = 0;//x -> y
        int a2 = 0;//y -> x
        
        for (int i = 0;i < s1.size();i++) {
            if (s1[i] == 'x' && s2[i] == 'y') {
                a1++;
            }
            if (s1[i] == 'y' && s2[i] == 'x') {
                a2++;
            }
        }
                
        if (a1 % 2 + a2 % 2 == 1) {
            return -1;
        }
        
        int ret = a1 / 2 + a2 / 2;
        if (a1 % 2 == 1) {
            ret += 2;
        }
        return ret;
    }
};

第二题:

前缀和,把数组中所有奇数都变成 11,所有偶数变成 00,于是原数组中区间中奇数的个数就等于变换后数组中区间和

用一个 mapmap 统计前缀和等于 ss 的个数,就可以统计区间和等于 kk 的个数了

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

第三题:

栈,首先把整个括号拿出来匹配,如果当前位置是 ((,下标入栈,如果当前位置是 )),从栈中弹出一个 (( 的下标配对,标记这两个括号的位置都应该保留,注意栈有可能是空的。那些没标记的括号就是要删除的,其他非括号的字母直接保留

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> S;
        vector<bool> flag(s.size(), false);
        for (int i = 0;i < s.size();i++) {
            if (s[i] == '(') {
                S.push(i);
            } else if (s[i] == ')') {
                if (S.empty()) {
                    continue;
                }
                flag[i] = true;
                flag[S.top()] = true;
                S.pop();
            } else {
                
            }
        }
        string ret = "";
        for (int i = 0;i < s.size();i++) {
            if (s[i] == '(' || s[i] == ')') {
                if (flag[i]) {
                    ret.push_back(s[i]);
                }
            } else {
                ret.push_back(s[i]);
            }
        }
        return ret;
    }
};

第四题:

a1x1+a2x2+...+anxn=ka_{1}*x_{1}+a_{2}*x_{2}+...+a_{n}*x_{n}=k 有解的充要条件是:
gcd(a1+a2+...+an)kgcd(a_{1}+a_{2}+...+a_{n}) | k

贴个定理链接:https://baike.baidu.com/item/裴蜀定理/5186593

因此我们只需要计算数组所有数的最大公约数是否等于1即可

class Solution {
public:
    int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
    bool isGoodArray(vector<int>& nums) {
        int d = nums[0];
        for (int i = 1;i < nums.size();i++) {
            d = gcd(d, nums[i]);
        }
        return d == 1;
    }
};
34
展开全部 25 讨论