qulingyuan / leetcode_note Goto Github PK

View Code? Open in Web Editor NEW

1.0 1.0 0.0 2 KB

LeetCode

leetcode_note's People

Stargazers

Watchers

leetcode_note's Issues

76. 最小覆盖子串

解题思路

先找出所有的包含T的字串。

找出长度最小的那个字串，返回即可。

解题步骤

用双指针维护一个滑动窗口。

移动右指针，找到包含T的字串，移动左指针，尽量减少包含T的字串的长度。

循环上述过程，找到包含T的最小字串。

代码实现

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let left = 0;
    let right = 0;
    const need = new Map();
    for(let c of t){
        need.set(c,need.has(c) ? need.get(c) + 1 : 1);
    }
    let needType = need.size;
    let result = "";
    while(right < s.length){
        const c = s[right];
        if(need.has(c)){
            need.set(c,need.get(c) - 1);
            if(need.get(c) === 0) needType -= 1;
        }
        while(needType === 0){
            const newResult = s.substring(left,right + 1);
            if(!result || newResult.length < result.length) result = newResult;
            const c2 = s[left];
            if(need.has(c2)){
                need.set(c2,need.get(c2) + 1);
                if(need.get(c2) === 1) needType += 1;
            }
            left++;
        }
        right++;
    }
    return result;
};

104. 二叉树的最大深度

解题思路

求最大深度，考虑使用深度优先遍历。

在深度优先遍历的过程中，记录每个节点所在的层级，找出最大的层级即可。

解题步骤

新建一个变量，记录最大深度。

深度优先遍历整棵树，并记录每个节点的层级，同时不断刷新最大深度这个变量。

遍历结束返回最大深度这个变量。

代码：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    let res = 0;
    const dfs = (n,level)=>{
        if(!n) return;
        if(!n.left&&!n.right){
        res = Math.max(res,level);
        }
        dfs(n.left,level + 1);
        dfs(n.right,level + 1);
    }
    dfs(root,1);
    return res;
};

65. 有效数字

解题思路

状态机

解题步骤

构建一个表示状态的图。

遍历字符串，并沿着图走，如果到了某个节点无路可走就返回false。

遍历结束，如走到3/5/6，则返回true，否则返回false。

代码实现

/**
 * @param {string} s
 * @return {boolean}
 */
var isNumber = function(s) {
    const graph = {
        0: {'blank': 0,'sign':1,'.':2,'digit':6},
        1: {'digit':6,'.':2},
        2: {'digit':3},
        3: {'digit':3,'e':4},
        4: {'digit':5,'sign':7},
        5: {'digit':5},
        6: {'digit':6,'.':3,'e':4},
        7: {'digit':5}
    }
    let state = 0;
    for(c of s.toLowerCase().trim()){
        if(c >= '0' && c <= '9'){
            c = 'digit';
        }else if(c === ' '){
            c = 'blank';
        }else if(c === '+' || c === '-'){
            c = 'sign';
        }
        state = graph[state][c];
        if(state === undefined){
            return false;
        }
    }
    if(state === 3 || state === 5 || state === 6){
        return true;
    }
    return false;
};

211. 添加与搜索单词 - 数据结构设计

解题思路

由于有‘.’的出现，所以无法进行常规匹配，此时想到使用字典树。
用 count 表示以此节点结束的单词的个数。count === 0 标志来表示当前的字符是否为一个单词的结束。

解题步骤

trie 树的数据结构
add和search方法
为了debug, 写了display方法

代码实现

184ms

代码

/**
 * Initialize your data structure here.
 */

function Trie(val){
    this.val = val;
    this.count = 0;
    this.nextNodes = [];
}

var WordDictionary = function() {
  this.root = new Trie(null);  
};

WordDictionary.prototype.display = function(){
    console.log('----')
    const loop = (node) => {
        console.log(`${node.val}, ${node.count}`);
        node.nextNodes.forEach(n => loop(n));
     }
     loop(this.root);
}

