1190. 反转每对括号间的子串(栈|splay)[通俗易懂]

1190. 反转每对括号间的子串(栈|splay)[通俗易懂]给出一个字符串 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”输出:”apmnolkjihgf

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
    }
};
  1. 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/169062.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • vue的$on方法_vue基本指令

    vue的$on方法_vue基本指令v-on监听事件可以用v-on指令监听DOM事件,并在触发时运行一些JavaScript代码。事件代码可以直接放到v-on后面,也可以写成一个函数。示例代码如下:<divid

  • 激光测距芯片VL53L0X的使用与代码

    激光测距芯片VL53L0X的使用与代码一、介绍1、原理采用940nm垂直腔面发射激光器(Vertical-CavitySurface-EmittingLaser,简称VCSEL)发射出激光,激光碰到障碍物后反射回来被VL53L0X接收到,测量激光在空气中的传播时间,进而得到距离。VCSEL相关知识2、参数超小体积:4.4×2.4×1.0mm最大测距:2m发射的激光对眼镜安全,且完全不可见。工作电压:2.6to3.5V通信方式:IIC,400KHz,设备地址0x52,最低位是读…

  • idea2022怎么输入激活码_最新在线免费激活2022.02.04

    (idea2022怎么输入激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~CJM5ZJBPHS-eyJsaWNlbnNlSWQiOi…

  • Android源码学习「建议收藏」

    Android源码学习「建议收藏」作为一名程序员,肯定不仅仅限于使用API文档,因为浮于表面是远远不够的。进阶学习的阶段,需要我们保持一颗好奇的心,深入阅读Android源码,学习优秀的代码风格和设计思想,知其然并且知其所以然。引用Google的一张框架图:Applications层,和用户直接交互的就是这些应用程序,它们都是用Java开发的。 JavaFramework层,这一层大部分用Java语言编写。它是An…

  • ActiveMQ入门系列一:认识并安装ActiveMQ(Windows下)

    一、什么是ActiveMQ度娘给出的定义:ActiveMQ的官网打出的标语(如上图):大意是:兼容性好并且功能强大的开源多协议消息中间件,那具体是怎么体现的呢?1.兼容性好:ActiveMQ可以

  • CMSIS的简介_CMSInitiatingOccupancyFraction

    CMSIS的简介_CMSInitiatingOccupancyFractionCortex微控制器软件接口标准(CortexMicrocontrollerSoftwareInterfaceStandard)是ARM和一些编译器厂家以及半导体厂家共同遵循的一套标准,是由A

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号