这题没思路
看的答案...
dfs还理解，bfs是真牛啊
```js
var canFinish = function (numCourses, prerequisites) {
const outMap = new Map()
const edgesNum = new Map()
for (let index = 0; index < numCourses; index++) {
outMap.set(index, [])
}
for (const edge of prerequisites) {
outMap.get(edge).push(edge)
}
let traverse = []
outMap.forEach(function logMapElements(value, key, map) {
if (value.length == 0) {
traverse.push(key)
}
});
const cache = new Map()
let isNotCycle = true
const dfs = (index) => {
const status = cache.get(index)
if (status == 1) {
isNotCycle = false;
return;
}
if (status == 2) {
return;
}
cache.set(index, 1)
const edges = outMap.get(index)
for (let index = 0; index < edges.length; index++) {
const edge = edges;
dfs(edge)
}
outMap.set(index, [])
cache.set(index, 2)
}
for (let index = 0; index < numCourses; index++) {
if (cache.get(index) == undefined) {
dfs(index)
}
}
return isNotCycle
};
```
前缀树题
一次过，爽！
```js
var Trie = function () {
this.tree = {}
};
/**
* @param {string} word
* @Return {void}
*/
Trie.prototype.insert = function (word) {
word = word.split("")
let tree = this.tree
for (let index = 0; index < word.length; index++) {
const char = word;
if (tree == undefined) {
tree = {}
}
tree = tree
}
tree.end = true;
};
/**
* @param {string} word
* @return {boolean}
*/
Trie.prototype.search = function (word) {
word = word.split("")
let tree = this.tree
for (let index = 0; index < word.length; index++) {
const char = word;
if (tree == undefined) {
return false
}
tree = tree
}
return tree.end == true ? true : false
};
/**
* @param {string} prefix
* @return {boolean}
*/
Trie.prototype.startsWith = function (word) {
word = word.split("")
let tree = this.tree
for (let index = 0; index < word.length; index++) {
const char = word;
if (tree == undefined) {
return false
}
tree = tree
}
return true
};
```
回溯，这题没手感没做出来
题解是利用swap秒的
没想到...
我一开始是想用一个数字代表位数来着，简直太复杂了
```js
/**
* @param {number[]} nums
* @Return {number[][]}
*/
const swap = (nums, x, y) => {
const temp = nums;
nums =nums
nums = temp
}
var permute = function (nums) {
const ret = []
const dfs = (border) => {
if (border === nums.length) {
ret.push([...nums])
return;
}
for (let index = border; index < nums.length; index++) {
swap(nums,border, index)
dfs(border + 1)
swap(nums,border, index)
}
}
dfs(0)
return ret
};
```
https://leetcode.cn/problems/subsets/submissions/562020613/?envType=study-plan-v2&envId=top-100-liked
递归秒了，还算简单
```js
var subsets = function (nums) {
const ret = []
const dfs = (arr, index) => {
if(index==nums.length){
ret.push([...arr]);
return;
}
arr.push(nums);
dfs(arr, index + 1);
arr.pop();
dfs(arr, index + 1);
}
dfs([], 0)
return ret
};
```
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/submissions/562020921/?envType=study-plan-v2&envId=top-100-liked
递归+打表秒
```js
var letterCombinations = function (digits) {
if(digits===''){
return []
}
const charTable = {
2: ['a', 'b', 'c'],
3: ['d', 'e', 'f'],
4: ['g', 'h', 'i'],
5: ['j', 'k', 'l'],
6: ['m', 'n', 'o'],
7: ['p', 'q', 'r', 's'],
8: ['t', 'u', 'v'],
9: ['w', 'x', 'y', 'z'],
}
const arr = digits.split('')
const result = []
const data = []
const dfs = (x) => {
if(x===arr.length){
result.push(data.join(""))
return
}
const table = charTable]
for (let index = 0; index < table.length; index++) {
const char = table;
data.push(char);
dfs(x + 1)
data.pop()
}
}
dfs(0)
return result
};
```
https://leetcode.cn/problems/combination-sum/submissions/562021268/?envType=study-plan-v2&envId=top-100-liked
递归边界秒
```js
var combinationSum = function (candidates, target) {
const result = [];
const dfs = (arr, sum, x) => {
if (sum === target) {
result.push([...arr])
return;
}
if (x >= candidates.length) {
return;
}
const num = candidates
let times = 0
while (sum <= target) {
dfs(arr, sum, x + 1)
times++;
sum = sum + num;
arr.push(num)
}
for (let index = 0; index < times; index++) {
arr.pop()
}
dfs(arr, sum, x + 1)
}
dfs([], 0, 0)
return result
};
```
https://leetcode.cn/problems/generate-parentheses/submissions/562021777/?envType=study-plan-v2&envId=top-100-liked
括号题，边界递归秒
```js
var generateParenthesis = function (n) {
let result = [];
const arr = []
const dfs = (l, r) => {
if (l == 0 && r == 0) {
result.push(arr.join(""))
return;
}
if (l >= 0) {
arr.push("(");
dfs(l - 1, r);
arr.pop()
}
if (r > l) {
arr.push(")");
dfs(l, r - 1);
arr.pop()
}
}
dfs(n,n)
return result
};
```
https://leetcode.cn/problems/valid-parentheses/submissions/562024935/?envType=study-plan-v2&envId=top-100-liked
来道堆栈的简单题舒缓一下心情，今日收工
```js
var isValid = function (s) {
s = s.split("")
const stack = []
for (const char of s) {
if ("})]".indexOf(char) !== -1) {
const allStr = stack.pop() + char
if('() {} []'.indexOf(allStr)==-1){
return false
}
} else {
stack.push(char)
}
}
return stack.length==0?true:false
};
```
https://leetcode.cn/problems/sort-colors/description/?envType=study-plan-v2&envId=top-100-liked
感觉像简单题...
秒
```js
/**
* @param {number[]} nums
* @Return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function (nums) {
let red = 0,
white = 0,
blue = 0;
for (const num of nums) {
if (num == 0) {
red++;
} else if (num == 1) {
white++;
} else {
blue++;
}
}
for (let index = 0; index < red; index++) {
nums = 0;
}
for (let index = red; index < red + white; index++) {
nums = 1;
}
for (let index = red + white; index < red + white + blue; index++) {
nums = 2;
}
};
```
https://leetcode.cn/problems/min-stack/submissions/562037425/?envType=study-plan-v2&envId=top-100-liked
实现题，秒了
```js
var MinStack = function () {
this.stack = [];
};
/**
* @param {number} val
* @Return {void}
*/
MinStack.prototype.push = function (val) {
const lastValue =
this.stack.length === 0
? val
: Math.min(this.stack.min, val);
this.stack.push({
val,
min: lastValue,
});
};
/**
* @return {void}
*/
MinStack.prototype.pop = function () {
this.stack.pop()
};
/**
* @return {number}
*/
MinStack.prototype.top = function () {
return this.stack.val
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function () {
return this.stack.min
};
```