/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
    const loop = (node, i) => {
        if ( i >= word.length) {
            node.count++;
            return;
        }
        const letter = word[i];
        for(let j = 0; j < node.nextNodes.length; j++){
            if (node.nextNodes[j].val === letter){
                loop(node.nextNodes[j], i + 1);
                return;
            }
        }
        const n = new Trie(letter);
        node.nextNodes.push(n);
        loop(n, i + 1);        
    }
    loop(this.root, 0);
};

/** 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function(word) {
    const loop = (node, i) => {
        if (i >= word.length) {
            if(word === 'an.') {
                console.log("!!", node, i)
            }
            if (node.count !== 0){
                return true;
            };
            return false;
        }
        const letter = word[i];
        let flag = false;
        for(let j = 0; j < node.nextNodes.length; j++){
            if (letter === '.'){
                if (flag) return true;
                flag = flag || loop(node.nextNodes[j], i + 1);
            } else if (node.nextNodes[j].val == letter){
                return loop(node.nextNodes[j], i + 1);
            } 
        }
        return flag;
    }
    return loop(this.root, 0);   
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * var obj = new WordDictionary()
 * obj.addWord(word)
 * var param_2 = obj.search(word)
 */

331. 验证二叉树的前序序列化

思路

如输入： "9,3,4,#,#,1,#,#,2,#,6,#,#" ，当遇到 x,#,# 的时候，就把它变为 #。

模拟一遍过程：

[9,3,4,#,#] => [9,3,#]，继续
[9,3,#,1,#,#] => [9,3,#,#] => [9,#] ，继续
[9,#2,#,6,#,#] => [9,#,2,#,#] => [9,#,#] => [#]，结束

作者：fuxuemingzhu
链接：https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/solution/pai-an-jiao-jue-de-liang-chong-jie-fa-zh-66nt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码

/**
 * @param {string} preorder
 * @return {boolean}
 */
var isValidSerialization = function(preorder) {
    const order = preorder.split(','); 
    const stack = [];
    for (let i = 0; i < order.length; i++ ) {
        stack.push(order[i]);
        while(stack.length >= 3 && stack[stack.length - 1] === '#' && stack[stack.length - 2] === '#' && stack[stack.length - 3] !== '#') {
            stack[stack.length - 3] = '#';
            stack.pop();
            stack.pop();
        }
        
    }
    return stack.length === 1 && stack[0] === '#';
};

83.删除链表中重复元素

83_删除排序链表中的重复元素

解题思路

因为链表是有序的，所以重复元素一定相邻。
遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值。

解题步骤

遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值。
遍历结束后，返回原链表的头部。

代码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    let p = head;
    while(p && p.next){
        if(p.val === p.next.val){
            p.next = p.next.next;
        }else{
            p = p.next;
        }
    }
    return head;
};

198. 打家劫舍

解题思路

f(k)表示前k个房屋中能偷窃到的最大数额。

Ak表示第k个房屋的钱数。

f(k) = max(f(k-2) +Ak,f(k-1))

解题步骤

定义子问题：f(k) = max(f(k-2) +Ak,f(k-1))

反复执行：从2循环到n，执行上述公式。

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if(nums.length === 0) return 0;
    const dp = [0,nums[0]];
    for(let i = 2; i <= nums.length; i++ ){
        dp[i] = Math.max(dp[i-2]+nums[i-1],dp[i-1]);
    }
    return dp[nums.length];
};

可以不用数组，只用两个变量记录即可。可优化时间复杂度为O(1):

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if(nums.length === 0) return 0;
    let dp0 = 0;
    let dp1 = nums[0];
    for(let i = 2; i <= nums.length; i++ ){
        const dp2 = Math.max(dp0+nums[i-1],dp1);
        dp0 = dp1;
        dp1 = dp2;
    }
    return dp1;
};

1.两数之和

LeetCode_1_两数之和

解题思路

把 nums 想象成相亲者。

把 target 想象成匹配条件。

用字典建立一个婚姻介绍所，存储相亲者的数字和下标。

解题步骤

