写点什么

JavaScript 刷 LeetCode 拿 offer- 栈相关题目

作者:js2030code
  • 2023-02-20
    浙江
  • 本文字数:1329 字

    阅读完需:约 4 分钟

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]


用户头像

js2030code

关注

还未添加个人签名 2022-09-14 加入

还未添加个人简介

评论

发布
暂无评论
JavaScript刷LeetCode拿offer-栈相关题目_JavaScript_js2030code_InfoQ写作社区