leetcode-207-208

leetcode207题208题:

leetcode207题(课程表):

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

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

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

示例:

输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。

解答:

这其实是在判断prerequisites中的数组关系能否构成一个有向无环图,需要借助各个元素的入度表和邻接矩阵以及队列得以实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var canFinish = function(numCourses, prerequisites) {
var indegrees = [];//入度表
var adjacency = [];//邻接矩阵
for(var i=0;i<numCourses;i++){
adjacency[i] = [];
indegrees[i] = 0;
}
var queue = [];//队列
for(var i=0;i<prerequisites.length;i++){
var arr = prerequisites[i];
//arr[0]是后面要完成的,arr[1]是需要提前完成的
//图中应该是arr[1]指向arr[0],所以应该是arr[0]的入度加1
indegrees[arr[0]]++;//arr[0]的入度加1
adjacency[arr[1]].push(arr[0]);//arr[1]的指向里面有arr[0]
}
for(var i=0;i<numCourses;i++){//将入度为0的点放入队列
if(indegrees[i]==0){
queue.push(i);
}
}
while(queue.length!=0){//拿出队列中入度为0的点,并将其邻接矩阵的元素的入度减1
var temp = queue.shift();
numCourses--;
temp = adjacency[temp];
for(var i=0;i<temp.length;i++){
indegrees[temp[i]]--;
if(indegrees[temp[i]]==0){//如果入度为0,那么该放入队列中
queue.push(temp[i]);
}
}
}
return numCourses==0;//如果没有环的话,那么所有元素都会进入队列,那么最终numCourse最终为0
};

leetcode208题(实现Trie-前缀树):

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

示例:

Trie trie = new Trie();

trie.insert(“apple”);
trie.search(“apple”); // 返回 true
trie.search(“app”); // 返回 false
trie.startsWith(“app”); // 返回 true
trie.insert(“app”);
trie.search(“app”); // 返回 true

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
* Initialize your data structure here.
*/
var Trie = function() {
this.nextLetters = {};//将一个节点的向下相连的节点设置为对象中的内容
this.isWord = false;//插入进去的单词的最后一个节点的isWord为true,其它为false,默认为false
};

/**
* Inserts a word into the trie.
* @param {string} word
* @return {void}
*/
Trie.prototype.insert = function(word) {
var cur = this;
var arr = word.split('');
for(var i=0;i<arr.length;i++){
if(!cur.nextLetters.hasOwnProperty(arr[i])){
cur.nextLetters[arr[i]] = new Trie();
cur = cur.nextLetters[arr[i]];
}else{
cur = cur.nextLetters[arr[i]];
}
}
cur.isWord = true;
};

/**
* Returns if the word is in the trie.
* @param {string} word
* @return {boolean}
*/
Trie.prototype.search = function(word) {
var cur = this;
var arr = word.split('');
for(var i=0;i<arr.length;i++){
if(cur.nextLetters.hasOwnProperty(arr[i])){
cur = cur.nextLetters[arr[i]];
}else{
return false;
}
}
return cur.isWord;
};

/**
* Returns if there is any word in the trie that starts with the given prefix.
* @param {string} prefix
* @return {boolean}
*/
Trie.prototype.startsWith = function(prefix) {
var cur = this;
var arr = prefix.split('');
for(var i=0;i<arr.length;i++){
if(cur.nextLetters.hasOwnProperty(arr[i])){
cur = cur.nextLetters[arr[i]];
}else{
return false;
}
}
return true;
};

/**
* Your Trie object will be instantiated and called as such:
* var obj = new Trie()
* obj.insert(word)
* var param_2 = obj.search(word)
* var param_3 = obj.startsWith(prefix)
*/

taylor swift

分享到