新建一个字典作为婚姻介绍所。

nums 里的值，逐个来介绍所找对象，没有合适的就先登记着，有合适的就牵手成功。

代码实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const map = new Map();
    for(let i = 0;i<nums.length;i++){
        const n = nums[i];
        const n2 = target - nums[i];
        if(map.has(n2)){
            return [map.get(n2),i];
        }else{
            map.set(n,i);
        }
    }
};

3.无重复字符的最长子串

LeetCode_03_无重复字符的最长子串

解题思路

先找出所有的不包含重复字符的字串。

找出长度最大的那个字串，返回其长度即可。

解题步骤

用双指针维护一个滑动窗口，用来剪切字串。

不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位。

过程中，记录所有窗口的长度，并返回最大值。

代码实现

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let leftp = 0;
    let result = 0;
    const map = new Map();
    for(let i = 0; i < s.length; i++){
        if(map.has(s[i]) && map.get(s[i]) >= leftp){
            leftp = map.get(s[i]) + 1;
        }
        result = Math.max(result, i - leftp + 1);
        map.set(s[i],i);
    }
    return result;
};

111. 二叉树的最小深度

解题思路

求最小深度，考虑使用广度优先遍历。

在广度优先遍历过程中，遇到叶子节点，停止遍历，返回节点层级。

解题步骤

广度优先遍历整棵树，并记录每个节点的层级。

遇到叶子节点，返回节点层级，停止遍历。

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if(!root) return 0;
    const queue = [[root,1]];
    while(queue.length>0){
        const [n,level] = queue.shift();
        if(!n.left && !n.right) return level;
        n.left && queue.push([n.left,level+1]);
        n.right && queue.push([n.right,level+1]);
    }
};

227. 基本计算器 II

双栈思路

为什么用栈？因为算数运算符优先级，问题是包含子问题的。
优先级高的先计算，栈顶元素优先级高 > 即将入栈的op，弹栈运算直到优先级小于或者不存在元素为止。
即存ops的栈是不严格的单调递增。
这样也保证最后计算的时候从右往左算不会出问题。

双栈代码

/**
 * @param {string} s
 * @return {number}
 */

function level(c) { 
    switch (c) { 
       // !!!
        case '@': return 0;
        case '+':
        case '-': return 1; 
        case '*':
        case '/': return 2;
        default: return -1;
    }
}
function cal(a, op, b){
    switch(op) {
        case '+': return a + b; 
        case '-': return a - b; 
        case '*': return a * b; 
        case '/': return Math.floor(a / b);
    }
    return 0;
}
var calculate = function(s) {
    const stack1 = [];
    // 不严格递增
    const stack2 = [];
    let i = 0;
    s += '@';
    while(i < s.length){
        if (s[i] === ' ') {
            i++;
            continue;
        }
        if (level(s[i]) === -1) {
            let num = +s[i];
            let j = i + 1;
            while(s[j] !== ' ' && +s[j] >= 0 && +s[j] <= 9 && j < s.length){
                num = num * 10 + (+s[j]);
                j++;
            }
            console.log(num);
            stack1.push(num); 
            i = j;
        } else {
            while (stack2.length !== 0  && level(stack2[stack2.length - 1]) >=  level(s[i])){
                let b = stack1.pop();
                let a = stack1.pop(); 
                stack1.push(cal(a, stack2.pop(), b));
            }
            stack2.push(s[i]);
            i++;
        }   
    }
    return stack1[0];
};

1110.删点成林

210. 课程表 II

解题思路

删掉节点意味着要找到parent，把 parent.left 置为 null。深度遍历和层序遍历都可以。
每删除一个点，这个节点的子节点是森林的根节点。
！但是必须要在把所有的关系都删结束之后，再把执行上面这步。
删除头节点的操作会不一样，为了统一加一个哨兵节点（假的root）可以统一处理。

解题步骤

更新关系
把待删节点放到forest里面
遍历forest找到所有的树放到结果里面
如果root不被删除，它也仍然是一颗树，把root放到返回结果里

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number[]} to_delete
 * @return {TreeNode[]}
 */
