LeetCode20、括号匹配-一一网

前言

昨天因为生病了、没有更新、应广大粉丝催更要求，今天你们要的力扣刷刷来啦。

栈的前世今生

栈是什么：

是一个后进先出的数据结构只能在一端（栈顶）增加和删除
push入栈、pop出栈

//数组模拟栈
const stack = [];
stack.push(1);
stack.push(2);
const item = stack.pop()
const item1 = stack.pop()
//1、2依次进栈、然后2先出栈、典型的先进后出
复制代码

数组的push、pop方法

//push方法：向数组末尾添加一个或者更多的元素，返回新的长度
//可以接受任意个数量的参数
//返回值：返回修改后数组的长度
源码实现：
var arr =[1,2,3,4]
Array.prototype.myPush =function(){
    for(var i =0;i<arguments.length;i++){
        this[this.length]=arguments[i]
    }
    return this.length
}
myPush(arr)
//pop方法：从数组的末尾移除最后一项，减少数组的length值，并返回移除的项
//返回值：从数组中删除的元素(数组为空的时候返回undefined)
源码实现：
var arr1 =[1,2,3,4]
Array.prototype.myPop=function (){
    var result =null;
    if(this.length===0){
        return undefined;
    }
    result = this[this.length-1];
    this.length=this.length-1;
    return result;
}
复制代码

栈的应用场景

需要后进先出的场景
- 十进制转二进制、判断字符串括号是否有效、函数调用堆栈

LeetCode20、括号匹配

给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：
输入：s = "()"
输出：true
复制代码

示例 2：
输入：s = "()[]{}"
输出：true
复制代码

示例 3：
输入：s = "(]"
输出：false
复制代码

解题思路：

对于没有闭合的左括号而言，越靠后的左括号，对应的有括号越靠前
满足后进先出，可以用栈
思路：
- 新建一个栈
- 扫描字符串、遇到左括号就入栈，遇到和栈顶（最后一位推入栈中的括号）括号类型匹配的右括号就出栈，类型不匹配就直接判定不合法。
- 最后栈空了就合法，否则不合法

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    if (s.length % 2 === 1) {//如果是奇数肯定false
        return false;
    }
    const stack = [];
    for (let i = 0; i < s.length; i += 1) {
        //遍历字符串,并且赋值给c
        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;//如果栈空了会返回true
};
//时间复杂度和空间复杂度都是O（n）
复制代码