【刷题日记】1021. 删除最外层的括号

简介: 本次刷题日记的第 50 篇,力扣题为:1021. 删除最外层的括号,简单

本次刷题日记的第 50 篇,力扣题为:1021. 删除最外层的括号简单

一、题目描述:

image.png

第一感觉这个题有点啰嗦,需要咱们静下心来好好阅读和查看,肯定很简单的


二、这道题考察了什么思想?你的思路是什么?

仔细查看这道题,其实很简单,实际上就是和题目标题说的一样,删除最外层的括号

但是这里需要明确的是,是删除原语的最外层括号

  • 题目给出的一个字符串,我们找到字符串中的包含每一个原语的边界,且删除掉原语左右两边的括号,掐头去尾就行,剩下的字符串就是原语,即为题目答案

分析

仔细来看,不管原因的呈现形式是什么样子的,根据题意,我们知道,原语一定是被 () 包起来的,我们只需要找到完整的括号即可

看到括号,是否会想起使用栈的方式来进行处理呢

遍历给出的字符串,当是 ( 的时候,入栈,是 )出栈,这样我们就能识别到是一个 括号了

但是我们不仅仅要识别是否是完整的括号,我们还需要将原语提取出来

提取原语

那么我们可以这么思考一下,将一个大象装进冰箱分为几步呢?

  • 打开冰箱
  • 把冰箱装进去
  • 关上冰箱

那么对于这个题,我们是不是也是可以这样?

  • 找到原语边界
  • 去掉原语最外层的括号
  • 拼接原语

如图:

提取原语的话,我们就可以按照上述的栈的思路走,用一个 stack 来表示我们需要识别的原语边界用 res 来存放实际的原语

image.png

如何找到一个包含原语的边界呢?

例如,我们遍历图中的字符串,识别到是 ( 就将字符入栈到 stack 中,识别到是 ) 就将栈顶的字符弹出

另外我们识别到 stack 不为空的时候,说明此时我们在遍历原语,则将该部分加入到 res 中即可,最终 res 即为我们拼接的最终原语

三、编码

根据上述逻辑和分析,我们就可以翻译成如下代码

编码需要注意,我们是要校验到 stack 不为空的时候,才会将当前的数据看做是原语的一部分,并且加入到 res 结果集中

编码如下:

func removeOuterParentheses(s string) string {
    var res, stack []rune
    for _,ch := range s {
        if ch == ')' {
            stack = stack[:len(stack) - 1]
        }
        if len(stack) > 0 {
            res = append(res, ch)
        }
        if ch == '(' {
            stack = append(stack, ch)
        }
    }
    return string(res)
}

四、总结:

此处的时间复杂度比较明确,我们只遍历了一遍 s ,因此时间复杂度是 O(n) ,空间复杂度也是 O(n),因为我们引入了栈空间,此处占空间的最大长度会是 s 的长度

原题地址:1021. 删除最外层的括号

今天就到这里,学习所得,若有偏差,还请斧正

欢迎点赞,关注,收藏

朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力

image.png

好了,本次就到这里

技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。

我是阿兵云原生,欢迎点赞关注收藏,下次见~


相关文章
|
2月前
leetcode代码记录(有效的括号
leetcode代码记录(有效的括号
18 1
|
2月前
|
存储 算法 索引
刷题专栏(二十六):字符串中的第一个唯一字符
刷题专栏(二十六):字符串中的第一个唯一字符
84 1
刷题专栏(二十六):字符串中的第一个唯一字符
|
12月前
|
Cloud Native
【刷题日记】316. 去除重复字母
本次刷题日记的第 42 篇,力扣题为:316. 去除重复字母 ,中等
|
2月前
|
测试技术
【刷题-牛客】出栈、入栈的顺序匹配 (代码+动态演示)
【刷题-牛客】出栈、入栈的顺序匹配 (代码+动态演示)
52 0
|
8月前
|
算法 索引
代码随想录算法训练营第九天 | LeetCode 8. 找出字符串中第一个匹配项的下标、LeetCode 459. 重复的子字符串
代码随想录算法训练营第九天 | LeetCode 8. 找出字符串中第一个匹配项的下标、LeetCode 459. 重复的子字符串
23 0
|
8月前
|
算法
代码随想录算法训练营第十一天 | LeetCode 20. 有效的括号、LeetCode 1047. 删除字符串中的所有相邻重复项、LeetCode 150. 逆波兰表达式求值
代码随想录算法训练营第十一天 | LeetCode 20. 有效的括号、LeetCode 1047. 删除字符串中的所有相邻重复项、LeetCode 150. 逆波兰表达式求值
43 0
|
8月前
|
算法
代码随想录算法训练营第11天 | 20. 有效的括号, 1047. 删除字符串中的所有相邻重复项,150. 逆波兰表达式求值
代码随想录算法训练营第11天 | 20. 有效的括号, 1047. 删除字符串中的所有相邻重复项,150. 逆波兰表达式求值
|
12月前
|
算法 Go Cloud Native
【刷题日记】890. 查找和替换模式
本次刷题日记的第 62 篇,力扣题为:890. 查找和替换模式,中等
|
数据安全/隐私保护
列表循环练习题
列表循环练习题
C/C++ leetcode刷题的各种小tips记录
C/C++ leetcode刷题的各种小tips记录
120 0