首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【面试高频题】难度 1.5/5,常规栈运用题

【面试高频题】难度 1.5/5,常规栈运用题

作者头像
宫水三叶的刷题日记
发布2022-10-30 12:47:48
发布2022-10-30 12:47:48
37200
代码可运行
举报
运行总次数:0
代码可运行

题目描述

这是 LeetCode 上的「1190. 反转每对括号间的子串」,难度为「中等」

Tag : 「双端队列」、「栈」

给出一个字符串 s(仅含有小写英文字母和括号)。

请你按照从括号内到外的顺序,逐层反转每对匹配括号中的字符串,并返回最终的结果。

注意,您的结果中 不应 包含任何括号。

示例 1:

代码语言:javascript
代码运行次数:0
运行
复制
输入:s = "(abcd)"

输出:"dcba"

示例 2:

代码语言:javascript
代码运行次数:0
运行
复制
输入:s = "(u(love)i)"

输出:"iloveu"

示例 3:

代码语言:javascript
代码运行次数:0
运行
复制
输入:s = "(ed(et(oc))el)"

输出:"leetcode"

示例 4:

代码语言:javascript
代码运行次数:0
运行
复制
输入:s = "a(bcdefghijkl(mno)p)q"

输出:"apmnolkjihgfedcbq"

提示:

0 <= s.length <= 2000
  • s 中只有小写英文字母和括号
  • 我们确保所有括号都是成对出现的

双端队列(栈)

根据题意,我们可以设计如下处理流程:

  • 从前往后遍历字符串,将不是 ) 的字符串从「尾部」放入队列中
  • 当遇到 ) 时,从队列「尾部」取出字符串,直到遇到 ( 为止,并对取出字符串进行翻转
  • 将翻转完成后字符串重新从「尾部」放入队列
  • 循环上述过程,直到原字符串全部出来完成
  • 从队列「头部」开始取字符,得到最终的答案

可以发现,上述过程需要用到双端队列(或者栈,使用栈的话,需要在最后一步对取出字符串再进行一次翻转)。

Java 中,双端队列可以使用自带的 ArrayDeque, 也可以直接使用数组进行模拟。

代码(使用 ArrayDeque ):

代码语言:javascript
代码运行次数:0
运行
复制
class Solution {
    public String reverseParentheses(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        Deque<Character> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == ')') {
                StringBuilder path = new StringBuilder();
                while (!d.isEmpty()) {
                    if (d.peekLast() != '(') {
                        path.append(d.pollLast());
                    } else {
                        d.pollLast();
                        for (int j = 0; j < path.length(); j++) d.addLast(path.charAt(j));
                        break;
                    }
                }
            } else {
                d.addLast(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!d.isEmpty()) sb.append(d.pollFirst());
        return sb.toString();
    }
}

代码(数组模拟双端队列):

代码语言:javascript
代码运行次数:0
运行
复制
class Solution {
    int N = 2010, he = 0, ta = 0;
    char[] d = new char[N], path = new char[N];
    public String reverseParentheses(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == ')') {
                int idx = 0;
                while (he < ta) {
                    if (d[ta - 1] == '(' && --ta >= 0) {
                        for (int j = 0; j < idx; j++) d[ta++] = path[j];
                        break;
                    } else {
                        path[idx++] = d[--ta];
                    }
                }
            } else {
                d[ta++] = c;
            }
        }
        StringBuilder sb = new StringBuilder();
        while (he < ta) sb.append(d[he++]);
        return sb.toString();
    }
}
  • 时间复杂度:每个 ( 字符只会进出队列一次;) 字符串都不会进出队列,也只会被扫描一次;分析的重点在于普通字符,可以发现每个普通字符进出队列的次数取决于其右边的 ) 的个数,最坏情况下每个字符右边全是右括号,因此复杂度可以当做 O(n^2) ,但实际计算量必然取不满 n^2 ,将普通字符的重复弹出均摊到整个字符串处理过程,可以看作是每个字符串都被遍历常数次,复杂度为O(n)
  • 空间复杂度:
O(n)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1190 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-08-31,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 宫水三叶的刷题日记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 双端队列(栈)
  • 最后
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档