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

绝地灬酷狼 2022-11-30 12:48 108阅读 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 条评论，108人围观）

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

相关阅读

相关 DP：最长有效括号

DP：最长有效括号问题： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0c

Love The Way You Lie/ 2023年10月06日 16:51/ 0 赞/ 12 阅读

相关 leetcode 最长有效括号

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

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

相关最长有效括号

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

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

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

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

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

相关 32. 最长有效括号

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

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

相关 LeetCode32. 最长有效括号

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

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

相关最长公共字符串

include <iostream> include <string> include <stack> include <algorit

ゞ浴缸里的玫瑰/ 2022年06月17日 04:26/ 0 赞/ 142 阅读

相关 Java 最长字符串

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

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

相关输出最长字符串

import java.util.Scanner; public class Main \{ public static void main(String\[\] arg

以你之姓@/ 2022年04月10日 02:22/ 0 赞/ 170 阅读

相关算法训练最长字符串 java

算法训练最长字符串时间限制：1.0s 内存限制：512.0MB 求出5个字符串中最长的字符串。每个字符串长度在100以内，且全为小写字母。样例输入 one

川长思鸟来/ 2021年12月21日 17:15/ 0 赞/ 208 阅读