var delNodes = function(root, to_delete) {
    const pNode = new TreeNode(-1, root, null);
    let forest = [];
    let arr = [pNode];
    const getChildren = (node) => {
        const rs = [];
        if (node.left) {
            rs.push(node.left);
        }
        if (node.right) {
            rs.push(node.right);
        }
        return rs;
    }
    while(arr.length !== 0){
        const node = arr.pop();
        if (node.left) {
            arr.push(node.left);
            if (to_delete.indexOf(node.left.val) !== -1){
                forest.push(node.left);
                node.left = null;
            }
        }
        if (node.right) {
            arr.push(node.right);
            if (to_delete.indexOf(node.right.val) !== -1){
                forest.push(node.right);
                node.right = null;
            }
        }
    }
    let result = [];
    for(let i = 0; i < forest.length; i++){
        result = [...result, ...getChildren(forest[i])];
    }    
    if (to_delete.indexOf(root.val) === -1) {
        result.push(root);
    }
    return result;
};

349.两个数组的交集

349_两个数组的交集

解题思路

求交集且无序唯一，符合集合的特性，故使用集合。

解题步骤

用集合对 nums1 去重。
遍历 nums1，筛选出 nums2 也包含的值。

代码实现

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    return [...new Set(nums1)].filter(item=>nums2.includes(item));
};

1022. 从根到叶的二进制数之和

解题思路

对于一条路径，递归返回的时候也就是从叶子节点返回到根节点的时候，恰好可以得到，这个节点对于结果的贡献值是多少。

解题步骤

递归函数loop，A的子节点是 B 和 C
result =[...loop(B), loop(c)]，，result 是 A节点在所有路径里面出现的位置（指数）

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumRootToLeaf = function(root) {
    const powerArr = [1];
    const nThPowerOf2 = (times) => {
        let result = 1;
        let tmp = times;
        while (tmp--){
            result *= 2;
        }
        powerArr[times] = result;
        return result;
    }
    let result = 0;
    const loop = (node) => {
        if(!node) return [];

        if (!node.left && !node.right){
            result += node.val;
            return  [1];
        }
        
        if (node.left || node.right) {
            const timesArr = [...loop(node.left), ...loop(node.right)];
            for (let i = 0;i < timesArr.length; i++) {
                const times = timesArr[i];
                result += node.val * nThPowerOf2(times);
                timesArr[i] = times + 1;
            }
            return timesArr;
        }
    }
    loop(root);
    console.log(powerArr);
    return result;
};

94. 二叉树的中序遍历

递归版：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    const res = [];
    const inorder = (n)=>{
        if(!n) return;
        inorder(n.left);
        res.push(n.val);
        inorder(n.right);
    }
    inorder(root);
    return res;
};

迭代版

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    const res = [];
    const stack = [];
    let p = root;
    while(stack.length || p){
        while(p){
        stack.push(p);
        p = p.left;
    }
        const n = stack.pop();
        res.push(n.val);
        p = n.right;
    }
    return res;
};

933.最近的请求次数

解题步骤

有新请求就入队，3000ms前发出的请求出队。
队列的长度就是最近请求次数。

代码实现：

var RecentCounter = function() { //为该类的构造函数
    this.q = [];
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) { //属性和方法定义在构造函数的prototype对象之上
    this.q.push(t);
    while(this.q[0] < t - 3000){
        this.q.shift();
    }
    return this.q.length;
};

329. 矩阵中的最长递增路径

思路

不重不漏得把所有能建立关系的点之间连起来
求出最长的路径

步骤

把二维数组由数字元素换成node。

node1.val = 1;
node2.val = 2;
node1.next = node2;
node2.pre = node1;

建立关系。遍历二维数组，不重不漏。以matrix[i][j]为起点，看右边的节点或者下面的节点可不可以建立联系。
node.count这个值的维护。每次建立连接之后，以node.pre更新父节点的count值。（类似于计算最短截止日期，或者说是动态规划的子问题）。用到了回溯。
遍历所有节点找到最大的count值

