2019-10-14 Daily Report

概览

长安大道横九天,峨眉山月照秦川。

元数据:Course Schedule

时间:Monday, October 14, 2019 13:05 PM

作者:Syncher Pylon


  • 处理邮件
  • 更新 Todo List
  • 学习算法
  • 学习英语

算法学习笔记

今日算法题:Leetcode 207 Course Schedule

题目描述

题目大意是,有 n 门课,课程编号从 0 ~ n-1,课程之间是有依赖的,如果 0 号课程需先修于 1 号课程,那么依赖关系表示为 [0, 1],现在给定总课程数 n 和依赖关系 pairs,判断是否可以修完课程。

Example 1:

1
2
3
4
Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.

Example 2:

1
2
3
4
5
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.

分析

以课程编号为顶点,课程依赖关系作为有向边,构建有向图。

如给定依赖关系为 pairs = [[1, 0], [2, 6], [1, 7], [5, 1], [6, 4], [7, 0], [0, 5]]

graph LR
1((1)) -->0((0))
1 --> 7((7))
5((5)) --> 1
2((2)) --> 6((6))
6 --> 4((4))
7 --> 0
0 --> 5

3((3))

其中 0 -> 5 -> 1 -> 00 -> 5 -> 1 -> 7 -> 0构成循环依赖,因此无法完成所有课程。所以问题的本质是 判断有向图是否有环

实现

第一步: 构建有向图。使用连接矩阵表示有向图,0 和 1 代表连通性,代码如下:

1
2
3
graph = [[0] * n for _ in rang(n)]
for a, b in pairs:
graph[a][b] = 1

第二部:从第一个点开始 DFS 搜索所有可达点,标记搜索后的点,如果搜索过的点再次被搜索到说明长生循环依赖。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
visiting = visited = [[False] * n for _ in range(n)]

def dfs(x, y):
if visiting[x][y]:
return False
visiting[x][y] = True
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
for i in range(4):
new_x = x + dx[i]
new_y = y + dy[i]
if new_x < n and new_x >= 0 and new_y < n and new_y >= 0 and graph[new_x][new_y] == 1:
dfs(new_x, new_y)
visiting[x][y] = False
visited[x][y] = True
return True

for a, b in paris:
if not visited[x][y]:
dfs(a, b)

// TODO: Topological Sort

英语学习笔记

  • compliance: action or fact of complying with a wish or command.

    It helps you to ensure compliance in your daily business.

  • perception: the ability to see, hear, or becoming aware of somthing through the senses.

  • aware: having knowledge or perception of a situation or fact.

    • be aware of
    • be aware that
  • subsequent: coming after something in time; following

    subsequent chapter

  • overriding: more important than any other considerations. most important

    the overriding fundamental right: 最基本的权力

  • comprise: consist of; be made up of; constitute;

    It comprises many aspects.

  • confidentiality: the state of keeping or being kept secret or private.

  • disposal: the action or process of throwing away or getting rid of something.

  • unattended: /ˌənəˈtendəd/ not noticed or deal with.

  • suspicious: having or showing a cautious distrust of someone or something.

  • distrust: the feeling that someone or something cannot be relied upon.

  • lurk: be or remain hidden so as to wait in ambush for someone or something.

  • claim: 索赔

本文标题:2019-10-14 Daily Report

文章作者:Syncher

发布时间:2019年10月14日 - 13:10

最后更新:2019年10月18日 - 18:10

原始链接:https://0x400.com/2019-10-14-diary-2019-10-14.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。