In The End

个人博客

0%

Leetcode周赛第161场题解

发表于 更新于 分类于 ，

今天的周赛竞争很激烈啊，感觉都做得挺好的

这四道题代码实现上都很简单，更加偏向思维量一些

第四题的数论我失忆了，现在假装自己AK了

周赛传送门

https://leetcode-cn.com/contest/weekly-contest-161

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

题目

有两个长度相同的字符串 s1 和 s2，且它们其中 只含有 字符 "x" 和 "y"，你需要通过「交换字符」的方式使这两个字符串相同。

每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。

交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换 s1[i] 和 s2[j]，但不能交换 s1[i] 和 s1[j]。

最后，请你返回使 s1 和 s2 相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回 -1 。

示例 1：

1
2
3
4
输入：s1 = "xx", s2 = "yy"
输出：1
解释：
交换 s1[0] 和 s2[1]，得到 s1 = "yx"，s2 = "yx"。

示例 2：

1
2
3
4
5
6
输入：s1 = "xy", s2 = "yx"
输出：2
解释：
交换 s1[0] 和 s2[0]，得到 s1 = "yy"，s2 = "xx" 。
交换 s1[0] 和 s2[1]，得到 s1 = "xy"，s2 = "xy" 。
注意，你不能交换 s1[0] 和 s1[1] 使得 s1 变成 "yx"，因为我们只能交换属于两个不同字符串的字符。

示例 3：

1
2
输入：s1 = "xx", s2 = "xy"
输出：-1

示例 4：

1
2
输入：s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
输出：4

提示：

  • 1 <= s1.length, s2.length <= 1000
  • s1, s2 只包含 'x' 或 'y'。

题解

这题一开始卡了挺久的，心态差点卡炸了

后来在纸上摆弄了一下发现特别简单

有意思的地方是，这道题给的第一个样例和第二个样例其实就是提示

我们看样例1，当s1=”xx”，s2=”yy”时我们只需要一步就可以变成相同的字符串。再看样例2，对于样例2我们则需要两步。

请仔细思考上面的现象，你就能发现这道题的解法

下面我来揭晓答案，由于字符串只有x和y，所以我们的字符串一定可以通过上面的两种方法来变成相同的。那么那一种更赚呢，很明显是样例1这种的，所以我们只需要计算一下s1为x，s2为y的情况，记为a；再将s1为y，s2为x的情况记为b，然后如果a+b为奇数就输出-1（因为无法通过这两种方法消除），如果是偶数就让a内部两两消除（就是答案加上a/2），b同理，最后剩下的一对就得用方法2消除，也就是答案+2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int ans=0,a=0,b=0;
        for(int i=0;i<s1.length();i++){
            if(s1[i]=='x'&&s2[i]=='y') a++;
            else if(s1[i]=='y'&&s2[i]=='x') b++;
        }
        if((a+b)&1) return -1;
        else{
            ans+=a/2;
            ans+=b/2;
            int t=0;
            if(a&1) t++;
            if(b&1) t++;
            ans+=t;
            return ans;
        }
    }
};

5248. 统计「优美子数组」

题目

给你一个整数数组 nums 和一个整数 k。

如果某个子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

示例 1：

1
2
3
输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

示例 2：

1
2
3
输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。

示例 3：

1
2
输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16

提示：

  • 1 <= nums.length <= 50000
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= nums.length

题解

这道题首先得找到所有奇数的位置，生成一个数组，然后进行找到符合条件的范围（假设k=3，就得从i=0,j=2扫描整个奇数位置数组）

然后需要知道每个奇数左边和右边有多少偶数可以取到，我们拿样例3举例子

示例 3：

1
2
输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16

首先1 2 2 1是一定得取到的，我们可以看到左边的1有三个偶数2，那对应了四种情况，右边的1右边也有三个偶数2，也对应了四种情况，所以答案是4x4=16种

以此类推，如果有多个奇数就用双指针滑动求出每一种的答案，相加即可

