专栏首页渔夫算法:有效括号

算法:有效括号

版权声明: https://blog.csdn.net/li_xunhuan/article/details/90140416

问题描述:

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

有效字符串需满足:

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

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

示例 1:

输入: “()” 输出: true

示例 2:

输入: “()[]{}” 输出: true

示例 3:

输入: “(]” 输出: false

示例 4:

输入: “([)]” 输出: false

示例 5:

输入: “{[]}” 输出: true

方案1:

我们用一个堆栈来实现,若发现是左括号之一,压入堆栈;发现是右括号之一,那么弹出上一个堆栈值,除非弹出括号是与当前右括号对应的左括号,那么必然是括号不对; 这样我们还要考虑一个问题,如果左括号比右括号多怎么办,但是存在着的右括号和左括号都是匹配的,那么我们考虑到,堆栈的弹出左括号操作必然会有造成栈元素减少,所以我们利用堆栈元素空不空来最后把关,是否完全匹配

时间复杂度,空间复杂度:均为O(n)

代码1:
class Solution {
public boolean isValid(String s) {
    if(s==null){
        return false;
    }
    int length=s.length();
    if(length==0)
        return true;

Stack stack = new Stack<>();

for(int i=0;i<length;i++){
    char charTemp=s.charAt(i);
    if(charTemp=='{'||charTemp=='['||charTemp=='('){
        stack.push(charTemp);
    }else{
        if(stack.empty())
            return false;
        char charcurr = stack.pop();
        if((charTemp=='}'&&charcurr!='{')||(charTemp==']'&&charcurr!='[')||(charTemp==')'&&charcurr!='('))
    return false;    
    }

}
if(stack.empty())
return true;    
   return false;
}
}

方案2:

我们发现使用Java语法中的Stack结构可以解决这个问题,那么问题来了,我们何不用简单的数组实现这个问题,只要设置一个top指针(Java中没有指针,但是类似于C中的作用,所以命名为指针),使top始终指向堆栈顶元素,并且自定义数组实现堆栈的压入push以及弹出操作pop 时间复杂度,空间复杂度:均为O(n)

代码2:
class Solution {
public boolean isValid(String s) {
    if(s==null){
        return false;
    }
    int length=s.length();
    if(length==0)
        return true;
    char[] stack=new char[length];
    int top=-1;
for(int i=0;i<length;i++){
    char charTemp=s.charAt(i);
    if(charTemp=='{'||charTemp=='['||charTemp=='('){
        ++top;
        stack[top]=charTemp;
        
    }else{
        if(top==-1)
            return false;
        char charcurr = stack[top];
        top--;
        if((charTemp=='}'&&charcurr!='{')||(charTemp==']'&&charcurr!='[')||(charTemp==')'&&charcurr!='('))
    return false;    
    }

}
if(top==-1)
return true;    
   return false;
}
}

方案3:

我们发现如果数组用不了这么大,这样造成了空间的极大浪费,所以我们用ArrayList对方案2中的数组数据结构进行优化: 时间复杂度,空间复杂度:均为O(n)

实际上这个运行时间并不比方案2简单,原因暂时未知

代码3:

class Solution {
public boolean isValid(String s) {
    if(s==null){
        return false;
    }
    int length=s.length();
    if(length==0)
        return true;
    List<Character> stack= new ArrayList<>();
for(int i=0;i<length;i++){
    char charTemp=s.charAt(i);
    if(charTemp=='{'||charTemp=='['||charTemp=='('){
      stack.add(charTemp);
    }else{
        if(stack.isEmpty())
            return false;
        char charcurr = stack.remove(stack.size()-1);
        if((charTemp=='}'&&charcurr!='{')||(charTemp==']'&&charcurr!='[')||(charTemp==')'&&charcurr!='('))
    return false;    
    }

}
if(stack.isEmpty())
return true;    
   return false;
}
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java虚拟机详解(三)------垃圾回收

      如果对C++这门语言熟悉的人,再来看Java,就会发现这两者对垃圾(内存)回收的策略有很大的不同。

    IT可乐
  • 精英程序员跟普通程序员区别在哪里?应该如何针对性的提高自己?

    正常来讲程序员之间的差异,主要还是解决问题的能力,一个好的程序框架不但可以兼容性强而且长时间运行还能非常的稳定,后续即使增加很多的功能也能不出大的问题,如果是普...

    程序员互动联盟
  • 你真的了解 lambda 吗(纠错篇)?

    本文链接:http://www.cmlanche.com/2018/07/22/lambda用法与源码分析/

    用户1516716
  • java自学出来的怎么找工作?

    一般来讲如果通过自学编程顺利找到工作的话,那么后劲一定都会非常的强劲,为什么通过自学编程找到工作的一般在公司做的还可以,作为一个从事编程行业十几年的老码农,对于...

    程序员互动联盟
  • SpringBoot2.0 基础案例(02):配置Log4j2,实现不同环境日志打印

    日志打印是了解Web项目运行的最直接方式,所以在项目开发中是需要首先搭建好的环境。

    知了一笑
  • 27款阿里巴巴实用且超神的Java开源项目

    Spring Cloud Alibaba 致力于提供分布式应用服务开发的一站式解决方案。此项目包含开发分布式应用服务的必需组件,方便开发者通过 Spring C...

    格姗知识圈
  • 如何在 IDEA 使用Debug 图文教程

    Debug用来追踪代码的运行流程,通常在程序运行过程中出现异常,启用Debug模式可以分析定位异常发生的位置,以及在运行过程中参数的变化。通常我们也可以启用De...

    用户1516716
  • 聊聊feign的Retryer

    feign-core-10.2.3-sources.jar!/feign/Retryer.java

    codecraft
  • Spring Boot配置文件详解

    Spring Boot提供了两种常用的配置文件,分别是properties文件和yml文件。他们的作用都是修改Spring Boot自动配置的默认值。

    格姗知识圈
  • 聊聊feign的RequestInterceptor

    feign-core-10.2.3-sources.jar!/feign/RequestInterceptor.java

    codecraft

扫码关注云+社区

领取腾讯云代金券