专栏首页老沙课堂数据结构与算法(四)栈

数据结构与算法(四)栈

概念

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

由于栈的特性为先进后出 所以称之为First In Last Out 简称FILO

栈pop和push

有效括号(leetCode 20题)

题目

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

有效字符串需满足:

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

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

解题思路

我们吧( [ {定义为统称为左括号

我们吧) ] }定义为统称为右括号

•给定字符串"({[]]})"; 如果发现是左面括号 就入栈。一直到发现是右括号•当为右括号就把栈顶元素pop出来, 如果和右括号匹配就继续, 否则返回false•如果遍历字符串到最后 栈为空,就返回true 否则就为false

有效括号

private static HashMap<Character, Character> map = new HashMap<Character, Character>();static {  map.put('(', ')');  map.put('[', ']');  map.put('{', '}');}
public boolean isValid(String s) {  int length = s.length();  Stack<Character> stack = new Stack<>();  for (int i = 0; i < length; i++) {    Character character = s.charAt(i);
    if (map.containsKey(character)) {      stack.push(character);    } else {      if (stack.isEmpty()) {        return false;      }      if (character != map.get(stack.pop())) {        return false;      }    }  }  if (stack.isEmpty()) {    return true;  }  return false;}

时间复杂度

因为需要遍历字符串 长度为n 所以时间复杂度为O(n);

本文分享自微信公众号 - 老沙课堂(gh_f73a6b772d4f),作者:沙睿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构与算法(二)数组

    在堆中连续开辟的一段空间,每个元素占有相同大小的空间。一经开辟,即固定大小,无法改变长短。

    老沙
  • 数据结构与算法(六) 二叉树遍历

    •任意一个节点的值都大于其左子树的值•任意一个节点的值都小于其右子树的值•他的左右子树也是一颗二叉搜索树•二叉搜索树可以大大提高效率(搜索和添加删除时间复杂度都...

    老沙
  • 数据结构与算法(一) 简单例子理解时间复杂度和空间复杂度

    所以总的时间为1 + n + n + n + n^2 + n^2 + n^2 = 1 +3n +3n^2 由于计算时间复杂度可以省略常数,系数以及低阶 所以这个...

    老沙
  • qcache_inserts com_select 与缓存命中率

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1148526
  • 小程序云开发实现商品浏览次数的展示

    我们在开发小程序的时候,经常遇到需要展示页面浏览次数,以彰显这个商品的热度。下面我们用云开发技术,实现一下这个简单的需求。

    CreatorRay
  • Leetcode之有效的括号

    润森
  • SQL函数

    Aggregate 函数: AVG() - 返回平均值 COUNT() - 返回行数 FIRST() - 返回第一个记录的值 LAST() - 返回最后...

    德勒
  • Sony IPELA E 系列网络摄像头远程命令执行漏洞预警

    索尼[1]是世界视听、电子游戏、通讯产品和信息技术等领域的先导者,是世界最早便携式数码产品的开创者,是世界最大的电子产品制造商之一。

    Seebug漏洞平台
  • 传统医疗行业上云实践

    随着医疗行业的发展,在医疗行业也出现了比较激烈的竞争,许多的医院开始由线下转到线上来,比较出名的可能就是寻医问药和春雨医生等这样问答形式的站点。他们验证了在线问...

    相柳
  • Java基础12 类型转换与多态

    我们之前使用类创造新的类型(type),并使用继承来便利我们创建类的过程。我将在这一讲中深入类型,并介绍多态(polymorphism)的概念。

    Java团长

扫码关注云+社区

领取腾讯云代金券