数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++中括号间字符串的反转
假设我们有一个字符串 s，它包含小写字母和括号。我们必须反转每一对匹配括号内的字符串，从最里面的开始。并且结果不应包含任何括号。所以如果输入类似于“(hel(lowo)rld)” ，那么输出将是“dlrlowoleh”，所以从一开始，它像这样改变： “(hel(lowo)rld)” → “(helowolrld)” → “dlrowoleh”。
为了解决这个问题，我们将遵循以下步骤：
n := 字符串的大小，创建一个名为 par 的数组，其长度为 n，定义一个栈 st
对于 i 的范围从 0 到 n – 1
如果 s[i] 是左括号，则将 i 插入 st
否则，当 s[i] 是右括号时，则 j := st.pop()，par[i] := j 且 par[j] := i
定义一个空字符串 ret
对于 i := 0，d := 1，i < n，i 增加 d
如果 s[i] 是左括号或 s[i] 是右括号，则 i := par[i]，d := -d 否则 ret 增加 s[i]
返回 ret
示例（C++）
让我们看看下面的实现以获得更好的理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void out(vector <int>& v){
for(int i = 0; i < v.size(); i++){
cout << v[i] << " " ;
}
cout << endl;
}
string reverseParentheses(string s) {
int n = s.size();
vector <int> par(n);
stack <int> st;
for(int i = 0; i < n; i++){
if(s[i] == '('){
st.push(i);
}
else if(s[i] == ')'){
int j = st.top();
st.pop();
par[i] = j;
par[j] = i;
}
}
string ret = "";
for(int i = 0, d = 1; i < n; i += d){
if(s[i] == '(' || s[i] == ')'){
i = par[i];
d = -d;
}
else{
ret += s[i];
}
}
out(par);
return ret;
}
};
main(){
Solution ob;
cout << (ob.reverseParentheses("(hel(lowo)rld)"));
}输入
"(hel(lowo)rld)"
输出
13 0 0 0 9 0 0 0 0 4 0 0 0 0 dlrlowoleh
更新于: 2020-04-29
303 次浏览
广告