我的代码在放入所有奇数的位置的同时还放入了-1和n，这样处理边界问题就会及其方便

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int n=nums.size();
        int ans=0;
        vector<int> v; 
        v.push_back(-1);
        for(int i=0;i<n;i++){
            if(nums[i]&1)
                v.push_back(i);
        }
        v.push_back(n);
        for(int i=k,j=1;i<v.size()-1;i++,j++){
            int l=v[j]-v[j-1],r=v[i+1]-v[i];
            ans+=l*r;
        }
        return ans;
    }
};

5249. 移除无效的括号

题目

给你一个由 '('、')' 和小写字母组成的字符串 s。

你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

请返回任意一个合法字符串。

有效「括号字符串」应当符合以下 任意一条 要求：

  • 空字符串或只包含小写字母的字符串
  • 可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
  • 可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

示例 1：

1
2
3
输入：s = "lee(t(c)o)de)"
输出："lee(t(c)o)de"
解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。

示例 2：

1
2
输入：s = "a)b(c)d"
输出："ab(c)d"

示例 3：

1
2
3
输入：s = "))(("
输出：""
解释：空字符串也是有效的

示例 4：

1
2
输入：s = "(a(b(c)d)"
输出："a(b(c)d)"

提示：

  • 1 <= s.length <= 10^5
  • s[i] 可能是 '('、')' 或英文小写字母

题解

我觉得第三题是今天这四道题里思维量最少的题了，但是相对来讲代码稍微麻烦一些（如果你没用方便的数据结构如set的话）

这题思路上来讲就是简单的括号匹配问题而已，一般我们的括号匹配都是往栈里面放字符的（左括号或者右括号），但是今天的题目如果你打破了这个思维定势的话就会很好做

具体的思路就是开一个int的栈，碰到左括号就把左括号的下标压进去，然后碰到右括号就直接将栈顶弹出，只有两种情况我们需要把下标插入进set里

  • 碰到右括号时发现栈空了，说明栈内没有可以与之匹配的左括号了，所以将这个右括号的下标插入进set
  • 遍历完字符串了发现栈内还有数字，说明这些都是没有右括号匹配的左括号，于是我们直接将它们全部插入进set

最后只要遍历一遍原字符串同时生成一个新串，然后每个字符都去询问一下set，如果在set中存在就说明是删除的字符，就不添加到新串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string minRemoveToMakeValid(string str) {
        stack<int> s;
        unordered_set<int> ss;
        for(int i=0;i<str.length();i++){
            if(str[i]=='(') s.push(i);
            else if(str[i]==')'){
                if(s.empty()) ss.insert(i);
                else s.pop();
            }
        }
        while(!s.empty()){
            ss.insert(s.top());
            s.pop();
        }
        string t;
        for(int i=0;i<str.length();i++)
            if(!ss.count(i))
                t+=str[i];
        return t;
    }
};

5250. 检查「好数组」

题目

给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。

假如该和结果为 1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。

示例 1：

1
2
3
4
输入：nums = [12,5,7,23]
输出：true
解释：挑选数字 5 和 7。
5*3 + 7*(-2) = 1

示例 2：

1
2
3
4
输入：nums = [29,6,10]
输出：true
解释：挑选数字 29, 6 和 10。
29*1 + 6*(-3) + 10*(-1) = 1

示例 3：

1
2
输入：nums = [3,6]
输出：false

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

题解

我先哭一会儿。。。就是没想起来这个定理啊

裴蜀定理，又称贝祖定理（Bézout’s lemma）。是代数几何中一个定理。

其内容是：

设a,b是不全为零的整数，则存在整数 , 使得 ax+by=gcd(a,b)

先考虑两个数的情况，当这两个数a和b互质的时候，ax+by就是1了（互质显然gcd为1），推广当多元如下

设a1,a2,a3……an为n个整数，d是它们的最大公约数，那么存在整数x1……xn使得x1*a1+x2*a2+…xn*an=d。

特别来说，如果a1…an互质，那么存在整数x1……xn使得x1*a1+x2*a2+…xn*an=1。证法类似两个数的情况。

所以只要对所有数字遍历一遍求gcd就行了

简单到爆炸。。。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
    bool isGoodArray(vector<int>& nums) {
        int ans=nums[0];
        for(int i=1;i<nums.size();i++)
            ans=gcd(ans,nums[i]);
        return ans==1;
    }
};

下周见下周见，祝我涛哥面试字节顺利哈哈哈