2019-11-11  86 views 评论

Leetcode题目解析(191111):207&208

 标签:

Leetcode 207:课程表

题目描述

现在你总共有 n 门课需要选,记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件,判断是否可能完成所有课程的学习?

解题思路

这个题目是一个图的问题,所给的示例是用边缘列表来表示的图。也即假如边缘列表表示如下

序号 节点1 节点2
1 0 1
2 1 2
3 2 0

所表示的图为

图

可以发现上图就是一个无法实现课程的图,这类的特点是它是一个有向有环图

所以这个问题可以转换为另一个问题:如何判断一个图是有向无环图?

使用拓扑排序如下:

  • 首先新建一个入度表indegrees,用于记录每个节点的入度。
  • 新建一个队列que,用于存储入度为0的节点。
  • 当queue非空,一次将首节点出队,在图中删除此节点pre,并将--numCourses。当然,我们不是真正从邻接表中删除pre,而是将indegrees[cur]-=1;当入度-1邻接节点cur的入度为0的时候,说明cur所有前驱结点已经删除,可以入队。
  • 若是有向无环图,则所有节点一定入队并且出队过,即若存在环的话,一定有节点入度始终不为0,即numCourses大于0。所以判断numCourses==0即可判断出是否是有向无环图。

代码实现

复杂度

运行时间
复杂度挺高的

Leetcode 208:实现Trie(前缀树)

题目描述

实现一个 Trie (前缀树),包含insertsearch, 和 startsWith 这三个操作。

示例

解题思路

Trie树的结点结构
Trie树是一个有根的树,其结点具有以下字段:。

最多 R个指向子结点的链接,其中每个链接对应字母表数据集中的一个字母。
本文中假定 R为26,小写拉丁字母的数量。布尔字段,以指定节点是对应键的结尾还是只是键前缀。

向Trial插入字符串

我们通过搜索 Trie 树来插入一个键。我们从根开始搜索它对应于第一个键字符的链接。有两种情况:

  • 如果链接已经存在。那么沿着链接移动到树的下一个子层。算法继续搜索下一个键字符。
  • 如果链接不存在。创建一个新的节点,并将它与父节点的链接相连,该链接与当前的键字符相匹配。

重复以上步骤,直到到达键的最后一个字符,然后将当前节点标记为结束节点,算法完成。

时间复杂度:O(m),其中m为键长。在算法的每次迭代中,我们要么检查要么创建一个节点,直到到达键尾。只需要 m次操作。

空间复杂度:O(m)。最坏的情况下,新插入的键和 Trie 树中已有的键没有公共前缀。此时需要添加 m 个结点,使用 O(m)空间。

查找Trial中的字符串

这个思路很简单。每个键在Trie树种都表示从根到内部结点或者叶的路径。我们用第一个键字符开始,检查当前结点与建字符对应的链接,其有两种情况:

  • 存在链接。继续往下一个结点走,如此循环。
  • 没有链接。再看isStr是否是True,是则返回true,否则就返回false。

时间复杂度:O(m),空间复杂度O(1)。

查找Trie中的键前缀

类似于前面的方法,但是到达键前缀的末尾时,总是返回true。理由也很简单,我们只是为了寻找与键前缀相匹配的字符串而已,并不是完全相等的字符串。

时间复杂度:O(m),空间复杂度O(1)。

参考:https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode/

代码实现

复杂度分析

运行时间

给我留言

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: