LeetCode 单周赛310 && Acwing周赛68场总结

一、LeetCode 单周赛310

1、6176.出现最频繁的偶数元素

（1）原题链接：力扣https://leetcode.cn/problems/most-frequent-even-element/

（2）解题思路：

        先用哈希表保存每个偶数出现的次数，再输出次数出现最多的偶数，为避免比较出现次数相同的偶数的大小，我们可以先对nums数组进行排序，然后按顺序按条件遍历即可。

（3）代码：

class Solution {
public:
    int mostFrequentEven(vector<int>& nums) {
        map<int, int> mp;
        
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); i ++) {
            if(nums[i] % 2 == 0) mp[nums[i]] ++;
        }
        
        if(!mp.size()) return -1;
        
        int t = 0x3f3f3f3f, val = 0;
        for(auto& [k, v] : mp) {
            if(v > val) {
                t = k;
                val = v;
            }
        }
        
        return t;
    }
};

2、6177.子字符串的最优划分

（1）原题链接：力扣https://leetcode.cn/problems/optimal-partition-of-string/

（2）解题思路：

        遍历字符串，用哈希表保存出现的字母，若发现存在相同的字母，则答案+1并清空哈希表，同时保存当前这个重复出现的字母到哈希表中。

（3）代码：

class Solution {
public:
    int partitionString(string s) {
        unordered_map<char, int> mp;
        int res = 1;
 
        for(auto& ch: s) {
            if(mp[ch]) {
                mp.erase(mp.begin(), mp.end());
                res ++;
                mp[ch] ++;
            }
            if(!mp[ch]) mp[ch] ++;
        }
        return res;
    }
};

 

3、6178.将区间分为最少数组

（1）原题链接：力扣https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups/

（2）解题思路：

        求不重合的区间组的个数可以转换为求区间重合的最大值，因此我们可以用前缀和的思想来写，找到前缀和的最大值，即为答案。

（3）代码：

class Solution {
public:
    const int N = 1e6 + 10;
    int minGroups(vector<vector<int>>& intervals) {
        int res = 0;
        
        vector<int> a(N);
        for(auto& ils: intervals) {
            a[ils[0]] ++;
            a[ils[1] + 1] --;
            
        }
        
        vector<int> sum(N);
        for(int i = 1; i < a.size(); i ++ ) {
            sum[i] += sum[i - 1] + a[i];
            if(sum[i] > res) res = sum[i];
        }
        
        return res;
    }
};

二、AcWing周赛68

1、4612.去掉0

（1）原题链接：4612. 去掉0 - AcWing题库

（2）解题思路：

        1、先用一个tmp字符串（空串）保存去掉第一个‘1’出现之前的‘0’以后的字符串。

        2、然后再从后往前遍历字符串，统计第一个‘1’后出现的‘0’的个数，即为答案。

（3）参考代码： 

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    
    while(t --) {
        string s;
        cin >> s;
        
        int res = 0;
        string tmp = "";
        
        bool flag = false;
        for(int i = 0; i < s.size(); i ++) {
            if(s[i] == '1') flag = true;
            if(flag) tmp += s[i];
        }
        
        bool flag1 = false;
        for(int i = tmp.size() - 1; i >= 0; i --) {
            if(tmp[i] == '1') flag1 = true;
            if(flag1 && tmp[i] == '0') res ++;
        }
        
        cout << res << endl;
    }
    return 0;
}

2、4613.方格跳跃

（1）原题链接：4613. 方格跳跃 - AcWing题库

（2）解题思路：

        1、先从左边遍历，统计第一次 ‘ > ' 出现的 ’ < ' 的个数；

        2、再从右边遍历，统计第一次 ’ < ' 出现的 ' > ' 的个数；

        3、为什么不用管中间，因为中间会一直卡在 ‘ > ' 和 ’ < ' 中间跳不出去。

（3）参考代码： 

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