周赛补题（AcWing、力扣）

AcWing第68场周赛

第一题：4612. 去掉0 - AcWing题库

思路：题目的意思可以理解为最先出现的1和最后出现的1之间有多少个0，可以找到第一次出现得1的位置和最后出现1的位置，在这两个位置之间枚举有多少的0。当然字符串中可能没有1，这说明需要删除的次数为0.

代码

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        string a;
        cin >> a;
        int n = a.size() - 1;
        int i = 0, j = a.size() - 1;
        while(i < n) 
        {
            if(a[i] == '1') break;
            i ++;
        }
        while(j >= 0)
        {
            if(a[j] == '1') break;
            j --;
        }
        int ans = 0;
        if(i < j)
        {
            for(int k = i; k < j; k ++)
                if(a[k] == '0')
                    ans ++;
        }
        cout << ans << endl;
 
    }
    return 0;
}

第二题：4613. 方格跳跃 - AcWing题库

思路：在一个位置上为了能够跳出界外，只有两种情况

1、从开头到该位置都是'<'

2、从该位置到结尾都是'>'

所以我们只用枚举向开头开始连续的'<'的位置和从结尾往前有多少个'>'.

代码

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200010;
char a[N];
int n;
 
int main()
{
    cin >> n;
    cin >> a;
    int i = 0, j = n - 1;
    while(i < n)
    {
        if(a[i] == '>') break;
        i ++;
    }
    while(j >= 0)
    {
        if(a[j] == '<') break;
        j --;
    }
    int ans = i + n - 1 - j;
    cout << ans << endl;
    return 0;
}

力扣第301场周赛

第一题：2404. 出现最频繁的偶数元素 - 力扣（LeetCode）

思路：可以用map将偶数的个数存储起来，枚举map就最大次数的偶数即可。

代码

class Solution {
public:
    int mostFrequentEven(vector<int>& nums) {
        map<int, int> mp;
        for(auto i : nums)
            if((i & 1) == 0)
                mp[i] ++;
        int ans = -1, cnt = 0;
        for(auto [x, y] : mp)
        {
            if(cnt < y) ans = x, cnt = y;
            else if(cnt == y) ans = min(ans, x);
        }
        return ans;
    }
};

第二题：2405. 子字符串的最优划分 - 力扣（LeetCode）

思路：可以统计划分的次数，用一个set来存储，如果有一个数出现在set中就划分的次数就要加1.

代码

class Solution {
public:
    int partitionString(string s) {
        int ans = 0;
        set<int> S;
        for(auto i : s)
        {
            if(S.count(i))
            {
                ans ++;
                S.clear();
            }
            S.insert(i);
        }
        ans ++;
        return ans;
    }
};

第三题：2406. 将区间分为最少组数 - 力扣（LeetCode）

思路：可以用差分。这个题目的要求可以为在一个位置上面的次数的最大值。

const int N = 1000010;
class Solution {
public:
    int a[N];
    int minGroups(vector<vector<int>>& intervals) {
        memset(a, 0, sizeof a);
        for(auto i : intervals)
        {
            int l = i[0], r = i[1];
            a[l] ++, a[r + 1] --;
        }
        for(int i = 1; i < N; i ++) a[i] += a[i - 1];
        int ans = 0;
        for(int i = 1; i < N; i ++)
        {
            ans = max(ans, a[i]);
        }
        return ans;
    }
};