刷题 - 判断有多少组有效括号

判断有多少组有效括号

代码语言：javascript复制

package com.parker.example;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @Author: Parker
 * @CreateTime: 2020-07-17 16:08
 * @Description: 判断有多少组有效括号 - 刷题
 */
public class Test5 {

    /** 前缀 */
    private static char PREFIX = '(';
    /** 后缀 */
    private static char POSTFIX = ')';

    public static void main(String[] args) {
        String s = ") ((( ((( )";
        String s1 = "((() ((( ((( ))))";
        int count;
        // 暴力解法
        //count = m1(s);

        // 压栈解法
        count = m2(s1);


        System.out.println(count);
    }


    /**
     * 暴力求解
     * @param s
     * @return
     */
    public static int m1(String s) {
        int count = 0;
        // 非法判断
        if(s.length() < 1){
            return count;
        }
        // 匹配寄存器
        Map<Integer,Integer> cMap = new HashMap<>(s.length());
        for (int i = 0; i < s.length(); i  ) {
            // 为 ）直接跳过
            if(s.charAt(i) != PREFIX){
                continue;
            }
            for (int k = 1 i; k < s.length(); k  ) {
                if(s.charAt(k) == POSTFIX && cMap.get(k) == null){
                    count  ;
                    // 后缀起始计数器
                    cMap.put(k,k);
                    break;
                }
            }
        }

        return count;
    }

    /**
     * 压栈求解
     * @param s
     * @return
     */
    public static int m2(String s){
        int count = 0;
        // 非法判断
        if(s.length() < 1){
            return count;
        }

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i  ) {
            // 如果是 （ 压栈
            if(s.charAt(i) == PREFIX){
                stack.push(s.charAt(i));
            }else if(s.charAt(i) == POSTFIX){
                if(!stack.isEmpty()){
                    char peek = stack.peek();
                    if(PREFIX == peek){
                        count  ;
                        // 出栈
                        stack.pop();
                    }
                }
            }
        }
        return count;
    }
}

我的博客即将同步至腾讯云 社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=1dhp3tfisfirp

腾讯云 博客 同步

0 人点赞