code

/**
 * @param {number[][]} matrix
 * @return {number}
 */

function Node(val) {
    this.val = val;
    this.next = [];
    this.pre = []; 
    this.count = 1;
}

const connect = (current, addon) => {
    current.next.push(addon);
    addon.pre.push(current);
    const loop = (node, i) => {
            if (addon.count + i > node.count) {
                node.count = addon.count + i;
                node.pre.forEach((n) => {
                    loop(n, i + 1);
                });
            }
    }
    loop(current, 1);
}

var longestIncreasingPath = function(matrix) {
    if (matrix.length === 1 && (matrix[0] && matrix[0].length) === 1){
        return 1;
    }

    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++){
           matrix[i][j] = new Node(matrix[i][j]);
        }
    }


    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            if (matrix[i + 1] && matrix[i + 1][j]){
                if (matrix[i + 1][j].val < matrix[i][j].val) {
                    connect(matrix[i + 1][j], matrix[i][j]);
                }
                if (matrix[i][j].val < matrix[i + 1][j].val) {
                    connect(matrix[i][j], matrix[i + 1][j]);
                }   
            }
            if (matrix[i] && matrix[i][j + 1]){
                if (matrix[i][j + 1].val < matrix[i][j].val) {
                    connect(matrix[i][j + 1], matrix[i][j]);
                }
                if (matrix[i][j].val < matrix[i][j + 1].val) {
                    connect(matrix[i][j],matrix[i][j + 1]);
                }
            }
        }
    }

    let result = 1;
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            result = matrix[i][j].count > result? matrix[i][j].count : result;
        }
    }
    return result;
};

102. 二叉树的层序遍历

解题思路

层序遍历顺序就是广度优先遍历。

不过在遍历时候需要记录当前节点所处层级，方便将其添加到不同的数组中。

解题步骤

广度优先遍历二叉树。

遍历过程中，记录每个节点的层级，并将其添加到不同的数组中。

代码：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root) return [];
    const queue = [[root,0]];
    const res = [];
    while(queue.length){
        const [n,level] = queue.shift();
        if(!res[level]){
            res.push([n.val]);
        }else {
            res[level].push(n.val);
        }
        n.left && queue.push([n.left,level+1]);
        n.right && queue.push([n.right,level+1]);
    }
    return res;
};

112. 路径总和

解题思路

在深度优先遍历的过程中，记录当前路径的节点值的和。

在叶子节点处，判断当前路径的节点值的和是否等于目标值。

解题步骤

深度优先遍历二叉树，在叶子节点处，判断当前路径的节点值的和是否等于目标值，是就返回true。

遍历结束，如果没有匹配，就返回false。

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
    if(!root) return false;
    let res = false;
    const dfs = (n,s)=>{
        if(!n.left && !n.right && s === targetSum){
            res = true;
        }
        if(n.left) dfs(n.left,s + n.left.val);
        if(n.right) dfs(n.right,s + n.right.val);
    };
    dfs(root,root.val);
    return res;
};

70. 爬楼梯

解题思路

爬到第 n 阶可以在第 n-1阶爬1个台阶，或者在n-2阶爬2个台阶。

F(n) = F(n-1) + F(n-2)

解题步骤

定义子问题：F(n) = F(n-1) + F(n-2)。

反复执行：从2循环到n，执行上述公式。

代码实现

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if(n < 2) return 1;
    const dp = [1,1];
    for(let i = 2; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
};

可以不用数组，只用两个变量记录即可。可优化时间复杂度为O(1):

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if(n < 2) return 1;
    let dp0 = 1;
    let dp1 = 1;
    for(let i = 2; i <= n; i++){
        const temp = dp0;
        dp0 = dp1;
        dp1 = dp1 + temp;
    }
    return dp1;
};

145. 二叉树的后序遍历

思路

用栈模拟递归

