lintcode刷题——python(栈)

xiaoxiao2021-02-28  9

带最小值操作的栈 

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

你实现的栈将支持pushpop 和 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

转载请注明原文地址: https://www.6miu.com/read-450159.html

最新回复(0)