LeetCode 之 JavaScript 解答第20题 —— 有效的括号（Valid Parent

novo 发布于2019-08-23 16:54 / 676人阅读

摘要：小鹿题目给定一个只包括，，，，，的字符串，判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。注意空字符串可被认为是有效字符串。除去这两种情况都不是符合条件的。

Time：2019/4/11
Title: Valid Parentheses
Difficulty: Easy
Author: 小鹿

题目：Valid Parentheses

Given a string containing just the characters "(", ")", "{", "}", "[" and "]", determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Solve: ▉ 算法思路

1、首先，我们通过上边的例子可以分析出什么样子括号匹配是复合物条件的，两种情况。

第一种（非嵌套情况）：{} [] ；

第二种（嵌套情况）：{ [ ( ) ] } 。

除去这两种情况都不是符合条件的。

2、然后，我们将这些括号自右向左看做栈结构，右侧是栈顶，左侧是栈尾。

3、如果编译器中的括号左括号，我们就入栈（左括号不用检查匹配）；如果是右括号，就取出栈顶元素检查是否匹配。（提前将成对的括号通过键值对的方式存到散列表中）

4、如果匹配，就出栈。否则，就返回 false；

▉ 代码实现

下方代码在标准的 Leetcode 测试中并不是最省内存和效率高的，因为我们用到了 Map，在内

var isValid = function(s) {
    let stack = [];
    //将括号匹配存入散列表中
    let map = new Map();
    map.set(")","(");
    map.set("]","[");
    map.set("}","{");
    // 取出字符串中的括号
    for(let i = 0; i < s.length; i++){
        let c = s[i];
        //如果是右括号，如果栈中不为空就出栈栈顶数据
        if(map.has(c)){
            //判断栈此时是否为0
            if(stack.length !== 0){
                //如果栈顶元素不相同，就返回 false
                if(stack.pop() !== map.get(c)){
                    return false;
                }
            //如果此时栈内无元素，返回false
            }else{
                return false;
            }
        }else{
            //如果是左括号，就进栈
            stack.push(c);
        }
    }
    //如果栈为空，括号全部匹配成功
    return stack.length === 0;
};
let str = "({(})";
console.log(isValid(str));

▉ 代码改进

1）该改进用对象替代了 Map，节省了内存空间。

2）在判断时，没有用到提前存储的结构，直接使用当遇到左括号是直接入栈，提高了执行效率。

var isValid = function(s) {
    let stack = [];
    var obj = {
        "]": "[",
        "}": "{",
        ")": "(",
    };

    for(var i = 0; i < s.length; i++) {
        if(s[i] === "[" || s[i] === "{" || s[i] === "(") {
            stack.push(s[i]);
        } else {
            var key = stack.pop();
            if(maps[key] !== s[i]) {
                return false;
            }
        }
    }
    if(!stack.length) {
        return true;
    }
    return false;
};

▉ 复杂度分析

时间复杂度： O（n）。只需要遍历一遍字符串中的字符，入栈和出栈的时间复杂度为 O(1)。空间复杂度： O（n）。当只有左括号近栈，没有右括号进行匹配的时候是最糟糕的情况，所有括号都在栈内。例如：{{{{{{{{{

欢迎一起加入到 LeetCode 开源 Github 仓库，可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡，共同完善我们的开源小仓库！
Github：https://github.com/luxiangqia...

服务器托管私有云 javascript算法题汇编语言程序设计第二版课后题答案 javascript必问面试题希望你的解答谢谢

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/103489.html

LeetCode 之 JavaScript 解答第150题 —— 逆波兰表达式求值

摘要：小鹿题目根据逆波兰表示法，求表达式的值。给定逆波兰表达式总是有效的。算法思路仔细观察上述的逆波兰表达式，可以发现一个规律就是每遇到一个操作符，就将操作符前的两个操作数进行运算，将结果保存到原位置。 Time：2019/4/14Title: Evaluate Reverse Polish NotationDifficulty: MediumAuthor:小鹿题目：Evaluate ...

104828720 2019-08-23 16:56 评论0 收藏0
LeetCode 之 JavaScript 解答第8题 —— 字符串转换整数（String to

摘要：当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。数字前正负号要保留。 Time：2019/4/19Title: String To IntegerDifficulty: MediumAuthor: 小鹿题目：String To Integer（字...

zhisheng 2019-08-23 17:03 评论0 收藏0
LeetCode 之 JavaScript 解答第98题 —— 验证二叉搜索树

摘要：小鹿题目验证二叉搜索树给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。算法思路定义全局的变量，用来返回是否为二叉搜索树。 Time：2019/4/24Title: Vaildata Binary Search TreeDifficulty: MediumAuthor: 小鹿 ...

用户84 2019-08-23 17:12 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
leetcode-019-删除链表倒数第N个结点(Remove Nth Node From End

摘要：第题给定一个链表，删除链表的倒数第个节点，并且返回链表的头结点。因为，若有一个真正的头结点，则所有的元素处理方式都一样。但以第一个有效元素为头结点，就导致算法的不一致，需要单独处理第一个有效元素头结点。 leetcode第19题 Given a linked list, remove the n-th node from the end of list and return its h...

brianway 2019-08-23 14:34 评论0 收藏0