資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在C++中，如何找到滿足給定位置具有開括號的平衡表示式？
給定一個整數m和一個位置陣列'position[]' (1 <= length(position[]) <= 2m)，找到可以構造長度為2m的正確括號表示式的數量，使得給定位置具有開括號。
注意：position[]陣列以(基於1的索引)[0, 1, 1, 0]的形式提供。這裡1表示應該設定開括號的位置。對於值為0的位置，可以設定開括號或閉括號。
示例
Input: n = 2, position[] = [1, 0, 1, 0] Output: 1 The only possibility is given below: [ ] [ ] In this case, recursive and recursion implementing memorization approach will be explained.
演算法
我們必須將給定陣列adj1（假設）中所有帶有開括號的位置標記為1。
我們執行一個遞迴迴圈，方法如下：
如果總括號數（開括號減去閉括號）小於零，則返回0。
如果索引達到m並且總括號數等於0，則存在解決方案並返回1，否則返回0。
如果索引值預先分配為1，則我們必須使用index+1遞迴呼叫函式，並將總括號數遞增。
否則，我們必須透過在該位置或索引處插入開括號並將總括號數遞增1，以及在該索引處插入閉括號並將總括號數遞減1，然後繼續到下一個索引直到m，來遞迴呼叫函式。
以下是上述演算法的遞迴解決方案：
示例
// C++ application of above method implementing Recursion
#include <bits/stdc++.h>
using namespace std;
// Function to locate or find Number of proper bracket expressions
int find(int index1, int openbrk1, int m, int adj1[]){
// If open-closed brackets less than 0
if (openbrk1 < 0)
return 0;
// If index reaches the end of expression
if (index1 == m) {
// If brackets are balanced
if (openbrk1 == 0)
return 1;
else
return 0;
}
// If the current index has assigned open bracket
if (adj1[index1] == 1) {
// We have to move forward increasing the
// length of open brackets
return find(index1 + 1, openbrk1 + 1, m, adj1);
}
else {
// We have to move forward by inserting open as well
// as closed brackets on that index
return find(index1 + 1, openbrk1 + 1, m, adj1)
+ find(index1 + 1, openbrk1 - 1, m, adj1);
}
}
// Driver Code
int main(){
int m = 2;
// Open brackets at position 1
int adj1[4] = { 1, 0, 0, 0 };
// Calling the find function to calculate the answer
cout << find(0, 0, 2 * m, adj1) << endl;
return 0;
}輸出
2
**記憶化方法 -**上述演算法的時間複雜度可以透過實現記憶化來改進或最佳化。
唯一需要執行的操作是實現一個數組來儲存先前迭代的結果，以便如果已經計算出值，則不需要多次遞迴呼叫同一個函式。
以下是所需的實現
// C++ application of above method implementing memorization
#include <bits/stdc++.h>
using namespace std;
#define M 1000
// Function to locate or find Number of proper bracket expressions
int find(int index1, int openbrk1, int m,
int dp1[M][M], int adj1[]){
// If open-closed brackets is less than 0
if (openbrk1 < 0)
return 0;
// If index attains or reaches the end of expression
if (index1 == m) {
// If brackets are balanced
if (openbrk1 == 0)
return 1;
else
return 0;
}
// If already stored in dp1
if (dp1[index1][openbrk1] != -1)
return dp1[index1][openbrk1];
// If the current index has assigned open bracket
if (adj1[index1] == 1) {
// We have to move forward increasing the length of open brackets
dp1[index1][openbrk1] = find(index1 + 1,
openbrk1 + 1, m, dp1, adj1);
}
else {
// We have to move forward by inserting open as
// well as closed brackets on that index
dp1[index1][openbrk1] = find(index1 + 1, openbrk1 + 1, m, dp1, adj1) + find(index1 + 1, openbrk1 - 1, m, dp1, adj1);
}
// We have to return the answer
return dp1[index1][openbrk1];
}
// Driver Code
int main(){
// dp1 array to precalculate the answer
int dp1[M][M];
int m = 2;
memset(dp1, -1, sizeof(dp1));
// Open brackets at position 1
int adj1[4] = { 1, 0, 0, 0 };
// We have to call the find function to compute the answer
cout<< find(0, 0, 2 * m, dp1, adj1) << endl;
return 0;
}
輸出
2
時間複雜度：O(N2)
更新於：2020年1月29日
156 次檢視
廣告