資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：查詢可構成括號序列的RBS字串數量
假設我們有一個包含括號的字串S。有兩種型別的括號： '(' ')' 和 '[' ']'。如果一個字串遵循以下型別，則稱其為正則括號序列 (RBS)：
- 空字串；
- '(' | RBS | ')'；
- '[' | RBS | ']'；
- RBS | RBS。
其中 '|' 表示兩個字串的串聯。在一個步驟中，我們可以選擇字串 S 的一個非空子序列（不必連續），該子序列是一個 RBS，然後將其從字串中移除，並將剩餘部分連線起來，而不改變順序。我們需要找到可以執行的最大步驟數。
問題類別
上述問題可以透過應用貪心演算法解決。貪心演算法是一種選擇當前最佳解決方案而不是遍歷所有可能解決方案的演算法。貪心演算法也用於解決最佳化問題，就像它的“兄弟”動態規劃一樣。在動態規劃中，需要遍歷所有可能的子問題以找到最優解，但它有一個缺點：它需要更多的時間和空間。因此，在各種情況下，使用貪心演算法來找到問題的最優解。雖然它並非在所有情況下都能給出最優解，但如果設計得當，它可以比動態規劃更快地產生解決方案。貪心演算法為最佳化問題提供區域性最優解。這種技術的示例包括克魯斯卡爾和普里姆最小生成樹 (MST) 演算法、霍夫曼樹編碼、迪傑斯特拉單源最短路徑問題等。
https://tutorialspoint.tw/data_structures_algorithms/greedy_algorithms.htm
https://tutorialspoint.tw/data_structures_algorithms/dynamic_programming.htm
因此，如果我們問題的輸入類似於 S = "([)]"，則輸出將為 2，因為如果我們移除 '(' 和 ')'，則會剩下 "[]" 作為子串，這是一個 RBS，現在將其移除以獲得空字串，這也是一個 RBS。
步驟
為了解決這個問題，我們將遵循以下步驟：
ans := 0
a := 0
b := 0
l := size of S
for initialize i := 0, when i < l, update (increase i by 1), do:
if S[i] is same as '(', then:
(increase a by 1)
if S[i] is same as '[', then:
(increase b by 1)
if S[i] is same as ')' and a > 0, then:
(decrease a by 1)
(increase ans by 1)
if S[i] is same as ']' and b > 0, then:
(decrease b by 1)
(increase ans by 1)
return ans示例
讓我們來看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(string S){
int ans = 0, a = 0, b = 0;
int l = S.size();
for (int i = 0; i < l; i++){
if (S[i] == '(')
a++;
if (S[i] == '[')
b++;
if (S[i] == ')' && a > 0){
a--;
ans++;
}
if (S[i] == ']' && b > 0){
b--;
ans++;
}
}
return ans;
}
int main(){
string S = "([)]";
cout << solve(S) << endl;
}輸入
"([)]"
輸出
2
瀏覽量：288
