2020/06/28

第29场周赛 rank：120 / 2260 AC:4 第195场周赛为参赛 AC 4

第29场双周赛

题目三：删掉一个元素以后全为 1 的最长子数组

本题实际上有一个母题，这里我们讲解母题。

最大连续1的个数 III

。

是一道比较适合采用滑窗解决的问题，思路是我们统计出现的0的位置和在窗内0出现的次数，一旦超过次数，更新左端点即可。

是一个比较好的框架思路，需要借助一个双端队列完成快速的更新左端点的位置。

class Solution:
    def longestOnes(self, nums: List[int], K: int) -> int:
        right = 0
        ans = 0
        num_0 = 0
        queue = collections.deque()
        # 这里的left初始为-1，是为了好统一计算窗的长度
        left = -1
        while right < len(nums):
            if nums[right] == 0:
                queue.append(right)
                num_0 += 1
                if num_0 > K:
                # 每次在计算的时候，右端点是0，左端点也是0，因此窗的长度是right-left-1
                    ans = max(ans, right-left-1)
                    left = queue.popleft()
                    num_0 -= 1
            right += 1
        return max(ans, right-left-1)

回归这次的考试题目就简单了。

唯一的不同在于这里是删除而不是替换。

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        if 0 not in set(nums):
            return len(nums)-1
        right = 0
        ans = 0
        num_0 = 0
        queue = collections.deque()
        left = -1
        while right < len(nums):
            if nums[right] == 0:
                queue.append(right)
                num_0 += 1
                if num_0 > 1:
                    ans = max(ans, right-left-2)
                    left = queue.popleft()
                    num_0 -= 1
            right += 1
        return max(ans, right-left-2)

第四题：并行课程II

一道考察状态压缩DP的题目，结合了dfs。在考试时候采用了高度贪心的策略，但是后来整明，这种方法是错误的，对于相同完成权重的并行优化问题，是不存在贪心的策略的。只能采用DP的方法来求解。

题目有两个比较好的地方，首先是对于依赖关系，这里采用的掩码的思路，也就是假设对于课程 5 ，需要课程1，2，3的先修。因此，

mask[5] = (00111)2

。这样在判断某个课程是某满足先修时，只需要

mask[j]&i == mask[j]

即可。保证相关的位置上都得是1。

另外是，dfs的搜索策略。每次考虑每门课程有没有被选取，然后更新状态。

class Solution:
    def minNumberOfSemesters(self, n: int, dependencies: List[List[int]], k: int) -> int:
        # 状态压缩dp
        def dfs(index, num, k, day, i):
            if (num-index < k): # num-index最多还能上的课程数量
                return # 最优解一定是要把课程上满的，这种不符合了
            if k == 0:
                if dp[i] == -1 or dp[i] > day:
                    dp[i] = day
            else:
                # 选择这门课
                dfs(index+1, num, k-1, day, i|(1<<lesson[index]))
                # 不选择这门课
                dfs(index+1, num, k, day, i)

        # dp不同的状态表示不同的已完成课程，属性是学期数量
        dp = [-1]*(1<<n)
        dp[0] = 0  ## 什么课都不上，自然是0学期
        # 构建掩码，为了方便，计数从0开始
        mask = [0]*n
        for pre, cur in dependencies:
            pre -= 1
            cur -= 1
            mask[cur] |= 1<<pre
        # 枚举各种课程的组合
        for i in range(1<<n):
            if dp[i] == -1:
                continue ## 这种学过课程情况还无法出现。属性是非法的
            lesson = []
            for j in range(n):
                if (i>>j) & 1 == 1:
                    continue # 表示这门课已经上过
                if mask[j]&i != mask[j]:
                    continue  # 本门课程j在当前的学过课程的下还无法解锁
                lesson.append(j)
            num = len(lesson)
            # 传入，课程在lesson中的索引，可选课程的数量，能上的最大课程数量，学期数，状态
            dfs(0, num, min(num, k), dp[i]+1, i)
        return dp[(1<<n)-1]

这个题目属实很好，值得多做。

第195场周赛

第四题：满足不等式的最大值

是一道考察单调队列的题目，我们维护一个递减的单调栈即可。

这里是在每个后方的元素读入之后，考察前面最优的选择。

class Solution:
    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
        ans = float('-inf')
        stack = collections.deque()
        for x,y in points:
        # 考察队头元素，也就是最大元素，是否满足要求
            while stack and x-stack[0][0]>k:
                stack.popleft()
            if stack:
                ans = max(ans, x+y+stack[0][1])
             # 维护递减序列，弹出比较小的那些
            while stack and stack[-1][1]<=y-x:
                stack.pop()
            stack.append([x, y-x])
        return ans