乐趣区

关于leetcode:JavaScript刷LeetCode拿offer栈相关题目

jiezi

1. 栈是什么？

  • 一种先进后出的数据结构；

  • JavaScript 没有栈的构造；能够用 array 实现栈的性能

    • 入栈 push(x);
    • 出栈 pop();
const stack = [];

// 入栈 
stack.push(1);
stack.push(2);

// 出栈
const item1 = stack.pop();
const item2 = stack.pop();

2. 什么场景下用栈

所有后进先出的构造。

2.1 十进制转换为二进制：最初余数要顺叙输入才是正确二进制；

  • 后进去的余数反而要排到后面
  • 把余数顺次入栈，而后出栈，就能够实现余数顺叙输入。

2.2 判断括号是否非法：左括号进栈，右括号出栈，栈空则非法；

  • 越靠后的左括号，对应的右括号越靠前
  • 左括号入栈，右括号出栈，最初栈空了就是非法的

2.3 函数调用栈：最初调用的函数，最先执行完；

  • 最初调用的函数，最先执行完
  • JS 解释器应用栈来管制函数调用的程序

3. leetcode: 20. 无效的括号

valid-parentheses

参考视频：传送门

3.1 解题思路

对于没有闭合的左括号而言，越靠后的左括号，对应的右括号越靠前 

 输出："{[]}"
输入：true

3.2 解题步骤

  • 新建一个栈
  • 扫描字符串，遇左括号入栈，遇到和栈顶括号类型匹配的右括号就出栈，类型不匹配间接断定为不非法 
/** * @param {string} s
 * @return {boolean} */
var isValid = function (s) {if (s.length % 2 === 1) {return false}
    const stack = [];
    for (let i = 0; i < s.length; i += 1) {const c = s[i];
        if (c === '(' || c === '{' || c === '[') {stack.push(c)
        } else {const t = stack[stack.length - 1];
            if ((t === '(' && c === ')') ||
                (t === '{' && c === '}') ||
                (t === '[' && c === ']')
            ) {stack.pop();
            } else {return false;}
        }
    }
    return stack.length === 0;
};

4. 前端与栈：JS 中的函数调用栈

4.1 后进先出 

    const func1 = () => {func2();
    };
    const func2 = () => {func3();
    };
    const func3 = () => {};

    func1();

5. LeetCode：144. 二叉树的前序遍历

学习这个题之前，要先理解下什么是二叉树·～～

进阶： 递归算法很简略，你能够通过迭代算法实现吗？

5.1 利用栈模仿递归，改写递归 

/** * 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 preorderTraversal = function (root) {const res = [];
    const stack = [];
    if (root) stack.push(root)
    while (stack.length) {const n = stack.pop();
        res.push(n.val)
        if (n.right) stack.push(n.right)
        if (n.left) stack.push(n.left)
    }
    return res
};

6. 栈 - 总结

  • 栈是一个后进先出的数据结构
  • JavaScript 没有栈的构造；能够用 array 实现栈的性能
  • 栈罕用操作： 入栈 push(x);、 出栈 pop();、 最初元素 stack[stack.length - 1]
退出移动版