讨论/题目交流/🐱 力扣第 9 场夜喵双周赛/
🐱 力扣第 9 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。
image.png

展开讨论
力扣 (LeetCode)发起于 2019-09-21
最近编辑于 2019-09-21

第 2 题

广度优先搜索,同时配合一定的剪枝策略,否则算法将超时。

剪枝的关键在于定义一个合法区域,一旦骑士移动到合法区域之外,则剪除该搜索分支,可以极大地提高效率。

合法区域定义如下:在起点与终点所限定的矩形的基础上,向四边各扩展 2 格所构成的矩形区域。为什么要扩展 2 格?这个 2 是怎么来的?由骑士的最基本走法可知,骑士要到达一个特定的点,最多需要额外 2 格的腾挪空间。如果不扩展这 2 格,那么有些终点将无法到达。

from collections import deque

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        start = complex(0, 0)
        end = complex(abs(x), abs(y))
        # 借助复数进行运算,而不是二元组,使得代码更加简洁高效
        directions = (1+2j, 1-2j, -1+2j, -1-2j, 2+1j, 2-1j, -2+1j, -2-1j)
        
        visited = set()
        q = deque([(start, 0)])
        while q:
            pos, depth = q.popleft()
            if not (-2 <= pos.real <= end.real + 2 and -2 <= pos.imag <= end.imag + 2):
                continue
            if pos in visited:
                continue
            if pos == end:
                return depth
            visited.add(pos)
            q.extend([(pos + d, depth + 1) for d in directions])

第 3 题

使用一组集合来保存矩阵的每一行数据,然后依次判断第一行的每一个数是否在剩余的所有的集合中均出现过。

O(MN) 时间复杂度(M、N 分别为矩阵的行数和列数):

class Solution:
    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        sets = [set(lst) for lst in mat]
        for x in mat[0]:
            if all(x in s for s in sets):
                return x
        return -1

第 4 题

注意:每个工人只能用一次,所以 N 个街区最终必然需要召唤出 N 个工人!

将任务放入堆中,每次取时间最短的两个,计算两者的总耗时(split + max(t1, t2))再放回堆中,直到只剩一个为止。

每次合并的两个任务其实分别代表两组任务,由于这两组任务的时间最接近,因此把这两组任务并行处理,重叠时间最多。

import heapq

class Solution:
    def minBuildTime(self, blocks: List[int], split: int) -> int:
        heapq.heapify(blocks)
        while len(blocks) > 1:
            t1 = heapq.heappop(blocks)
            t2 = heapq.heappop(blocks)
            heapq.heappush(blocks, split + max(t1, t2))
        return blocks[0]
2
展开全部 9 讨论