实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// var postorderTraversal = function(root) {
//     const result = [];
//     const loop = (node) => {
//         if (!node) return;
//         if (node.left) loop(node.left);
//         if (node.right) loop(node.right);
//         result.push(node.val);
//     }
//     loop(root)
//     return result;
// };

var postorderTraversal = function(root) {
    if (!root) return [];
    const stack1 = [root];
    const stack2 = [0];
    const result = [];
   while(stack1.length !== 0){
       const node = stack1[stack1.length - 1];
       const status = stack2[stack2.length - 1];
       switch(status) {
           case 0: 
             stack2[stack2.length - 1] = 1;
             if (node.left) {
                 stack1.push(node.left);
                 stack2.push(0);
             }
             break;
           case 1:
             stack2[stack2.length - 1] = 2;
             if (node.right) {
                 stack1.push(node.right);
                 stack2.push(0);
             }
             break;
            case 2:
              result.push(node.val);
              stack1.pop();
              stack2.pop();
              break;
            default:
             break; 
       }
   }
   return result;
};

332. 重新安排行程

思路

欧拉图

这种「一笔画」问题与欧拉图或者半欧拉图有着紧密的联系，下面给出定义：

通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路。
通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路。
具有欧拉回路的无向图称为欧拉图。
具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图。

判别这张图是否是欧拉图或者半欧拉图

如果没有保证至少存在一种合理的路径，我们需要判别这张图是否是欧拉图或者半欧拉图，具体地：

对于无向图 G，G 是欧拉图当且仅当 G 是连通的且没有奇度顶点。
对于无向图 G，G 是半欧拉图当且仅当 G 是连通的且 G 中恰有 2 个奇度顶点。
对于有向图 G，G 是欧拉图当且仅当 G 的所有顶点属于同一个强连通分量且每个顶点的入度和出度相同。
对于有向图 G，G 是半欧拉图当且仅当 G 的所有顶点属于同一个强连通分量且
- 恰有一个顶点的出度与入度差为 1；
- 恰有一个顶点的入度与出度差为 1；
- 所有其他顶点的入度和出度相同。

Hierholzer 算法

Hierholzer 算法用于在连通图中寻找欧拉路径，其流程如下：

从起点出发，进行深度优先搜索。
每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边。
如果没有可移动的路径，则将所在节点加入到栈中，并返回。

当我们顺序地考虑该问题时，我们也许很难解决该问题，因为我们无法判断当前节点的哪一个分支是「死胡同」分支。

不妨倒过来思考。我们注意到只有那个入度与出度差为 1 的节点会导致死胡同。而该节点必然是最后一个遍历到的节点。我们可以改变入栈的规则，当我们遍历完一个节点所连的所有节点后，我们才将该节点入栈（即逆序入栈）。

对于当前节点而言，从它的每一个非「死胡同」分支出发进行深度优先搜索，都将会搜回到当前节点。 而从它的「死胡同」分支出发进行深度优先搜索将不会搜回到当前节点。也就是说当前节点的死胡同分支将会优先于其他非「死胡同」分支入栈。

这样就能保证我们可以「一笔画」地走完所有边，最终的栈中逆序地保存了「一笔画」的结果。我们只要将栈中的内容反转，即可得到答案。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/reconstruct-itinerary/solution/zhong-xin-an-pai-xing-cheng-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

按照贪心的方式走，如果走到一个点，发现无法继续走了，并且还有某条边没有走过。则说明之前某一个分岔点上走错了，提前进入了一条无法回头的路。应该先走其它边，最后再走这一条无法回头的路。

把这段已知的无法回头的路去掉，则是一个更小的图。我们假想对这个小的图如何走，起点还是和原来一样，终点必然是刚刚的分岔点（因为分岔点不是终点，其原来的度数原来为偶数，去掉一条边后度数为奇数。）。在这个小的图上得到自然排序最小的答案后，再在最后添加上刚刚去掉的那一段，则是大图上的结果。

