跳到主要内容

1462. 课程安排 IV [medium]

1462. 课程安排 IV [medium]​

https://leetcode-cn.com/problems/course-schedule-iv/

你总共需要上 n 门课，课程编号依次为 0 到 n-1 。

有的课会有直接的先修课程，比如如果想上课程 0 ，你必须先上课程 1 ，那么会以 [1,0] 数对的形式给出先修课程数对。

给你课程总数 n 和一个直接先修课程数对列表 prerequisite 和一个查询对列表 queries 。

对于每个查询对 queries[i] ，请判断 queries[i][0] 是否是 queries[i][1] 的先修课程。

请返回一个布尔值列表，列表中每个元素依次分别对应 queries 每个查询对的判断结果。

注意：如果课程 a 是课程 b 的先修课程且课程 b 是课程 c 的先修课程，那么课程 a 也是课程 c 的先修课程。

示例 1：

image

输入：n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
输出：[false,true]
解释：课程 0 不是课程 1 的先修课程，但课程 1 是课程 0 的先修课程。

示例 2：

输入：n = 2, prerequisites = [], queries = [[1,0],[0,1]]
输出：[false,false]
解释：没有先修课程对，所以每门课程之间是独立的。

示例 3：

image

输入：n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
输出：[true,true]

示例 4：

输入：n = 3, prerequisites = [[1,0],[2,0]], queries = [[0,1],[2,0]]
输出：[false,true]

示例 5：

输入：n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]
输出：[true,false,true,false]

提示：

  • 2 <= n <= 100
  • 0 <= prerequisite.length <= (n * (n - 1) / 2)
  • 0 <= prerequisite[i][0], prerequisite[i][1] < n
  • prerequisite[i][0] != prerequisite[i][1]
  • 先修课程图中没有环。
  • 先修课程图中没有重复的边。
  • 1 <= queries.length <= 10^4
  • queries[i][0] != queries[i][1]

通过次数2,142 | 提交次数5,539

Second Try​

2020-07-01

floyd算法解法，，又一个新的经典算法，若不是这算法也算有名，上一个解法通过后法也就过去了。可惜对许多算法不算熟悉，所以算是一个学习新算法的练习机会。

floyd算法是跟dijkstra一路的，不过dijstra算法是从某个点到其他点的最短距离，而floyd是任意点到任意点的最短距离，复杂度是O(n^3). dijstra复杂度是O(NlgN).

对于三层循环kij, k必须在外部，这样才能对所有i,j不停的使用不同的中间点，且不断迭代更新。如果k在最里面，则对于特定的i,j只能被更新一轮,无法实现遍历所有可能。

好像是第一次遇到三轮迭代，结果顺序还有要求的算法。

floyd算法

https://www.bilibili.com/video/BV1Ut41197NX?from=search&seid=6252633800284596542

https://brilliant.org/wiki/floyd-warshall-algorithm/

理解floyd算法有个障碍，很多例子给的都是A到B的距离，比较A-C, C-B的距离，给的例子也只有三个点

本来以为floyd算法很牛逼，其实算起来时间完全比不上上个算法，毕竟是遍历了所有可能。不过floyd的原始意义是用来计算最短路径，还能用来解这个题，也算是灵活。

# 来一波floyd
class Solution(object):
    def checkIfPrerequisite(self, n, prerequisites, queries):
        """
        :type n: int
        :type prerequisites: List[List[int]]
        :type queries: List[List[int]]
        :rtype: List[bool]
        """
        dp = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 0
        for prereq, curr in prerequisites:
            dp[prereq][curr] = 1
        # k必须在外部，这样才能对所有i,j不停的使用不同的中间点，且不断迭代更新
        # 如果k在最里面，则对于特定的i,j只能被更新一轮
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
        rv = [dp[noi][noii] < float('inf') for noi, noii in queries]
        return rv

  • 执行用时：3076 ms, 在所有 Python 提交中击败了8.00%的用户
  • 内存消耗：15.5 MB, 在所有 Python 提交中击败了100.00%的用户
  • 稍微优化的版本

不需要测量距离，直接判断是否联通即可。

