WeeklyConstest161

发表于 分类于

力扣160场周赛[链接][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'。

算法分析

这是唯一过的题了。。。本题的思维并不难，分两种情况进行计数；搜先遍历数组，用x和y计数：

  • s1[i]=='x'&&s2[i]=='y'时x++；
  • s1[i]=='y'&&s2[i]=='x'时y++；

计数完后分三种情况计算结果，用ans存放答案：

  • ans+=x/2+y/2，相同的情况可以进行一次换位满足；
  • 第一种情况x%2==0&&y%2==0,这种情况不用处理直接返回ans的值
  • 第二种情况x%2==1&&y%2==1,这种情况需要二次交换得到相同的字符串返回ans+2
  • 第三种情况，不是之前的两种情况，则不能变成一样的字符串，直接返回-1

上代码

C++代码

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

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int minimumSwap(String s1, String s2) {
        int x=0,y=0;
        for(int i=0;i<s1.length();i++){
            if(s1.charAt(i)=='x'&&s2.charAt(i)=='y')x++;
            else if(s1.charAt(i)=='y'&&s2.charAt(i)=='x')y++;
        }
        int ans=0;
        ans+=x/2+y/2;
        if(x%2==1&&y%2==1)return ans+2;
        else if(!(x%2==1)&&!(y%2==1))return ans;
        return -1;
    }
}

第二题：思维题（乘法原理）

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

算法分析

通过分析多个样例可以得到结论，满足条件的数组个数等于左边离得最近的奇数的距离+1*右边里得最近的奇数的距离，前提中间的是满足条件的数组子集；在数组前后加上-1和n可以减少代码的复杂度，这种处理就是为了不用去考虑边界的情况，在循环遍历的时候

特别注意 : ‘&’的优先级小于’==’

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int n=nums.length;
        int ans=0;
        List<Integer> list = new ArrayList<>();
        list.add(-1);
        for(int i=0;i<nums.length;i++){
            if((nums[i] & 1)== 1)//优先级：& < ==
                list.add(i);
        }
        list.add(n);
        for(int i=k,j=1;i<list.size()-1;i++,j++){
            int l=list.get(j)-list.get(j-1),r=list.get(i+1)-list.get(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中，不为空向外弹出一个元素，遍历结束后，将栈中剩余的元素添加到set中，最后生成结果的字符串，当set中包含该下标的时候跳过，否则一直往上添加即可，最后返回答案

C++代码

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

Java代码

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 s) {
        Stack<Integer> sta = new Stack<>();
        Set<Integer> st = new HashSet<>();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                sta.push(i);
            }else if(s.charAt(i)==')'){
                if(sta.empty())st.add(i);
                else sta.pop();
            }
        }
        while(!sta.empty()){
            st.add(sta.pop());
        }
        StringBuffer sb = new StringBuffer();
        for(int i=0;i<s.length();i++){
            if(st.contains(i));
            else sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

第四题：裴蜀定理

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

算法分析

裴蜀定理：[详解][https://oi-wiki.org/math/bezouts/]

将裴蜀定理推广到多元就可以了，简而言之就是数组中有两个数是互质的就可以了

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int gcd(int x,int y){
        if(x<y){
            int t=x;
            x=y;
            y=t;
        }
        if(y==0)return x;
        return gcd(y,x%y);
    }
    bool isGoodArray(vector<int>& nums) {
        int t=nums[0];
        for(int i=1;i<nums.size();i++){
            t = gcd(t,nums[i]);
            if(t==1)return true;
        }
        if(t==1)return true;
        return false;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int gcd(int x,int y){
        if(x<y){
            int t=x;
            x=y;
            y=t;
        }
        if(y==0)return x;
        return gcd(y,x%y);
    }
    public boolean isGoodArray(int[] nums) {
        int t = nums[0];
        for(int i=1;i<nums.length;i++){
            t=gcd(t,nums[i]);
            if(t==1)return true;
        }
        if(t==1)return true;
        return false;
    }
}