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

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

image.png

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

展开讨论
共 25 个讨论

第一题:

数学题,统计两个字符串相同位置的对比,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

只有我觉得第一题是最难的吗...

8

惯例占坑,详细题解稍晚来~:

  • 交换字符使得字符串相同
    统计位置的匹配情况,一共只有4种可能,xxx-x,xyx-y,yxy-x,yyy-y,其中1和4是相同的情况,可以不管。我们统计两个字符串有多少对xyx-y 以及 yxy-x
    然后,我们可以根据匹配情况的统计进行贪心,如果我们同时有两对 xyx-y 或者 yxy-x,是可以通过一次交换使这两对相同的,最后会剩下只有一对不相同,这种情况是 1-1;或者各有一对不相同,这时我们需要用两次操作将他们变成一样。总体时间复杂度为O(n)O(n)

  • 统计「优美子数组」
    遍历数组,记录从 00 位置到当前位置的奇数数量。我们用一个dict来记录历史的数量的总和,然后对于每个位置,如果我们知道到这个位置有 xx 个奇数,那么只需要去dict里查 xkx-k 个奇数的数量就是以当前位置结尾的子数组数量了。总体时间复杂度为O(n)O(n)

  • 移除无效的括号
    经典的合法括号序列问题,只是这题需要我们记录方案。
    还是用一个栈维护括号状态,对于左括号,入栈,对于右括号,如果栈中有左括号,左括号出栈,否则右括号不记入答案。
    最后再把左括号栈中剩余的左括号从答案中删除就可以了,总体时间复杂度O(n)O(n)

  • 检查「好数组」
    唯一的结论是如果数组中所有数的最大公约数为 11,则存在解,否则不存在。所以只需要计算所有数最大公约数即可,时间复杂度O(nlog(m))O(nlog(m)),其中 mm 为数字大小。

7

结束了啊,只会个easy题。

class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int nx=0,ny=0;
        for(int i=0;i<s1.size();++i)
        	if(s1[i]!=s2[i] && s1[i] == 'x')
        		++nx;
        	else if(s1[i]!= s2[i] && s1[i]=='y')
    			++ny;
	if((nx%2) == (ny%2))
		return nx/2 + ny/2 + 2*(nx%2);
	else
		return -1;
        return 0;
    }
};
3

第一题把我做废了...

    int minimumSwap(string s1, string s2) {
        int ans = 0, n = s1.size();
        int cnt1 = 0,cnt2 = 0;//统计有多少对x-y和y-x
        for(int i = 0; i < n; i++){
            if(s1[i]=='x'&&s2[i]=='y') cnt1++;
            else if(s1[i]=='y'&&s2[i]=='x') cnt2++;
        }
        //对于每一对 x-y 和 x-y 以及 y-x 和 y-x 都只需要一次操作即可完成匹配
        ans += cnt1/2+cnt2/2;//所需要的操作数
        cnt1%=2;//剩余未匹配的对数
        cnt2%=2;
        if(cnt1+cnt2==1) return -1;//只剩一个时无法匹配
        else if(cnt1+cnt2==2) ans+=2;//只剩了x-y和y-x 需要两次匹配
        return ans;
    }
2

第一题

class Solution {
    public int minimumSwap(String s1, String s2) {
        if(s1.length() != s2.length())
            return -1;
        if(s1.length() == 0 && s2.length() == 0)
            return 0;
        int n = s1.length();
        int swap1 = 0,swap2 = 0;
        for(int i = 0; i <n; i++){
            if(s1.charAt(i) == s2.charAt(i))
                continue;
            if(s1.charAt(i) == 'x' && s2.charAt(i) == 'y'){
                ++swap1;
            }else{
                ++swap2;
            }
        }
        if(swap1%2 != swap2%2)
            return -1;
        if(swap1%2 == 0){
            return swap1/2 + swap2/2;
        }else{
            return swap1/2 + swap2/2 + 2;
        }
    }
}

第二题

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        if(nums == null || nums.length == 0)
            return 0;
        int len = nums.length;
        List<Integer> good = new ArrayList<Integer>();
        good.add(-1);
        for(int i=0; i< len; i++){
            if(nums[i] % 2 == 1)
                good.add(i);
        }
        good.add(len);
        int size = good.size();
        if(size < k+2)
            return 0;
        int res = 0;
        for(int j = 1; j<size-k; j++){
            int pre = good.get(j) - good.get(j-1);
            int pro = good.get(j+k) - good.get(j+k-1);
            res += pre*pro;
        }
        return res;
    }
}
2

太难了

2

第一次做出来三题,可惜来晚了第三题没提交上
作为菜鸟,都是用的顶直观的写法,给同样实力不强的朋友们一点信心233


交换字符使得字符串相同

class Solution:
    def minimumSwap(self, s1: str, s2: str) -> int:
        unite = s1 + s2
        if unite.count('x') % 2 == 1:
            return -1
        if s1 == s2:
            return 0
        diffCount = 0
        x2y = 0
        for i in range(len(s1)):
            if s1[i] != s2[i]:
                diffCount += 1
                if s1[i] == 'x' and s2[i] == 'y':
                    x2y += 1
                    

        if x2y % 2 == 1:
            return int(diffCount / 2 + 1)
        return int(diffCount / 2)

统计「优美子数组」

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        oddCount = 0
        oddIndex = []
        for i, n in enumerate(nums):
            if n % 2 == 1:
                oddCount += 1
                oddIndex.append(i)
        if oddCount < k:
            return 0
        
        niceCount = 0
        for i in range(oddCount-k+1):
            if i == 0:
                aheadNum = oddIndex[0] + 1
            else:
                aheadNum = oddIndex[i] - oddIndex[i-1]
            if i+k == oddCount:
                afterNum = len(nums) - oddIndex[-1]
            else:
                afterNum = oddIndex[i+k] - oddIndex[i+k-1]
                
            niceCount += aheadNum * afterNum
        return niceCount

移除无效的括号

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        temp = [c for c in s]
        removed = 0
        wait = []
        for i, c in enumerate(s):
            if c == '(':
                wait.append(i)
            elif c == ')':
                if len(wait) != 0:
                    wait.pop()
                else:
                    temp.pop(i-removed)
                    removed += 1

        for i in range(len(wait)):
            tempStr = ''.join(temp)
            toPop = tempStr.rindex('(')
            temp.pop(toPop)
            
        return ''.join(temp)
        
1

这次很简单嘛,第四题python自己有gcd美滋滋,2行就行了

1

第三题

C++ 我开了两个string, 其中一个用 string = char + string 构造

结果就 内存超限 了呜呜呜

1