JavaScript 刷 LeetCode 拿 offer- 栈相关题目
1. 栈是什么?
一种先进后出的数据结构;
JavaScript 没有栈的结构;可以用 array 实现栈的功能
入栈 push(x);
出栈 pop();
复制代码
2. 什么场景下用栈
所有后进先出的结构。
2.1 十进制转换为二进制:最后余数要倒叙输出才是正确二进制;
后出来的余数反而要排到前面
把余数依次入栈,然后出栈,就可以实现余数倒叙输出。
2.2 判断括号是否合法:左括号进栈,右括号出栈,栈空则合法;
越靠后的左括号,对应的右括号越靠前
左括号入栈,右括号出栈,最后栈空了就是合法的
2.3 函数调用栈:最后调用的函数,最先执行完;
最后调用的函数,最先执行完
JS 解释器使用栈来控制函数调用的顺序
3. leetcode: 20. 有效的括号
valid-parentheses
参考视频:传送门
3.1 解题思路
对于没有闭合的左括号而言,越靠后的左括号,对应的右括号越靠前
复制代码
3.2 解题步骤
新建一个栈
扫描字符串,遇左括号入栈,遇到和栈顶括号类型匹配的右括号就出栈,类型不匹配直接判定为不合法
复制代码
4. 前端与栈:JS 中的函数调用栈
4.1 后进先出
复制代码
5. LeetCode:144. 二叉树的前序遍历
学习这个题之前,要先了解下什么是二叉树·~~
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
5.1 利用栈模拟递归,改写递归
复制代码
6. 栈-总结
栈是一个后进先出的数据结构
JavaScript 没有栈的结构;可以用 array 实现栈的功能
栈常用操作:
入栈 push(x);
、出栈 pop();
、最后元素 stack[stack.length - 1]
评论