文章目录
- 61 课程表
- 62 实现Trie（前缀树）
- 63 全排列
- 64 子集
- 65 电话号码的字母组合
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;
};
