大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
给出一个字符串 s(仅含有小写英文字母和括号)。
请你按照从括号内到外的顺序,逐层反转每对匹配括号中的字符串,并返回最终的结果。
注意,您的结果中 不应 包含任何括号。
示例 1:
输入:s = "(abcd)"
输出:"dcba"
示例 2:
输入:s = "(u(love)i)"
输出:"iloveu"
示例 3:
输入:s = "(ed(et(oc))el)"
输出:"leetcode"
示例 4:
输入:s = "a(bcdefghijkl(mno)p)q"
输出:"apmnolkjihgfedcbq"
提示:
0 <= s.length <= 2000
s 中只有小写英文字母和括号
我们确保所有括号都是成对出现的
- 栈
class Solution {
public:
stack<char>s1;
queue<char>s2;
bool isalpha(char a){
return a >= 'a' && a <= 'z';
}
string reverseParentheses(string s) {
for(auto &a : s){
if(isalpha(a) || a == '('){
s1.push(a);
}
else{
while(s1.top() != '('){
s2.push(s1.top());
s1.pop();
}
s1.pop();
while(s2.size()){
s1.push(s2.front());
s2.pop();
}
}
}
string t = "";
while(s1.size()){
t.append(1,s1.top());
s1.pop();
}
reverse(t.begin(),t.end());
return t;
}
};
- splay
#define lson tr[u].s[0]
#define rson tr[u].s[1]
const int N = 2010;
class Solution {
public:
struct node{
int p,v;
int s[2];
int size,flag;
void init(int _v,int _p){
v = _v,p = _p;
flag = 0,size = 1;
}
}tr[N] = {
0};
int root = 0,ctx = 0;
void pushdown(int u){
if(tr[u].flag){
swap(tr[lson].s[0],tr[lson].s[1]);
swap(tr[rson].s[0],tr[rson].s[1]);
tr[lson].flag ^= 1;
tr[rson].flag ^= 1;
tr[u].flag = 0;
}
}
void pushup(int u){
tr[u].size = tr[lson].size + tr[rson].size + 1;
}
void rotate(int x){
int y = tr[x].p,z = tr[y].p;
int k = tr[y].s[1] == x;//k是1 则x是y的右儿子,k是0,则x是y的左儿子
tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1],tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y,tr[y].p = x;
pushup(y);pushup(x);
}
void splay(int x,int k){
//将x节点旋转到k节点下面
while(tr[x].p != k){
int y = tr[x].p,z = tr[y].p;
if(z != k){
if((tr[z].s[1] == y) ^ (tr[y].s[1] == x))rotate(x);
else rotate(y);
}
rotate(x);
}
if(!k)root = x;
}
void insert(char a){
int u = root,p = 0;
while(u)pushdown(u),p = u,u = tr[u].s[1];
u = ++ ctx;
if(p)tr[p].s[1] = u;
tr[u].init(a,p);
splay(u,0);
}
int get_th(int k){
int u = root;
while(true){
pushdown(u);
if(tr[lson].size >= k)u = lson;
else if(tr[lson].size + 1 == k)return u;
else k -= tr[lson].size + 1,u = rson;
}
return u;
}
string ans = "";
void output(int u){
pushdown(u);
if(lson)output(lson);
if(tr[u].v != 0)ans.append(1,tr[u].v);
if(rson)output(rson);
}
void build(int L,int R,int x){
int u = ++ ctx;
tr[u].init(x,R);
tr[R].s[0] = u;
pushup(R);pushup(L);
}
stack<int>ss;
string reverseParentheses(string s) {
int end = -1;
insert(0);
insert(0);
for(int i = 0;i < s.size();i ++){
if(s[i] == '('){
ss.push(end + 1);
}
else if(s[i] == ')'){
int L = ss.top() - 1;
ss.pop();
int R = end + 1;
L = get_th(L + 2);R = get_th(R + 2);
splay(L,0);splay(R,L);
int ls = tr[R].s[0];
tr[ls].flag ^= 1;
swap(tr[ls].s[0],tr[ls].s[1]);
}
else{
char x = s[i];
int L = end,R = end + 1;
L = get_th(L + 2);R = get_th(R + 2);
splay(L,0);splay(R,L);
build(L,R,x);
end ++;
}
}
output(root);
return ans;
}
};
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168544.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...