这里的逆序添加到结果集确实是最点睛的地方，贪心的情况下可能寻找不了欧拉路径。用Hierholzer 算法分析，入度大于出度的节点必然会第一个添加到结果集，再推广一下来看，也就是Hierholzer 算法第三条加入数组的次序恰好和欧拉回路是倒转的，reverse就行了。

代码

/**
 * @param {string[][]} tickets
 * @return {string[]}
 */



const Node = function(val){
    this.val = val;
    this.next = [];
} 

var findItinerary = function(tickets) {
    const nodeMap = {};
    const result = [];

    const getNodeOrNewOne = (key) => {
        if (!nodeMap[key]) {
            const node = new Node(key);
            nodeMap[key] = node;
        }
        return nodeMap[key];
    }; 


    for(let i = 0; i < tickets.length; i++){
        const relation = tickets[i];
        getNodeOrNewOne(relation[0]);
        getNodeOrNewOne(relation[1]);
        nodeMap[relation[0]].next.push(relation[1]);
        // lexicographical order
        nodeMap[relation[0]].next.sort();
    }

    const loop = (node) => {
        while(node.next.length !== 0) {
            const nextKey = node.next.shift();
            loop(nodeMap[nextKey]);
        }
        result.push(node.val);
    };

    loop(nodeMap['JFK']);
    return result.reverse();
};

210.课程表2

210. 课程表 II

解题思路

#1 的基础上，有限制条件的部分，拓扑排序次序。其他的随便加后面就好

解题步骤

略

代码实现

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */

var findOrder = function(numCourses, prerequisites) {
    function Node(v) {
        this.value = v;
        this.pre = [];
        this.state = '';
    }

    const courseMap = {};
    for (let i = 0; i < prerequisites.length; i++) {
        // course need pre to be done
        let cN = prerequisites[i][0], pN = prerequisites[i][1];

        let course, pre;
        if (courseMap[cN]) {
            course = courseMap[cN];
        } else {
            course = new Node(cN);
            courseMap[cN] = course;
        }
         if (courseMap[pN]) {
            pre = courseMap[pN];
        } else {
            pre = new Node(pN);
            courseMap[pN] = pre;
        }
        course.pre.push(pre);
    }
    const result = [];
    const courseSortArr = new Array(numCourses).fill(false);
    const canToposort = (node) => {
        node.state = 'ing';
        for(let i = 0; i < node.pre.length; i++) {
            if (node.pre[i].state === 'ing') {
                return false;
            }
            if(node.pre[i].state === '' && !canToposort(node.pre[i])){
                return false;
            }
        }
        node.state = 'solve';
        result.push(node.value);
        courseSortArr[node.value] = true;
        return true;    
    }

    for (let k in courseMap) {　
        if (courseMap[k].state === 'solved') continue;

        if (courseMap[k].state === '' && !canToposort(courseMap[k])) {
            return [];
        }
    }

    // 有条件限制的已经拍完序了
    if (result.length === numCourses) {
        return result;
    }
    
    for (let i = 0; i < numCourses; i++){
        if (courseSortArr[i] === false) {
            result.push(i);
        }
    }

    return result;
};

207.课程表

解题思路

某课程是另一课程的先决条件 =>

node1.pre = node2
node2.pre = node3
逻辑上 
node1.pre 也会包括 node3
这个如果用图来理解，会比较简单（和并查集，其实还不一样，原因略）

拓扑排序可以判断此课程安排图是否是有向无环图(DAG)。关键就在拓扑排序。

遍历可以用深度优先或者是广度优先，我用的深度优先。

解题步骤

先构筑完图，知道所有的关系
判断图里面存不存在环 => 用拓扑排序遍历节点，尝试去给一个解，如果中途遇到环了就终止
所有节点都可以被排序，就代表成功了

