lintcode刷题——python（栈）

带最小值操作的栈 

实现一个带有取最小值min方法的栈，min方法将返回当前栈中的最小值。

你实现的栈将支持push，pop 和 min 操作，所有操作要求都在O(1)时间内完成。

 注意事项

如果堆栈中没有数字则不能进行min方法的调用

样例

如下操作：push(1)，pop()，push(2)，push(3)，min()， push(1)，min() 返回 1，2，1

解析：我是用一个列表来模拟栈的，压栈操作，只需要append到数组里面，出栈时，只需要将数组的最后一个元素pop出来就行了。

class MinStack(object): def __init__(self): # do some intialize if necessary self.stack=[] def push(self, number): # write yout code here self.stack.append(number) def pop(self): # pop and return the top item in stack if self.stack!=[]: length=len(self.stack) topItem=self.stack[length-1] self.stack.pop(length-1) return topItem def min(self): # return the minimum number in stack if self.stack!=[]: return min(self.stack)

用栈实现队列 

正如标题所述，你需要使用两个栈来实现队列的一些操作。

队列应支持push(element)，pop() 和 top()，其中pop是弹出队列中的第一个(最前面的)元素。

pop和top方法都应该返回第一个元素的值。

样例

比如push(1), pop(), push(2), push(3), top(), pop()，你应该返回1，2和2

解析：这道题根本不需要双栈。。用一个列表就能实现了。。没鸟题目要求，和上一题目差不多，改改就过了。

class MyQueue: def __init__(self): self.stack1 = [] self.stack2 = [] def push(self, element): # write your code here self.stack1.append(element) def top(self): # write your code here # return the top element if self.stack1!=[]: return self.stack1[0] def pop(self): # write your code here # pop and return the top element if self.stack1!=[]: topItem=self.stack1[0] self.stack1.pop(0) return topItem

有效的括号序列 

给定一个字符串所表示的括号序列，包含以下字符： '(', ')', '{', '}', '[' and ']'， 判定是否是有效的括号序列。

样例

括号必须依照 "()" 顺序表示， "()[]{}" 是有效的括号，但 "([)]"则是无效的括号。

class Solution: # @param {string} s A string # @return {boolean} whether the string is a valid parentheses def isValidParentheses(self, s): # Write your code here # 用一个栈来实现，栈最外面的元素（某个左括号）期待它对应的右括号，如果出现了匹配的右括号，则将其出栈， # 如果来的是其他的左括号，则将其压栈，如果来的是不对应的右括号，直接GG，肯定不是合法括号序列。字符串遍历完了，最终看是不是空栈。 stack=[] if s =="": return True while s!="": currentChar=s[0] s = s[1:] if currentChar=="(" or currentChar=="{" or currentChar=="[": stack.append(currentChar) elif currentChar ==")" or currentChar=="}" or currentChar=="]": lengthStack=len(stack) if lengthStack==0: return False else: if currentChar==")" and stack[lengthStack-1]=="(": stack.pop(lengthStack-1) elif currentChar=="]" and stack[lengthStack-1]=="[": stack.pop(lengthStack - 1) elif currentChar=="}" and stack[lengthStack-1]=="{": stack.pop(lengthStack - 1) else: return False if stack==[]: return True else: return False