# 来一波优化的floyd
class Solution(object):
    def checkIfPrerequisite(self, n, prerequisites, queries):
        """
        :type n: int
        :type prerequisites: List[List[int]]
        :type queries: List[List[int]]
        :rtype: List[bool]
        """
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        for prereq, curr in prerequisites:
            dp[prereq][curr] = True
        # k必须在外部，这样才能对所有i,j不停的使用不同的中间点，且不断迭代更新
        # 如果k在最里面，则对于特定的i,j只能被更新一轮
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dp[i][j] = dp[i][j] or (dp[i][k] and dp[k][j])
        rv = [dp[noi][noii] for noi, noii in queries]
        return rv
  • 执行用时：1156 ms, 在所有 Python 提交中击败了30.00%的用户
  • 内存消耗：15.3 MB, 在所有 Python 提交中击败了100.00%的用户
  • 错误版本

k,i,j中k不在外围的情况，在某个测试集的时候自动挂掉了，还是测试集牛逼。

# 来一波floyd
class Solution(object):
    def checkIfPrerequisite(self, n, prerequisites, queries):
        """
        :type n: int
        :type prerequisites: List[List[int]]
        :type queries: List[List[int]]
        :rtype: List[bool]
        """
        dp = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 0
        for prereq, curr in prerequisites:
            dp[prereq][curr] = 1
        # k必须在外部，这样才能对所有i,j不停的使用不同的中间点，且不断迭代更新
        # 如果k在最里面，则对于特定的i,j只能被更新一轮
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
        rv = [dp[noi][noii] < float('inf') for noi, noii in queries]
        return rv

First Try​

2020-07-01

参考提示已经知道了使用打表法，但还是不知道怎么高效构建一个reachable[n][n]的数组。参考题解了解到也可以用dfs，还好对于递归已经很熟悉，终于也搞出来一个版本。

平时构建graph,都是一个点和下一个点，只能一步步往下遍历，遇到题目这种情况很麻烦。其实可以搞类似的图结构，但是每个点下面保存的都是可达到的所有节点，空间占用巨大，但是效果很给力。遍历每个节点，在递归结束后才收集，相当于逆序收集下游，最后上游集大成者。

class Solution(object):
    def checkIfPrerequisite(self, n, prerequisites, queries):
        """
        :type n: int
        :type prerequisites: List[List[int]]
        :type queries: List[List[int]]
        :rtype: List[bool]
        """
        # 靠，还超时了，难怪觉得这题怎么这么容易
        # 看提示才知道需要搞个超大空间的动态规划
        # cache = [[0] * n for i in range(n)]
        graph = collections.defaultdict(list)
        indgree = [0 for i in range(n)]
        for prereq, curr in prerequisites:
            graph[prereq].append(curr)
            indgree[curr] += 1
        starts= []
        for i in range(n):
            if indgree[i] == 0:
                starts.append(i)
        # print(starts)
        reachable = collections.defaultdict(set)
        visited = set()
        def dfs(graph, node, reachable):
            if node in visited:
                return 
            visited.add(node)
            reachable[node].update(graph[node])  # 差点忘记这一波
            for n in graph[node]:
                dfs(graph, n, reachable)
                reachable[node].update(reachable[n])
        for node in starts:
            dfs(graph, node, reachable)       
        
        rv = []
        for ni, nii in queries:
            if nii in reachable[ni]:
                rv.append(True)
            else:
                rv.append(False)
        return rv
  • 执行用时：124 ms, 在所有 Python 提交中击败了96.00%的用户
  • 内存消耗：15.6 MB, 在所有 Python 提交中击败了100.00%的用户
  • time exceeded version

非常自然的一个版本，对每个检查元素检查其中一个是否在另一个的下游，但是无奈这是n个查询，每次操作时间就爆表了。


class Solution(object):
    def checkIfPrerequisite(self, n, prerequisites, queries):
        """
        :type n: int
        :type prerequisites: List[List[int]]
        :type queries: List[List[int]]
        :rtype: List[bool]
        """
        # 靠，还超时了，难怪觉得这题怎么这么容易
        graph = collections.defaultdict(list)
        for prereq, curr in prerequisites:
            graph[prereq].append(curr)
        def dfs(graph, node, nexn):
            if nexn in graph[node]:
                return True
            for n in graph[node]:
                if dfs(graph, n, nexn):
                    return True
            return False

        rv = []
        for ni, nii in queries:
            rv.append(dfs(graph, ni, nii))
        return rv