【当前无排名】挑战leetcode进入前1w名

李恒道

这题没思路
看的答案...
dfs还理解，bfs是真牛啊

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[1]).push(edge[0])
    }
    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[index];
            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
};

李恒道

前缀树题
一次过，爽！

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[index];
        if (tree[char] == undefined) {
            tree[char] = {}
        }
        tree = tree[char]
    }
    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[index];
        if (tree[char] == undefined) {
            return false
        }
        tree = tree[char]
    }
    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[index];
        if (tree[char] == undefined) {
            return false
        }
        tree = tree[char]
    }
    return true
};

李恒道

回溯，这题没手感没做出来
题解是利用swap秒的
没想到...
我一开始是想用一个数字代表位数来着，简直太复杂了

/**
 * @param {number[]} nums
 * @Return {number[][]}
 */

const swap = (nums, x, y) => {
    const temp = nums[x];
    nums[x] =nums [y]
    nums[y] = 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
递归秒了，还算简单

var subsets = function (nums) {
    const ret = []
    const dfs = (arr, index) => {
        if(index==nums.length){
            ret.push([...arr]);
            return;
        }
        arr.push(nums[index]);
        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
递归+打表秒

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[arr[x]]
        for (let index = 0; index < table.length; index++) {
            const char = table[index];
            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
递归边界秒

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[x]
        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
括号题，边界递归秒

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
来道堆栈的简单题舒缓一下心情，今日收工

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
感觉像简单题...
秒

/**
 * @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[index] = 0;
  }
  for (let index = red; index < red + white; index++) {
    nums[index] = 1;
  }
  for (let index = red + white; index < red + white + blue; index++) {
    nums[index] = 2;
  }
};

李恒道

https://leetcode.cn/problems/min-stack/submissions/562037425/?envType=study-plan-v2&envId=top-100-liked
实现题，秒了

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[this.stack.length - 1].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[this.stack.length - 1].val
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
    return this.stack[this.stack.length - 1].min
};