python刷题笔记6--Valid Parentheses

发布时间：2024-12-18 09:01

给定一个字符串，只包含 '(' , ')' , '{' , '}' , '[' 和 ']' 这几个字符，判断输入字符串是否是有效的。

所有的括号必须以正确的顺序闭合，比如 "()" 和 "()[]{}" 是有效的，但 "(]" 和 "([)]" 是无效的。

思路1：建立一个空列表pars，字符串符合要求时正确弹入弹出pars，pars仍为空，返回pars长度为0
值为true。

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        pars = []
        
        parmap = {')': '(', '}': '{', ']': '['}
       
        for c in s:
#          print c
            if c in parmap and parmap[c] == pars[len(pars)-1]:
#               print c
#               print parmap[c]
#               print pars
#               print len(pars)
                pars.pop()
            else:
                pars.append(c)
#                print pars
#           print '***********' 
#       print len(pars)
        return len(pars) == 0
#s=['{','}']
#method=Solution()
#output=method.isValid(s)

#print output

思路2：实际上，通过观察可以发现：如果正要入栈的是右括号，而栈顶元素不是能与之消去的相应

左括号，那么该输入字符串一定是无效的。于是，可以大的加快判断过程。

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        pars = [None]
        parmap = {')': '(', '}': '{', ']': '['}
        for c in s:
            if c in parmap:
                if parmap[c] != pars.pop():
                    return False
            else:
                pars.append(c)
        return len(pars) == 1

说明
当然这里使用dict来存放括号的匹配关系不是必要的，直接通过字符之间ascii码的差值判断也是比较快的。

方法3：

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for i in range(len(s)):
            if s[i] == '(' or s[i] == '[' or s[i] == '{':
                stack.append(s[i])
            if s[i] == ')':
                if stack == [] or stack.pop() != '(':
                    return False
            if s[i] == ']':
                if stack == [] or stack.pop() != '[':
                    return False
            if s[i] == '}':
                if stack == [] or stack.pop() != '{':
                    return False
        if stack:
            return False
        else:
            return True

在列表中添加元素
1）在列表末尾添加元素时，最简单的方式是将元素附加到列表末尾，给列表附加元素时，它将添加到列表末尾

x=[1,2,3,4]
x.append[5]
print x
>>>[1,2,3,4,5]

2）在列表中插入元素使用方法insert（）可在列表的任何位置添加新元素为此需要制定新元素的索引和值

x=[1,2,3,4]
x.insert(0,'5')
print x

>>>[5,1,2,3,4]

从列表中删除元素
1）若知道删除的元素在列表中的位置可使用del语句，可删除任何位置的列表元素，条件是知道其索引（不能访问删除的值）

x=[1,2,3,4]
del  x[1]
print x

>>>[1,3,4]

2）使用pop删除元素，并可访问删除的值。列表相当于一个栈，删除末尾元素相当于弹出栈顶元素。

可删除末尾元素

x=[1,2,3,4,5]
y=x.pop()
print x
print y

>>>[1,2,3,4]
>>>5

可以使用pop删除列表中任何位置元素，只需在括号中指定删除元素的索引即可

x=[1,2,3,4,5]
y=x.pop(0)
print x
print y

>>>[2,3,4,5]
>>>1

3）不知道索引，根据值删除元素，使用remove方法删除元素的值，也可使用删除元素的值。方法remove至删除第一个指定的值，出现了多次，需要使用循环判断是否删除了所有这样的值

x=['a','b','c','d','e']
x.remove('c')
print x
print '**************************'
x=['a','b','c','d','e']
y='b'
x.remove(y)
print x
print y
print '**************************'
x=['a','b','c','d','b','e']
for index, item in enumerate(x):
    print index,item
y='b'
x.remove(y)
print x
for index, item in enumerate(x):
    print index,item
print '**************************' 


>>>
['a', 'b', 'd', 'e']
**************************
['a', 'c', 'd', 'e']
b
**************************
0 a
1 b
2 c
3 d
4 b
5 e
['a', 'c', 'd', 'b', 'e']
0 a
1 c
2 d
3 b
4 e
**************************

python刷题笔记6--Valid Parentheses

相关推荐