力扣第310场周赛总结与反思

本次又是二题选手，甚至第一题第二题都因为思维上的断层，卡了好一会儿。发现自己的心态得转变一下，之前参加周赛也是为了查漏补缺，能不能全做出来无所谓，只需要找到自己的薄弱之处，然后补齐就行了。现在的心态有些急功近利，不敢让竞赛积分下降，虽然现在也才1630出头，但是总是想让它往上涨，想让它上涨是没错的，但是参加周赛的目的本身就是尽力而为，切不可因为这种心态，打乱了自己的做题节奏。同时我也注意到，自己有时候总觉得自己的付出没到点子上，刷了接近500题了还是在1600，甚至之前刷的题也没有完全领会，甚至将此归根于自己悟性不够，当我看到一些清北复交的大佬可能400多题就上1800，心里也很不是滋味。在接下来的刷题过程中，我认为自己还是应该摆正心态，得次次有进步和自己比，但是也不要过分和别人比，人人之间对于某个东西的悟性亦有参差，再加上之前我的基础可能确实不好。自己背后也一定得专心与坚持，等所有题目都差不多见过了以后，相信思维一定会打开。

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

计数然后只关注偶数，由于我们nums[i]映射到cnt中其实次序是会打乱的，因此在找最大出现次数的时候，还需要记录到目前为止出现次数最多的数字，如果小的话，也是需要更新的。

class Solution {
    public int mostFrequentEven(int[] nums) {
        int[]cnt=new int[100010];
        int len=nums.length;
        for(int i=0;i<len;i++){
            cnt[nums[i]]++;
        }
        int res=-1;
        int best=-1;
        for(int i=0;i<len;i++){
          if(nums[i]%2!=0) continue;
          if(cnt[nums[i]]>best||(cnt[nums[i]]==best&&nums[i]<res)){
              res=nums[i];
              best=cnt[res];
          }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

T2.6177.子字符串的最优划分

就是模拟分割题，找出所有分割线res就行，然后分割的组数就是res+1，我用set记录重复元素，然后一旦出现重复的元素，就说明该元素前面应该有一条分割线，就需要清空set,将当前元素加入，上面清空加入这个点卡了我好久，说明脑子还没有完全跟着程序走。

class Solution {
    public int partitionString(String s) {
        int len=s.length();
        int res=0;
        HashSet<Character> set=new HashSet<>();
        for(int i=0;i<len;i++){
            if(!set.contains(s.charAt(i))){
                set.add(s.charAt(i));
            }
            else{
                res++;
                //清空set,将当前元素加入
                set.clear();
                set.add(s.charAt(i));
            }
        }
        return res+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

T3.6178.将区间分为最少组数

最小堆+左边界升序入堆+贪心。看灵神的题解说是用到堆，没想到这也可以，一步步分析来。首先看到答案/划分与输入顺序无关，应该可以想到「排序」，给我们一些利于解题的性质。然后就是如何贪心地将区间进行组合，尤其是可能会存在多组的情况，可以看到在划分过程中，如果某个划分的组中区间出现重叠，那我们就应该新开一个划分组，但是在没有出现重叠的情况下，我们尽可能将当前数据放到之前划分的右边界最小的组中，并且更新其右边界。这种找最小同时更新最小再放入下次比较，我们可以采用堆实现，如果当前元素左边界比最小还小的话，只能入堆，相当于新开了一组，最终堆中的元素就是总组数。

思考单调递增队列也可以找到最小，但是当其某个新组的右边界比之前队列中的所有都要小的话，要把前面的全部出队，才能保证从队首取到最小值，但是这样子无法从队列中元素个数上反应组数了。

class Solution {
    public int minGroups(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->(a[0]-b[0]));
        PriorityQueue<Integer> pq=new PriorityQueue<>();
        for(int[]i:intervals){
            if(!pq.isEmpty()&&i[0]>pq.peek()){
                pq.poll();
                pq.offer(i[1]);
            }else{
                pq.offer(i[1]);
            }
        }
        return pq.size();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这题看似是求最小区间贪心，其实可以就用差分，将每个区间看成是给区间内的数+1，这样相当于就是尽可能在给定的数据范围内，将每个区间平铺开来。最终有重叠部分的最大值，相当于就是前缀和最大值，就是需要的组数。

class Solution {
    public int minGroups(int[][] intervals) {
        int len=intervals.length;
        //开辟的数组大小需要包含值域范围
        int[]c=new int[(int)1e6+10];
        for(int[]i:intervals){
            c[i[0]]+=1;
            c[i[1]+1]-=1;
        }
        int sum=0;
        int res=0;
        for(int cc:c){
            sum+=cc;
            res=Math.max(res,sum);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

T4.6206.最长递增子序列II

参考灵神的题解，和线段树有关，但是我这方面还不太熟练，准备出个专题文章好好学学。