数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用Java计算最长平衡括号前缀的长度
在本文中，我们将探讨如何使用Java查找最长平衡括号前缀的长度，首先我们将通过一些示例来理解问题，然后学习两种不同的方法来找到它。
问题陈述
在这里，我们将得到一个包含括号的字符串，我们需要找到字符串中平衡括号集的长度，即对于每个左括号"("，如果存在一个右括号")"，则我们称之为平衡的。
前缀定义字符串中的第一个平衡集，例如括号集'(())()'，我们只考虑'(())'。
输入输出场景
让我们看一些输入输出场景，以便更好地理解。
- 假设输入字符串为"(()"，这里平衡括号前缀为()，则长度为2。
- 如果输入字符串为"((()()))((("，这里平衡括号前缀为((()()))，则长度为8。
- 如果输入字符串为"(()())()()"，平衡括号前缀为(()())，则长度为6。
我们可以得到最长平衡括号前缀的长度：
- 使用栈数据结构
- 计算左括号和右括号
使用栈数据结构
我们可以使用一个栈，然后从栈中，如果我们得到一个左括号'('，则将其压入栈中，如果我们得到一个右括号，则弹出栈并使计数器变量加2（一个平衡对的长度为2），继续这个过程，当我们得到空栈时，我们将返回计数器变量。
算法
以下是算法：
Step 1: Initialize a stack and a counter.
Step 2: Iterate through each character in the string.
- If character is ( push it onto the stack.
- If character is ) pop the stack.
- Increment counter by 2
- Check whether the stack is empty or not
- If empty, break;
Step 3: Finally return the counter;
示例
import java.util.Stack;
public class Example {
public static int longestBalancedPrefix(String s) {
Stack<Character> stack = new Stack<>();
int count = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(') {
stack.push(ch);
} else if (ch == ')') {
if (!stack.isEmpty()) {
stack.pop();
count += 2;
if (stack.isEmpty()) {
break;
}
}
}
}
return count;
}
public static void main(String args[]) {
String s = "((())((";
System.out.println("input string is: " + s);
System.out.println("Length of longest balanced parentheses prefix is " + longestBalancedPrefix(s));
}
}
输出
input string is: ((())(( Length of longest balanced parentheses prefix is 4
计算左括号和右括号
在这种方法中，我们将使用两个变量，一个为count，另一个为length。然后从字符串中，如果字符为"("，我们将count加1，如果字符为")"，我们将count减1，并将length加2，并检查count是否为零，如果为零，则中断循环并返回length。
示例
public class Example {
public static void main(String args[]) {
String s = "((())())(())";
int count = 0;
int length = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(') {
count++;
} else if (ch == ')') {
count--;
length = length + 2;
if (count == 0) {
break;
}
}
}
System.out.println("Input string is " + s);
System.out.println("Length of the longest balanced parentheses prefix is " + length);
}
}
输出
Input string is ((())())(()) Length of the longest balanced parentheses prefix is 8
更新于：2024年11月7日
29 次浏览
广告