A. Most Frequent Even Element (opens new window)

Count the frequency of all even numbers, then select the smallest even number with the highest frequency.

DETAILS

def mostFrequentEven(self, A: List[int]) -> int:
        if all(a % 2 == 1 for a in A): return -1
        c = collections.Counter([a for a in A if a % 2 == 0])
        v = max(list(c.values()))

        for a in sorted(A):
            if a % 2 == 0 and c[a] == v:
                return a

B. Optimal Partition of String (opens new window)

Count the occurrence of character in curring part, if duplicated character occurs, meaning we should start a new part.

DETAILS

def partitionString(self, S: str) -> int:
        cnt, ans = [0] * 26, 0
        for ch in S:
            pos = ord(ch) - ord('a')
            if cnt[pos]:
                ans += 1
                cnt = [0] * 26
            cnt[pos] += 1
        return ans + 1
        

C. Divide Intervals Into Minimum Number of Groups (opens new window)

Greedy. Use priority queue to store the ending time of all merged intervals, for each newly added interval [start, end], 'attach' it to the current interval with the earliest ending time. If the earliest ending time is still later than the start, meaning this new interval must be in a new group.

DETAILS

def minGroups(self, intervals: List[List[int]]) -> int:
        end = []
        for s, e in sorted(intervals):
            if end and end[0] < s:
                heapq.heappushpop(end, e)
            else:
                heapq.heappush(end, e)
        
        return len(end)

2407. Longest Increasing Subsequence II (opens new window)

Please refer to This LC Discussion (opens new window) for my solutions in English.

我们先从暴力的DP方法开始，用一个数组LIS来记录以每个数字结尾的最长递增序列长度。

对于数字a，以它为结尾的递增序列的最大长度，等同于以a - k到a - 1这些数字结尾的最大长度加一：

LIS[a] = max(LIS[a - k : a]) + 1

但是等号右边的求最大值也是线性时间，这样会带来平方的总时间。

考虑到题目本质是单点更新+线段查询，用线段树。

DETAILS

class SEG:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * 2 * self.n
       
    def query(self, l, r):
        l += self.n
        r += self.n
        ans = 0
        while l < r:
            if l & 1:
                ans = max(ans, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                ans = max(ans, self.tree[r])
            l >>= 1
            r >>= 1
        return ans
    
    def update(self, i, val):
        i += self.n
        self.tree[i] = val
        while i > 1:
            i >>= 1
            self.tree[i] = max(self.tree[i * 2], self.tree[i * 2 + 1])

class Solution:
    def lengthOfLIS(self, A: List[int], k: int) -> int:
        n, ans = max(A), 1
        seg = SEG(n)
        for a in A:
            a -= 1
            premax = seg.query(max(0, a - k), a)
            ans = max(ans, premax + 1)
            seg.update(a, premax + 1)
        return ans