java 实现计算最长有效字符串

绝地灬酷狼 2022-11-30 12:48 151阅读 0赞

这个算法给人的第一感觉是挺简单的，而且类似的还有一个算法是--有效括号。查看括号是不是一一对应的。但是在写的时候还是遇到了挺多的坑的。记录一下。

首先这类问题肯定先想到队列、栈等等。比较之下要使用栈（stack）

大概就是这样的，直接上代码：

public class bracket{
    
        public static int bracketLength(String s){
            if (s == null || s.length() == 0){
                return 0;
            } 
            // 创建一个空栈
            Deque<Integer> stack = new ArrayDeque<Integer>();
            // 给栈添加一个基本数据，要不如果第一个就是")"就容易空指针
            stack.push(-1);
            //System.out.println(stack);
            // 定义一个初始长度
            int res = 0;
            for (int i = 0; i < s.length(); i++) {
                // 如果是"("，直接入栈。
                if (s.charAt(i) == '(') stack.push(i);
                // 如果是")"，就需要出栈，然后继续判断一下栈是不是为空了
                else {
                    stack.pop();
                    // 如果此时栈空了，那么我们就需要将此时的 角标位置放入栈中。
                    if (stack.isEmpty()) {
                        stack.push(i);
                    }
                    // 如果不是空的，就计算长度。每次都进行比较，只留下来最长的一个数
                    else {
                        res = Math.max(res, i - stack.peek());
                    }
                }
            }
            return res;
        }
    
        public static void main(String[] args) {
    
            String s = ")()())";
            int i = leetcode1(s);
            System.out.println(i);
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，151人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 最长有效括号

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"

Dear 丶/ 2023年08月17日 15:43/ 0 赞/ 119 阅读

相关 leetcode 32. 最长有效括号

思路：动态规划，dp\[i\]表示以s\[i\]结尾的，最长的子串长度很明显,当s\[i\]=='('时，不能构成完整子串，dp\[i\]=0, 当s\[i\]==

桃扇骨/ 2023年07月02日 10:27/ 0 赞/ 7 阅读

相关 leetcode32 最长有效括号

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nk

た入场券/ 2023年06月18日 05:54/ 0 赞/ 15 阅读

相关 32. 最长有效括号

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号

我会带着你远行/ 2023年02月22日 13:55/ 0 赞/ 10 阅读

相关 Leetcode 最长有效括号

利用括号匹配的算法以及栈，就可以算出匹配序列，然后利用两个变量记录有效括号的起始值与结束值，就可以得到最长有效括号。 include<stdio.h> inc

左手的ㄟ右手/ 2023年02月22日 13:52/ 0 赞/ 8 阅读

相关最长有效括号

最长有效括号 1、参考资料 https://leetcode-cn.com/problems/longest-valid-parentheses/ 2、题目要求

今天药忘吃喽~/ 2022年12月05日 10:00/ 0 赞/ 162 阅读

相关 java 实现计算最长有效字符串

这个算法给人的第一感觉是挺简单的，而且类似的还有一个算法是--有效括号。查看括号是不是一一对应的。但是在写的时候还是遇到了挺多的坑的。记录一下。首先这类问题肯定先想到队列、

绝地灬酷狼/ 2022年11月30日 12:48/ 0 赞/ 152 阅读

相关 32. 最长有效括号

[https://leetcode-cn.com/problems/longest-valid-parentheses/][https_leetcode-cn.com_prob

今天药忘吃喽~/ 2022年09月10日 11:27/ 0 赞/ 156 阅读

相关 LeetCode32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。示例 1：输入：s = "(()" 输出：2 解释：最长有效括号子串

系统管理员/ 2022年09月08日 00:12/ 0 赞/ 143 阅读

相关 Java 最长字符串

求出5个字符串中最长的字符串。每个字符串长度在100以内，且全为小写字母。样例输入 one two three four five 样例输出 three 代码：

秒速五厘米/ 2022年04月22日 23:28/ 0 赞/ 185 阅读