经典面试算法系列
2021-09-03 09:25:35
9次阅读
0个评论
0615面试算法系列 001 有效的括号

力扣原题链接 https://leetcode-cn.com/problems/valid-parentheses/ 给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

这道题就是典型的栈

class Solution:
    def isValid(self, s: str) -> bool:
        b=[]
        for i in s:
            if i in '([{':
                b.append(i)
            elif i ==')':
                if len(b)>0 and b[-1]=='(':
                    b.pop()
                else:
                    return False
            elif i ==']':
                if len(b)>0 and b[-1]=='[':
                    b.pop()
                else:
                    return False

            elif i =='}':
                if len(b)>0 and b[-1]=='{':
                    b.pop()
                else:
                    return False
        return len(b)==0

首先新建一个列表把它当做栈,遍历字符串,如果是左半边部分,进栈,然后三个条件,如果进入了三个任意一个条件,但是是空的或者左半边不在栈顶,就返回false,如果符合出栈。最后判断栈的长度,如果都匹配那么就是0.

002 删除最外层括号

原题链接:https://leetcode-cn.com/problems/remove-outermost-parentheses/ 1021. 删除最外层的括号 有效括号字符串为空 ("")、"(" + A + ")" 或 A + B,其中 A 和 B 都是有效的括号字符串,+ 代表字符串的连接。例如,"","()","(())()" 和 "(()(()))" 都是有效的括号字符串。

如果有效字符串 S 非空,且不存在将其拆分为 S = A+B 的方法,我们称其为原语(primitive),其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 S,考虑将其进行原语化分解,使得:S = P_1 + P_2 + ... + P_k,其中 P_i 是有效括号字符串原语。

对 S 进行原语化分解,删除分解中每个原语字符串的最外层括号,返回 S 。

示例 1:

输入:"(()())(())" 输出:"()()()" 解释:输入字符串为 "(()())(())",原语化分解得到 "(()())" + "(())", 删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。示例 2:

输入:"(()())(())(()(()))" 输出:"()()()()(())" 解释:输入字符串为 "(()())(())(()(()))",原语化分解得到 "(()())" + "(())" + "(()(()))", 删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。示例 3:

输入:"()()" 输出:"" 解释:输入字符串为 "()()",原语化分解得到 "()" + "()", 删除每个部分中的最外层括号后得到 "" + "" = ""。

<pre class="prettyprint lang-js">class Solution:
    def removeOuterParentheses(self, S: str) -> str:
        a=[]
        b=""
        for i in S:
            if i=='(':
                a.append(i)
                if len(a)>1:
                    b+=i
            else:
                a.pop()
                if len(a)>0:
                    b+=i
        return b</pre>

跟上面一个思路,用b装内层的括号,如果是‘(’,进栈,如果长度大于1,说明不是外层的括号,拼接b,如果是右半部分,那么出栈,剩下的长度如果大于0,那么也不是最外层括号,再拼接起来,最后返回b。

很抱歉呀,上周没有更新,上周事情真的是太多了,搞得我心累,这周我一定,嗯一定。嘿嘿。

收藏 0 0

登录 后评论。没有帐号? 注册 一个。

cspython

  • 0 回答
  • 0 粉丝
  • 0 关注