資料結構
網路
關係資料庫管理系統(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 次瀏覽
廣告