Leetcode_Weekly_310

比赛地址：第 310 场周赛
由于本人较懒，格式原因可能不太会注意，原题地址就不单独贴了。直接进上方超链看对应题号就可以。且出于能力原因我一眼第四题都不会看，是个每周稳两道冲三道的菜鸡(笑)，即只更新前三题的思路和反思。对应序号括号后面的是对应力扣题号，可以直接搜到。

题-思-解

1(2404)、出现最频繁的偶数元素

1.1 我的思路

出现次数问题，一眼丁真鉴定为hash，由于有序hash特性，将出现过的偶数作为key放入map后会自动排序，value为对应偶数出现次数，且用迭代器从前到后遍历map的过程中也是先看key大小(因为map的主key有序性)再在循环内比较value，大value留key，一样value不变，此时不变的value就是更小的，因为迭代器对应较小。思路就是这样。

1.2 代码

1.2.1 My

class Solution {
public:
    int mostFrequentEven(vector<int>& nums) {
        map<int,int>mmp;
        int result = -1;
        int hmt = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] % 2 == 0){
                if (mmp.find(nums[i]) == mmp.end()){
                    mmp.emplace(nums[i],1);
                } else{
                    mmp[nums[i]]++;
                }
            }
        }
        for (auto it : mmp) {
            if (hmt < it.second){
                result = it.first;
                hmt = it.second;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1.2.2 Other answer（also map）

class Solution {
public:
    int mostFrequentEven(vector<int>& nums) {
        map<int, int> mp;
        for (auto &x : nums) { /* 统计元素出现次数 */
            mp[x]++;
        }
    
        int ans = -1;
        int mx = 0;
        for (auto &[val, cnt] : mp) {
            if (mp[val] > 0 && val % 2 == 0 && cnt > mx) { /* 统计次数最多的偶数 */
                ans = val;
                mx  = cnt;
            }
        }
        return ans;
    }
};
//作者：liu-xiang-3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.2.3 double 100%

class Solution {
public:
    int mostFrequentEven(vector<int>& nums) {
        int s=nums.size();
        int count[100000]={0};
        int flag=0;
        int num_max=0;
        int maxn=0;
        for(int i=0;i<s;i++){
            if(nums[i]%2==0) {
                flag = 1;
                count[nums[i]]++;
                if (count[nums[i]] > num_max) {
                    num_max = count[nums[i]];
                    maxn = nums[i];
                }
                else if(count[nums[i]] == num_max){
                    maxn=min(maxn,nums[i]);
                }
            }
        }
        if(flag){
            return maxn;
        }
        else{
            return -1;
        }
        
    }
};

//作者：Arc_zml
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
26
27
28
29
30
31
32

1.3 反思

此次第一题一共提供了三版代码，效率排名为312，方法二在初始化map的时候将所有数字全放到map，这就造成了空间利用率不够高后续循环调用的冗余度过大，但代码确实是更短，可效率确实我那样更高些。方法三是双百，原作者在代码中自己模拟了map，且在每一次循环中都维护着num_max,这就导致了单次遍历就可以完成任务，且并没有使用任何顺序容器。在我建立容器时为了保持有序性编译器做了自己的排序，肯定是消耗内存的，且初始化遍历一次，对map对象进行内部遍历又一次，确实效率没一次过的效率高。“模拟map + 维护单值”的做法确实在这种题很吃香。

2(2405)、子字符串的最优划分

2.1 我的思路

滑动窗口+hash，单窗口内不能存在重复字母，存在则更新窗口大小为0、划分数量+1、clear map。一次遍历得到答案，但并没有双百。至于正向反向不影响答案，因为不存在重复字母的序列是一样的不分正反。

2.2 代码

2.2.1 My(滑动窗口+hash)

class Solution {
public:
 int partitionString(string s) {
        map<char,int> mmp;
        int howmany = 1;
        for (int i = 0; i < s.size(); ++i) {
            if (mmp.find(s[i]) == mmp.end()){
                mmp.emplace(s[i],0);
            } else{
                mmp.clear();
                mmp.emplace(s[i],0);
                howmany++;
            }
        }
        return howmany;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.2.2 贪心+位运算

class Solution {
public:
    int partitionString(string s) {
        int i = 0;
        int ans = 0;
        while (i < s.size()) {
            int j = i;
            int mask = 0;
            /* 判断是否有重复字母出现 */
            while (j < s.size() && (mask & (1 << (s[j] - 'a'))) == 0) {
                mask |= 1 << (s[j++] - 'a');
            }
            ans++;
            i = j;
        }
        return ans;
    }
};

//作者：liu-xiang-3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.3 反思

滑动窗口+hash固然很好，但从优化来说用unordered_map更好，因为不需要排序特性。位运算更加快速，从bit角度模拟了map，省去编译器的优化过程。这道题的位运算有两个注意点：

• 如何限制边界？答：size越界 or 出现进位
• 如何判断进位？ 答：在当前mask赋值前进行判断 (mask & (1 << (s[j] - 'a'))) == 0 ，这种情况便是不会出现进位的情况(对应bit位不重复)

简单例子可为 “abcbcb”，对应bit为 111 110 110 。
发现自己对位运算和贪心很不熟练，加以count，加把劲骑士，下次一定学。

3(2406)、将区间分为最少组数

3.1 我的思路

说来惭愧，这道题本应该用线段树来做，之前做题没有完全搞懂，只能用自己的土方法了。

1. 对原vector排序，规律按照字典序就可以。(为顺序遍历做处理)
2. 取到intervals.size()大小的bool数组，用来存取第 i 个vector是否被使用过。(剪枝)
3. 由于 ‘1’ 中已经将 vector 变为有序，顺序处理，即只要没被使用过，就直接将 result (组数)++ 。至于这一组哪些对应bool变true放在 digui 函数中处理。(结果赋值点)
4. 对当前 (假设当前为第 i 个) 之后的vector进行遍历，如果遇到符合 intervals[j][0] > intervals[i-1][1] 即前一个的后面小于后一个的前面这种情况，就停止当前遍历并递归到下一次循环中。注意这里每一个的遍历次数最多为 size - i 因此时间复杂度还不是很爆炸。(判断当前组还有哪些合法成员并修改对应bool数组为true)
5. 出于在 digui 函数中的 for 是从前到后遍历一个有序数组，这里用二分优化查找插入点的过程。(剪枝)
6. 超时了捏，法克鱿。(剪枝也没毛用，你和nlogn沾边了)

3.2 代码

3.2.1 My(排序+递归+二分优化)

class Solution {
public:
   //3_将区间分为最少组数
    int erfen_3(vector<vector<int>>& intervals, int findit, int i, int right){
        //1,3,5 找4
        int mid = (i + right)/2;
        if (i >= right){
            return mid;
        }
        if (intervals[mid][0] > findit){
            right = mid -1;
        } else{
            i = mid + 1;
        }
        return erfen_3(intervals,findit,i, right);
    }
    void digui_3(vector<vector<int>>& intervals, vector<bool>& isUsed , int i){
        int aim = erfen_3(intervals,intervals[i-1][1],i,intervals.size()-1);
        if (intervals[aim][0] < intervals[i-1][1]){
            aim++;
        }
        for (int j = aim; j < intervals.size(); ++j) {
            if (intervals[j][0] > intervals[i-1][1] && isUsed[j] == false){
                isUsed[j] = true;
                digui_3(intervals,isUsed,j+1);
                break;
            }
        }
    }
    int minGroups(vector<vector<int>>& intervals) {
        int result = 0;
        sort(intervals.begin(),intervals.end());
        vector<bool>isUsed(intervals.size(),false);
        for (int i = 0; i < intervals.size(); ++i) {
            if (isUsed[i] == false){
                result++;
                isUsed[i] = true;
                //递归
                digui_3(intervals,isUsed,i+1);
            }
        }
        return result;
    }
};
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

3.2.2 数组模拟hash，段状态压缩

class Solution {
public:
    const int N = 1e6 + 2;
    int minGroups(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<int> diff(N);
        for(auto it : intervals){
            int l = it[0];
            int r = it[1];
            diff[l]++;
            diff[r+1]--;
        }
        int now = diff[0];
        int ans = now;
        for (int i = 1; i < N; ++i) {
            now += diff[i];
            ans = max(now,ans);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.2.2.1 逻辑review

1. 明确这题可能出现的数值对边界(最大值)N为 10^6
2. 创建大小为 N 的数组 diff 用来存放压缩后的状态
3. 对整个 intervals 进行遍历，并对 diff 数组初始化。这里注意，状态压缩是默认前端点处于段重复状态(根据题意知段重复时必须开辟新组)，而后端点处于可合并状态。可合并需要满足当前闭区间无重复点，即 “r+1”。举例如：[1,3] and [5,6]是一对可合并区间对。对重复状态采取 +1 对合并状态采取 -1 。最后根据从前向后的遍历，可以得到答案。
4. 这里有需要思考的点，就是压缩后的状态是如何代表是否可以合并的。对于区间 [a,b] 明显，区间内只要存在其他点就说明是重复的，在 diff 中只有一个点来判断是否重复，这样是否可行呢？答案肯定是可行的，给 diff[a]++ 就代表之后的区间都可以取到重合，直到遇到 diff[b+1] 。那么再考虑特殊情况，只存在一个数值对时如何得到答案呢？因为取遍数组 diff 就会发现结果是 0 而不是我们想要的答案。这时就需要对压缩后的状态进行分析，从前向后进行累加，保留最大状态就可以，因为整个过程是动态的，即在整个遍历过程中会出现“合并”。例：
   [1,2]\[3,4]\[2,5]
diff->{1,1,1,0,0,0} - {0,0,1,0,1,1} = {1,1,0,0,-1,-1} 可见 [1,2]和[3,4]可以合并，因此会出现前面累加状态 -1 的情况。
5. 出于状态压缩的特殊性，若全遍历完不储存最大值则结果一定为0，在遍历过程中要找的就是 “合并最少且重叠最多的情况”
6. 目前自己只能理解到这种程度，后续肯定要记住这种思想，并问一下前辈们这样为什么可以。

3.2.3 priority_queue(那是真的牛批)

class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end());
        priority_queue<int, vector<int>, greater<int>>pq;
        for(auto &vec : intervals){
            if(pq.size()!=0 && pq.top() < vec[0]){
                pq.pop();
            }
            pq.push(vec[1]);
        }
        return pq.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.2.3.1 逻辑review

1. 想到这种方法的前提是可以将思维跳到第二步，即维护一个右边界组
2. 首先进行排序，按照左先右后顺序 sort
3. 下面建立优先队列，第三个参数取到 greater ，以小顶堆方式存放数据
4. 每次向内部存放的时候都判断是否当前数值对的左边界是否大于当前小顶堆的顶值，即判断左边界是否可以与当前最小的右边界拼接。
5. 可以进行拼接的时候就将当前小顶堆的顶pop，然后插入当前数值对右边界到优先队列
6. 那么是否可行呢？答案是肯定的，因为之前进行的排序保证了在之后进行的遍历过程中，在 interval内取到数值对的左边界均大于优先队列内对应数对的左边界(虽然只存放了右边界，但其配对左边界有这样的关系)，因此只存在将后遍历到的数值对拼接到前面遍历到的数值对堆中这种情况。而优先队列的特性又保证了在插入队列时其栈顶是最小值(最小右边界的数值对，且其对应左边界一定小于之后遍历到的数值对左边界)。
7. 如此以来就cover到了所有的情况，直接拿下。
8. Question：维护大顶堆，该如何写代码呢？选择左边界还是右边界做排序值呢？在我感觉来这样是最顺应本题特性的方法了，如果使用大顶堆就需要保证每个新遍历到的数值对右边界要同时小于遍历过的数值对的左边界和右边界，即要按照右边界排序，并取左边界为大顶堆内元素。看着是镜像，但排序需要重新对数值对进行颠倒构造，提高了时间复杂度。
9. Question：既然每次都保证了当前遍历数值对的左边界大于堆内右边界，那排序是不是就不需要了呢？例：[[5,10],[6,8],[1,5],[2,3],[1,10]] 明显前三个入堆后，堆内数据变成了 {5,8,10} ，但在 [2,3] 想入堆时，原本可以合并的 [5,10] 现在只剩下了一个 10 ，无法保证可以合并。因此为了符合小顶堆堆顶最小的这种特性，需要对原数值对数组进行排序，保证不需要将当前数值对前插合并这种情况。排序后一是保证了左边界一定非递减，右边界在左边界相同时非递减。这样在遍历到一个数值对判断在堆中是否合并时就可以直接用左边界和其堆顶比，而不会出现堆内存在某值对应左边界比当前遍历到的数值对右边界还大的情况(前插合并)。

3.3 反思

待更新