LeetCode - 020 - 有效的括号(valid-parentheses)

栏目: 编程工具 · 发布时间: 4年前

内容简介:解题千千万,官方独一家,上面是官方使用 Java 进行的题解。小伙伴可以先自己在本地尝试解题,再看看官方解题,最后再回来看看首先,我们来想下平时玩的翻牌游戏:
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:
输入: "()"
输出: true

示例 2:
输入: "()[]{}"
输出: true

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true
复制代码

三 解题

解题千千万,官方独一家,上面是官方使用 Java 进行的题解。

小伙伴可以先自己在本地尝试解题,再看看官方解题,最后再回来看看 jsliang 讲解下使用 JavaScript 的解题思路。

  • 解题代码
var isValid = function(s) {
  let judge = {
    '[': ']',
    '(': ')',
    '{': '}',
  }
  let parameter = s.split('');
  let stack = [];
  for (let i = 0; i < parameter.length; i++) {
    if (judge[stack[stack.length - 1]] === parameter[i]) {
      stack.pop();
    } else {
      stack.push(parameter[i]);
    }
  }
  if (stack.length == 0) {
    return true;
  }
  return false;
};
复制代码
  • 执行测试
  1. s()[]{}
  2. returntrue
  • LeetCode Submit
✔ Accepted
  ✔ 76/76 cases passed (76 ms)
  ✔ Your runtime beats 96.48 % of javascript submissions
  ✔ Your memory usage beats 66.23 % of javascript submissions (33.8 MB)
复制代码
  • 知识点
  1. split()split() 方法使用指定的分隔符字符串将一个 String 对象分割成字符串数组,以将字符串分隔为子字符串,以确定每个拆分的位置。 split() 详细介绍
  2. push()push() 方法将一个或多个元素添加到数组的末尾,并返回该数组的新长度。 push() 详细介绍
  3. pop()pop() 方法从数组中删除最后一个元素,并返回该元素的值。此方法更改数组的长度。 pop() 详细介绍
  • 解题思路

首先,我们来想下平时玩的翻牌游戏:

游戏屏幕中有 4 * 4 共 16 张牌。

如果在同一个回合中(一个回合能翻 2 次牌),我们翻出来相同的两张牌,就把它摊开(消掉);

如果在同一个回合中翻到两张不同的牌,我们就要把它覆盖回去。

LeetCode - 020 - 有效的括号(valid-parentheses)

这时候,机智如你,有没有想过要一个作弊器,用来记录我们翻过的牌?!

就好比:我们先翻到红包,再翻到炸弹,下一次翻到红包的时候,我们就打开一开始翻到红包的地方……

OK,这么讲,小伙伴们大致清楚了。

现在,我们有一个字符串: (()[]{}) ,我们要判断它是否是有效的括号,怎么判断呢:

  1. 这些括号必须成对出现,例如: ()[]{}
  2. 这些括号出现的情况不能乱序,例如: ([)]{[}]

同时,我们初始化下数据:

  • judge :
{
  '[': ']',
  '(': ')',
  '{': '}',
}
复制代码
  • parameter[ '(', '(', ')', '[', ']', '{', '}', ')' ]
  • stack[]

然后,我们是不是该开始使用我们的作弊器了:

LeetCode - 020 - 有效的括号(valid-parentheses)

在这个作弊器中,我们将碰到的括号记录起来。

如果碰到下一个括号,是我们想要的类型,那么就消掉最上层的括号;

如果碰到下一个括号,不是我们想要的类型,那么就把它放到数组的最上层。

  1. 遍历第一次, stack 末尾是空的,所以我们执行 push() 操作, stack['(']
  2. 遍历第二次, stack 末尾是 '(' ,通过 judge 转换就是 ')' ,而在这个位置的 parameter[i]'(' ,两者不相同,所以我们还是执行 push() 操作, stack['(', '(']
  3. 遍历第三次, stack 末尾是 '(' ,通过 judge 转换就是 ')' ,而在这个位置的 parameter[i]')' ,两者相同,所以我们执行 pop() 操作,将数组的末尾给删掉, stack['(']
  4. ……以此类推,最后我们的 stack 变成 [] 空数组。

最后,我们根据 stack 是否为空数组,来进行判断这个字符串是不是有效数组。

jsliang广告推送:

也许小伙伴想了解下云服务器

或者小伙伴想买一台云服务器

或者小伙伴需要续费云服务器

欢迎点击 云服务器推广 查看!

LeetCode - 020 - 有效的括号(valid-parentheses)
LeetCode - 020 - 有效的括号(valid-parentheses)

LeetCode - 020 - 有效的括号(valid-parentheses)

jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议 进行许可。

基于 github.com/LiangJunron… 上的作品创作。

本许可协议授权之外的使用权限可以从 creativecommons.org/licenses/by… 处获得。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

jQuery基础教程(第3版)

jQuery基础教程(第3版)

[美] Jonathan Chaffer、[美] Karl Swedberg / 李松峰 / 人民邮电出版社 / 2012-4 / 59.00元

内容简介: jQuery是功能强大却又简洁明快的轻量级JavaScript库,出自名家之手。在DOM操作、事件处理、Ajax特性以及动画特效等方面的出色表现,使它迅速从众多JavaScript库中脱颖而出,成为一颗闪亮的明星。 本书是《jQuery基础教程(第2版)》的升级版,涵盖了jQuery 1.6及1.7的各种新特性,内容源自著名jQuery资源网站LearningjQuery.......一起来看看 《jQuery基础教程(第3版)》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

MD5 加密
MD5 加密

MD5 加密工具

html转js在线工具
html转js在线工具

html转js在线工具