文章目录
61 课程表
- Map + BFS
- 拓扑排序：将有向无环图转为线性顺序。
- 遍历prerequisites：1. 数组记录每个节点的入度，2. 哈希表记录依赖关系。
- n = 6，prerequisites = [ [3，0]，[3，1]，[4，1]，[4，2]，[5，3]，[5，4] ]。
0、1、2的入度为0，3、4、5的入度为2。
map：0：[3]，1：[3，4]，2：[4]，3：[5]，4：[5]。 - 创建队列，将入度为0的节点入队。
- 陆续将入度为0的节点从队列中弹出，直至队列为空。入度为0的节点不需要学习先修课程，所以可以直接选。
- 每弹出一个节点，就将该节点对应后续课程的入度 - 1，并将入度为0的节点加入队列。
- count记录选课的数量，每弹出一个节点，count++，最后判断count是否等于总课数。
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {boolean}
*/
var canFinish = function(numCourses, prerequisites) {
let pre = new Array(numCourses).fill(0);
let map = new Map();
for(let i = 0; i < prerequisites.length; i++){
pre[prerequisites[i][0]] += 1;
if(!map.has(prerequisites[i][1])){
map.set(prerequisites[i][1], [prerequisites[i][0]]);
}else{
map.get(prerequisites[i][1]).push(prerequisites[i][0]);
}
}
let queue = [];
let count = 0;
for(let j = 0; j < numCourses; j++){
if(pre[j] == 0){
queue.push(j);
}
}
while(queue.length != 0){
let item = queue.shift();
count += 1;
let cls = map.get(item);
if(cls != undefined){
for(let k = 0; k < cls.length; k++){
pre[cls[k]] -= 1;
if(pre[cls[k]] == 0){
queue.push(cls[k]);
}
}
}
}
return count == numCourses;
};
62 实现Trie（前缀树）
-
前缀树，又称字典树、单词查找树。
-
isEnd：记录该节点是否为最后一个节点（单词的结尾）。
-
Trie：保存了当前节点（字母）的下一个出现的所有字符。
-
例如：sea，sels，she组成的前缀树如下所示。
-
s
-
/ \
-
e h
-
/ \ \
-
a l e
-
|
-
s
-
插入：向Trie中插入一个单词。
从根结点开始与单词的第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，这时开始不断开辟新的结点，直到插入完单词的最后一个字符，并将最后一个结点isEnd = true，表示它是一个单词的末尾。 -
查找：查找Trie中是否存在单词word。
从根结点开始一直向下匹配，如果前缀链上没有对应的字符就返回false，如果直到最后一个字符都匹配，则返回所匹配最后一个节点的isEnd。 -
前缀匹配：判断Trie中是否有以prefix为前缀的单词。
和查找类似，只是不需要判断最后一个字符结点的isEnd，因为既然能匹配到最后一个字符，就一定有单词以prefix为前缀。
var Trie = function() {
this.children = {};
this.isEnd = false;
};
/**
* @param {string} word
* @return {void}
*/
Trie.prototype.insert = function(word) {
let trie = this.children;
for(let i of word){
if(trie[i] == null){
trie[i] = new Trie();
}
trie = trie[i];
}
trie.isEnd = true;
};
/**
* @param {string} word
* @return {boolean}
*/
Trie.prototype.search = function(word) {
let trie = this.children;
for(let i of word){
if(trie[i] == null){
return false
}
trie = trie[i];
}
return trie.isEnd;
};
/**
* @param {string} prefix
* @return {boolean}
*/
Trie.prototype.startsWith = function(prefix) {
let trie = this.children;
for(let i of prefix){
if(trie[i] == null){
return false
}
trie = trie[i];
}
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)
*/
63 全排列
- 递归
- 设置used数组，标记已经选择的元素。
- for循环横向遍历，递归纵向遍历。
- 递归出口：收集元素的数组path的length = 数组nums的length，此时到达叶子节点，找到了一个全排列，收集路径path。
- 注意：在结果数组res中放路径时，应使用 path .slice()，因为如果使用path，后续path的改变会影响存放在res的path。
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
var traversal = function(nums, used){
if(path.length == nums.length){
res.push(path.slice());
return;
}
for(let i = 0; i < nums.length; i++){
if(used[i] == 0){
path.push(nums[i]);
used[i] = 1;
traversal(nums, used);
path.pop();
used[i] = 0;
}
}
}
let used = Array(nums.length).fill(0);
let path = [];
let res = [];
traversal(nums, used);
return res;
};
64 子集
- 递归
- 设置startIndex，标记遍历开始的位置。
- for循环横向遍历，递归纵向遍历。
- 子集与全排列不同，需要记录所有的节点，而不只是叶子节点。
- 每次进入递归都要收集子集。
- 递归出口：startIndex > nums的length，此时没有元素可取了。
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
var traversal = function(nums, startIndex){
res.push(path.slice());
if(startIndex == nums.length){
return;
}
for(let i = startIndex; i < nums.length; i++){
path.push(nums[i]);
traversal(nums, i + 1);
path.pop();
}
}
let res = [];
let path = [];
traversal(nums, 0);
return res;
};
65 电话号码的字母组合
- 递归
- 定义map数组映射数字和字母。
- for循环横向遍历，字母的个数为for循环的遍历次数；递归纵向遍历，digits的长度为递归深度。
- 设置index，记录遍历到digits的第几个数字了。
- 递归出口：index = digits的length，此时到达叶子节点，收集结果。
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
var traversal = function(digits, index){
if(index == digits.length){
res.push(path.slice().join(""))
return;
}
let all = map[digits[index] - '0'];
for(let item of all){
path.push(item);
traversal(digits, index + 1);
path.pop();
}
}
let map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
let path = [];
let res = [];
if(digits.length == 0){
return res;
}
traversal(digits, 0);
return res;
};