数据结构
网络
关系数据库管理系统(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 次查看
广告