leetcode-45双周赛

Posted on In

leetcode双周赛第四题和每日一题992题解

1751. 最多可以参加的会议数目 II

yw6SyR.jpg
可以使用动态规划, 和背包问题一个思路, 一个会议可以参加也可以不参加, 对于一个会议, 如果不参加的话, 那就再其余会议中最多选择K个参加, 如果参加, 那就在其余会议(排除掉和该会议时间相交的会议)最多选择K-1个参加.

按照会议结束时间排序. dp[i][j]为在会议0~j中最多选择i个参加的最大价值, dp[i][j] = max(dp[i][j-1], value_j + dp[i-1][index]), index是0~j中最后一个和会议j时间不相交的会议

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def maxValue(self, events: List[List[int]], k: int) -> int:
    events.sort(key=lambda x: x[1])
    prev = [-1] * len(events)
    for i in range(len(prev) - 1, -1, -1):
        j = i
        while j >= 0 and events[j][1] >= events[i][0]: j -= 1
        prev[i] = j
    dp = [[0] * len(events) for _ in range(k + 1)]
    for i in range(1, len(dp)):
        dp[i][0] = events[0][2]
    for i in range(1, len(dp)):
        for j in range(1, len(dp[0])):
            value = events[j][2]
            index = prev[j]
            if index >= 0:
                value += dp[i-1][index]
            dp[i][j] = max(dp[i][j-1], value)
    return dp[k][-1]

按照会议开始时间排序. dp[i][j]为在会议j~end中最多选择i个的最大价值, dp[i][j] = max(dp[i][j+1], value_j + dp[i-1][index]), index是j~end中第一个和会议j时间不相交的会议

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def maxValue(self, events: List[List[int]], k: int) -> int:
    events.sort(key=lambda x: x[0])
    prev = [0] * len(events)
    for i in range(len(prev)):
        j = i
        while j < len(prev) and events[j][0] <= events[i][1]: j += 1 
        prev[i] = j
    dp = [[0] * len(events) for _ in range(k + 1)]
    for i in range(1, len(dp)):
        dp[i][-1] = events[-1][2]
    for i in range(1, k + 1):
        for j in range(len(dp[0]) - 2, -1, -1):
            value = events[j][2]
            index = prev[j]
            if index < len(prev):
                value += dp[i-1][index]
            dp[i][j] = max(dp[i][j+1], value)
    return dp[k][0]

总之, 无论按照什么排序, 只要想清楚选择一个会议后, 怎么找到下一个会议和dp的含义, dp转移方程就OK了, 我当时是按照开始时间排序, 但是按照结束时间的处理方式来的。。。

992. K 个不同整数的子数组

ywcxq1.jpg
先写个暴力法, 从每一个下标i开始, 遍历i~end, 如果从i到j的不同整数小于K, 那就继续增加j向后找, 如果正好的K, ans+1, 再继续向后找, 直到出现了新的数字 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 暴力 TLE: 49/55
def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
    ans = []
    for i in range(len(A)):
        if i != 0 and A[i] == A[i-1]:
            ans.append(ans[-1] + (-1 if K == 1 else 0))
            continue
        items = set()
        size = 0
        for j in range(i, len(A)):
            items.add(A[j])
            if len(items) == K:
                size += 1
            elif len(items) > K:
                break
        if size == 0:
            break
        ans.append(size)
    return sum(ans)

滑动窗口, 只要想清楚在暴力遍历中以i开始遍历一遍得到的结果怎么用于优化下一次的计算就好了. left, right为窗口的两端, n为窗口中不同整数的个数, 只要n < k就不断加入right, 如果n == k, 说明加入right后, 窗口中正好出现了k个不同整数, right继续向后移动, 直到遇见一个新数字, 这时候就要想办法移动left
以 arr = [1, 2, 2, 4, 2, 3], K = 3为例, left = 0, right = 0, right向后移动, 直到right = 3(arr[right] = 4), 此时 n = k, 记录bingo = right, 再向后走, 直到right = 5, n > k, 然后移动left缩小窗口, 此时left = 0, right = end_index

  • 如果(left, right)中已经没有了arr[left], 去掉left后, (left, right)就只有k-1个, 加上right正好k个, ans += 1, right += 1
  • 如果(left, right)中还有arr[left]
    • 如果arr = [1, 2, 2, 1, 4, 2, 3], bingo = 4, 下一个arr[left]的坐标 < bingo, (left, bingo]正好有k个, ans += right - bingo(以arr[left+1]开始的序列的数组个数)
    • 如果arr = [1, 2, 2, 4, 1, 2, 3], bingo = 3, 下一个arr[left]的坐标 > bingo, bingo = 下一个arr[left]下标, (left, bingo]正好有k个, ans += right - bingo 
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
def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
    left, right = 0, 0
    window = {}
    bingo = -1
    ans = 0
    while right < len(A):
        # add A[right] to window
        if A[right] in window:
            window[A[right]].append(right)
        else:
            window[A[right]] = deque([right])
        if len(window) < K:
            right += 1
        elif len(window) == K:
            ans += 1
            if bingo == -1: bingo = right
            right += 1
        else:
            if len(window[A[left]]) == 1:
                bingo = right
                right += 1
                window.pop(A[left])
            else:
                bingo = max(bingo, window[A[left]][1])
                window.pop(A[right])
                window[A[left]].popleft()
            ans += right - bingo
            left += 1
        # print(ans)
    if bingo == -1:
        return ans
    while left < right:
        if len(window[A[left]]) == 1:
            break
        window[A[left]].popleft()
        bingo = max(bingo, window[A[left]][0])
        ans += right - bingo
        left += 1
    return ans

1751. 最多可以参加的会议数目 II
992. K 个不同整数的子数组