专栏首页java工会算法养成记:有效括号

算法养成记:有效括号

LeetCode20

Valid Parentheses 验证括号

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

An input string is valid if:

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

2.Open brackets must be closed in the correct order.

中文意思就是:

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

有效字符串需满足:

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

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

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

在实际测试里,

执行耗时是:2ms,1ms

内存消耗是:37.4MB,37.3MB

这题不难,但是尝试了好多种写法,一直都是2ms,接近崩溃。直到想到判断其他括号的时候,如果匹配上了就可以跳出循环了,用了图二的continue,出现1ms,击败98.92%的用户,悬着的心才下来,但是测试效果也不太稳定,希望各位小伙伴也提供下思路。

有个收获就是,之前写栈的时候,判断空,直接就用了stack.empty();测试中,使用这个方法一直都比stack.size()>0好内存高,看了下empty()的方法,里面还是去拿了size()来判断,还套了两层,这的确是没有必要了。

这一版文案您还觉得满意吗?
哪里不太对,但又说不上来。

数据结构和算法一直都是程序员面试重点。写好每一个方法,每一个接口,程序的效率也会越来越高。为了学习和巩固数据结构和算法,我们特别创作了《呆萌程序员--明明凯凯算法养成记》,每天更新一篇数据结构知识点或者刷一道LeetCode题目。算法都会在LeetCode上测试。当然答案不唯一,由于能力有限,实现方法不一定是最好的,也希望各位小伙伴一起来学习分享~

本文分享自微信公众号 - java工会(javagonghui),作者:除却巫山

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

原始发表时间:2020-03-07

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ 2942Knights of the Round Table(tarjan求点双+二分图染色)

    Description Being a knight is a very attractive career: searching for the Holy G...

    attack
  • 【Codeforces】1217A - Creating a Character

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【POJ 3176】Cow Bowling(DP)

    The cows don't use actual bowling balls when they go bowling. They each take a n...

    饶文津
  • LWC 58:724. Find Pivot Index

    LWC 58:724. Find Pivot Index 传送门:724. Find Pivot Index Problem: Given an array ...

    用户1147447
  • 洛谷P2870 [USACO07DEC]最佳牛线,黄金Best Cow Line, Gold

    题目描述 FJ is about to take his N (1 ≤ N ≤ 30,000) cows to the annual"Farmer of the...

    attack
  • P2880 [USACO07JAN]平衡的阵容Balanced Lineup

    题目背景 题目描述: 每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛....

    attack
  • cpuimage 开源之

    前年学习opengl做的一个小东西。 原本计划将gpuimage 的算法一个一个转写成cpu版本 c,c++ 版本。 gpuimage 项目参考: https:...

    cpuimage

扫码关注云+社区

领取腾讯云代金券