标签：heapq Contest int 310 item intervals 端点 ans Weekly

Weekly Contest 310

Problem A

Most Frequent Even Element

思路

水题，用map存一下每个偶数数量然后统计就行

代码

class Solution:
    def mostFrequentEven(self, nums: List[int]) -> int:
        nums.sort()
        M = {}
        ans = -1
        t = 0
        for item in nums:
            if item%2==1:
                continue
            M.setdefault(item,0)
            
            M[item]+=1
            if M[item]>t:
                t = M[item]
                ans = item
        return ans

Problem B

Optimal Partition of String

思路

从左往右扫，用set记录出现的字符，重复就清空set

代码

class Solution:
    def partitionString(self, s: str) -> int:
        ans = 0
        M = {s[0]}
        for i in range(1,len(s)):
            if s[i] in M:
                ans += 1
                M = {s[i]}
            else:
                M.add(s[i])
        return ans+1

Problem C

Divide Intervals Into Minimum Number of Groups

思路

区间分组问题，先将区间按照左端点从小到大排序，然后遍历，然后维护一个优先队列，存储右端点，如果队列中最小的右节点都要比当前左端点要大，则需要新开一个组来存储一个区间，否则用这个右端点来代替最小的右端点。

代码

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        # print(intervals)
        L = []
        heapq.heapify(L)
        for i in range(len(intervals)):
            if len(L)==0 or L[0]>=intervals[i][0]:
                heapq.heappush(L,intervals[i][1])
            else:
                heapq.heappop(L)
                heapq.heappush(L,intervals[i][1])
        return len(L)

Problem D

Longest Increasing Subsequence II

思路

线段树，不会

代码

coming soon

总结

有进步 能出3题了

标签：heapq,Contest,int,310,item,intervals,端点,ans,Weekly
From： https://www.cnblogs.com/baihualiaoluan/p/16708564.html