代码实现

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
    function Node(v) {
        this.value = v;
        this.pre = [];
        this.state = '';
    }

    const courseMap = {};
    for (let i = 0; i < prerequisites.length; i++) {
        // course need pre to be done
        let cN = prerequisites[i][0], pN = prerequisites[i][1];

        let course, pre;
        if (courseMap[cN]) {
            course = courseMap[cN];
        } else {
            course = new Node(cN);
            courseMap[cN] = course;
        }
         if (courseMap[pN]) {
            pre = courseMap[pN];
        } else {
            pre = new Node(pN);
            courseMap[pN] = pre;
        }
        course.pre.push(pre);
    }

    const canToposort = (node) => {
        node.state = 'ing';
        for(let i = 0; i < node.pre.length; i++) {
            if (node.pre[i].state === 'ing') {
                return false;
            }
            if(node.pre[i].state === '' && !canToposort(node.pre[i])){
                return false;
            }
        }
        node.state = 'solve';
        return true;    
    }

    for (let k in courseMap) {　
        if (courseMap[k].state === 'solved') continue;

        if (courseMap[k].state === '' && !canToposort(courseMap[k])) {
            return false;
        }
    }
    return true;
};

1021. 删除最外层的括号

思路

用计数的方式模拟栈的思维

code

/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function(s) {
    const pri = [];
    for (let i = 0, pre = 0, cnt = 0; i< s.length; i++){
        if(s[i] === '(') {
            cnt++;
        } else if (s[i] === ')'){
            cnt--;
        }
        if (cnt === 0) {
            pri.push(s.substr(pre + 1, i - pre - 1));
            pre = i + 1;
        }
    }
    return pri.join('');
};

141.环形链表

141_环形链表

解题思路

两个人在圆形操场上的起点同时起跑，速度快的人一定会超过速度慢的人一圈。
用一快一慢两个指针遍历链表，如果指针能够相逢，那么链表就有环。

解题步骤

用一快一慢两个指针遍历链表，如果指针能够相逢，就返回 true。
遍历结束后，还没有相逢就返回 false。

代码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    p1 = head;
    p2 = head;
    while(p1 && p2 && p2.next){
        p1 = p1.next;
        p2 = p2.next.next;
        if(p1 === p2){
            return true;
        }
    }
    return false;
};

257. 二叉树的所有路径

思路

递归找找到root到叶子节点的路径

步骤

路径以参数传递，递归出口的时候放到result里面。
递归出口是 node && !node.left && !node.right

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function(root) {
    const result = [];
    const loop = (node, pre) => {
        if (node && !node.left && !node.right){
            pre.push(node.val);
            result.push(pre);
            return ;
        }
        if (node) {
            loop(node.left, [...pre, node.val]);
            loop(node.right, [...pre, node.val])
        }
    };
    loop(root, []);
    return result.map(arr => arr.join('->')); 
};

206.反转链表

206_反转链表

解题思路

反转两个节点：将 n+1 的 next 指向 n。
反转多个节点：双指针遍历链表，重复上述操作。

解题步骤

双指针一前一后遍历链表
反转双指针

代码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let curr = head;
    let prev = null;
    while(curr!==null){
        const tempNext = curr.next;
        curr.next = prev;
        prev = curr;
        curr = tempNext;
    }
    return prev;
};

qulingyuan / leetcode_note Goto Github PK

leetcode_note's People

Stargazers

Watchers

leetcode_note's Issues

解题思路

解题步骤

代码实现

解题思路

解题步骤

代码：

解题思路

解题步骤

代码实现

解题思路

解题步骤

代码实现

184ms

思路

代码

解题思路

解题步骤

代码实现

解题思路

解题步骤

代码实现

解题思路

解题步骤

代码实现

解题思路

解题步骤

代码实现

解题思路

解题步骤

双栈思路

双栈代码

解题思路

解题步骤

代码实现

解题思路

解题步骤

代码实现

解题思路

解题步骤

代码

解题步骤

思路

步骤

code

解题思路

解题步骤

解题思路

解题步骤

代码实现

解题思路

解题步骤

代码实现

思路

实现

思路

代码

解题思路

解题步骤

代码实现

解题思路

解题步骤

代码实现

思路

code

解题思路

解题步骤

代码实现

思路

步骤

代码

解题思路

解题步骤

代码实现

Recommend Projects

Recommend Topics