資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用 C++ 在括號字串中查詢平衡點。
在這裡，我們將學習如何在括號字串中找到平衡點。平衡點是指索引 I，在該索引之前左括號的數量等於其之後右括號的數量。假設括號字串類似於“(()))(()()())))”，仔細觀察，我們可以得到
因此，從 0 到 9 的左括號數量為 5，從 9 到 14 的右括號數量也為 5，所以這是平衡點。
為了解決這個問題，我們必須遵循以下幾個步驟：
- 儲存字串中每個索引 i 之前的左括號數量。
- 儲存字串中每個索引 I 之前的右括號數量，但應從最後一個索引開始。
- 檢查某個索引的左括號數量和右括號數量是否相同。
示例
#include<iostream>
#include<cmath>
using namespace std;
int findEqualPoint(string str) {
int total_length = str.length();
int open[total_length+1] = {0}, close[total_length+1] = {0};
int index = -1;
open[0] = 0;
close[total_length] = 0;
if (str[0]=='(') //check whether first bracket is opening or not, if so mark open[1] = 1
open[1] = 1;
if (str[total_length-1] == ')') //check whether first bracket is closing or not, if so mark close[end] = 1
close[total_length-1] = 1;
for (int i = 1; i < total_length; i++) {
if ( str[i] == '(' )
open[i+1] = open[i] + 1;
else
open[i+1] = open[i];
}
for (int i = total_length-2; i >= 0; i--) {
if ( str[i] == ')' )
close[i] = close[i+1] + 1;
else
close[i] = close[i+1];
}
if (open[total_length] == 0)
return total_length;
if (close[0] == 0)
return 0;
for (int i=0; i<=total_length; i++)
if (open[i] == close[i])
index = i;
return index;
}
int main() {
string str = "(()))(()()())))";
cout << "Index of equal point: " << findEqualPoint(str);
}輸出
Index of equal point: 9
更新於：2019年10月29日
288 次檢視
廣告