每天一道算法题(JavaScript篇):有效的括号

题目描述:给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/valid-parentheses

💯有效的括号

🌕栈的描述 🌙题目解析 ⭐代码实现

🌕栈的描述

1️⃣栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进⬇后出⬆的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
在这里插入图片描述

2️⃣JavaScript中没有栈,但是可以用Array实现栈的功能,栈中数组长度减一即为栈尾元素,也就是最后进入的那个元素,最先出去的那个元素
3️⃣JavaScript中对栈的操作一般会使用到

    push()方法,将元素压入栈顶 pop()方法,从栈顶弹出(删除)元素,并返回该元素 peek()方法,返回栈顶元素,不删除 clear()方法,清空栈 length拿到栈中元素数量

🌙题目解析

部分括号示例
在这里插入图片描述

根据上面的示例可以看出,对于没有闭合的左括号来说,越靠后的左括号对应的右括号越靠前。一前一后就可以考虑到使用栈来解决这个问题。

确定了用栈来解决问题的话,首先肯定是先对拿到的字符串进行扫描,如果遇到左括号就push入栈,遇到右括号就判断栈顶元素是否为和其匹配的左括号,是就出栈,否就判断为无效。

这时候是不是结束了?非也!假如最后一个元素是左括号怎么办?上面的逻辑还会将其入栈,所以最后还要判断以下栈是否为空,若最后栈为空,括号才有效

其实大家根据常识就能知道,一个有效的括号必然是一个左括号一个右括号搭配的,假如在一开始拿到字符串后就对长度进行判断,为奇数直接判定无效,就可以省略掉后面的代码执行,提高效率

⭐代码实现

题目描述:给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

    左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合
var isValid = function(s) {
    let stack = [], length = s.length;
    if(length % 2) return false;
    for(let item of s){
        switch(item){
            case "{":
            case "[":
            case "(":
                stack.push(item);
                break;
            case "}":
                if(stack.pop() !== "{") return false;
                break;
            case "]":
                if(stack.pop() !== "[") return false;
                break;
            case ")":
                if(stack.pop() !== "(") return false;
                break;
        }
    }
    return stack.length===0;
};

无论是内存还是时间上都还有很多值得优化的地方,大家有好的方法欢迎指教🙋‍♀️🙋‍♀️🙋‍♀️🙋‍♀️
在这里插入图片描述

来源url
栏目