# 每日一题之LeetCode 栈简单题集合496，682,232,225,155,844，20

496 下一个最大的元素

class Solution:
def nextGreaterElement(self, nums1, nums2):

``````     L=[]
for i in nums1:
k=nums2.index(i)
lenth2=len(nums2)
if k==lenth2-1:
L.append(-1)
for j in range(k+1,lenth2):
if nums2[j]>i:
L.append(nums2[j])
break

if j==lenth2-1:
L.append(-1)
return L  ``````

class Solution:
def nextGreaterElement(self, nums1, nums2):

``````                    d = {}
st = []
ans = []

for x in nums2:
while len(st) and st[-1] < x:
d[st.pop()] = x
st.append(x)

for x in nums1:
ans.append(d.get(x, -1))

return ans``````

682.棒球比赛

ops= ["35","-32","C","39","+","-48","C","5","88","-52","+","C","D","D","100","C","+","-74","53","59"]
L=[]
sum=[]
lenth=len(ops)
for i in range(0,lenth):
if i==0:
sum.append(int(ops[i]))
else:

``````   if ops[i]==‘C‘:

sum.insert(0,0)

sum.insert(1,0)

sum.pop()

elif  ops[i]==‘D‘:
sum.append(sum[i-1]*2)

elif ops[i]==‘+‘:
sum.append(sum[i-1]+sum[i-2])
else :

sum.append(int(ops[i]))``````

score=0
for j in sum:
score=score+j
print(score)
232.用栈实现队列

class MyQueue:

``````def __init__(self):
"""
"""
self.stact=[]
self.queue=[]
self.len=0

def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: void
"""
self.stact.append(x)
self.len=self.len+1

def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""

while len(self.stact)!=0:
self.queue.append(self.stact.pop())

x = self.queue.pop()

while len(self.queue)!= 0:
self.stact.append(self.queue.pop())

self.len -=1
return x

def peek(self):
"""
Get the front element.
:rtype: int
"""

while len(self.stact)!=0:
self.queue.append(self.stact.pop())

x = self.queue.pop()
self.queue.append(x)
while len(self.queue)!= 0:
self.stact.append(self.queue.pop())

return x

def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""

if self.len==0:
return False``````

class MyQueue:

``````def __init__(self):
"""
"""
self.queue = []

def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: void
"""
self.queue.append(x)

def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
if len(self.queue)>0:
print( self.queue.pop(0))

def peek(self):
"""
Get the front element.
:rtype: int
"""
if len(self.queue)>0:
print( self.queue[0])

def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
if len(self.queue)>0:
return False
else:
return True
def shuchu(self):
for i in self.queue:
print(i)``````

235，用队列来实现栈

class MyStack:

``````def __init__(self):
"""
"""
self.queue = []

def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: void
"""
self.queue.append(x)

def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
if len(self.queue)>0:
return self.queue.pop()
#len(self.queue)-=1

def top(self):
"""
Get the front element.
:rtype: int
"""
if len(self.queue)>0:
return self.queue[-1]

def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
if len(self.queue)>0:
return False
else:
return True``````

155，最小栈

class MinStack:

``````def __init__(self):
"""
"""
self.queue = []
self.min=None
def push(self, x):
"""
:type x: int
:rtype: void
"""
self.queue.append(x)
self.min=min(self.queue)

def pop(self):
"""
:rtype: void
"""
if len(self.queue)>0:
self.queue.pop()
self.min=min(self.queue)
return self.queue
def top(self):
"""
:rtype: int
"""
if len(self.queue)>0:
return self.queue[-1]

def getMin(self):
"""
:rtype: int
"""
return self.min``````

class MinStack(object):
def init(self):
"""
"""
self.stack = []
self.min = None

``````def push(self, x):
"""
:type x: int
:rtype: void
"""
self.stack.append(x)
if self.min == None or self.min > x:
self.min = x

def pop(self):
"""
:rtype: void
"""

popItem = self.stack.pop()
if len(self.stack) == 0:
self.min = None
return popItem

if popItem == self.min:
self.min = self.stack[0]
for i in self.stack:
if i < self.min:
self.min = i
return popItem

def top(self):
"""
:rtype: int
"""
return self.stack[-1]

def getMin(self):
"""
:rtype: int
"""
return self.min``````

844.比较含退格的字符串

class Solution:

``````def backspaceCompare(self, S, T):
"""
:type S: str
:type T: str
:rtype: bool
"""

S1=back(S)
T1=back(T)
if S1==T1:
return True
else:
return False``````

def back(L):
K=[]
for i in L:
if i==‘#‘ and len(K)!=0:

``````               K.pop()
elif  i==‘#‘ and len(K)==0:
pass
else:
K.append(i)
return K``````

20，有效的括号

class Solution:
def isValid(self, s):

``````    a=list(s)
b=[]                            #存放左括号的栈  qc:list当做栈
c={‘(‘:‘)‘,‘[‘:‘]‘,‘{‘:‘}‘}     #字典存储     qc；key:value 键：值
for i in a:
if i==‘‘:
return True
elif i in c: #如果是字典中的键，即左括号，放进栈
b.append(i)
else:
if len(b)==0: #先判断是否有左括号存在
return False
else:
#字典得到该键的值==栈顶值对应的右括号
if c.get(b[-1])!=i:
return False
else:
del b[-1]      #删除栈顶元素
if len(b)!=0:  #若还存在左括号，此时已没有右括号，出错
return False
return True``````

PS.写这么一些题还是有用的，至少遇到一些题知道其实是采用了栈的思想，以前都是瞎写。编程还是要有思维。

## LeetCode 第 73 题 (Set Matrix Zeroes)

LeetCode 第 73 题 (Set Matrix Zeroes) Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably a bad idea. A simple impro

## leetcode中第一题twosum问题解答算法的可行性证明

leetcode中第一题twosum问题解答算法的可行性证明 一.引入 关于leetcode中第一题twosum问题,网上已有不少高人做出过解答,并提出了切实可行的算法实现.我在解答该题时参考了博客http://www.zixue7.com/article-9576-1.html的解答.为让读者更直观地阅读和理解本文,先简要摘录以上博客的内容如下: 题目还原 Two Sum Given an array of integers, find two numbers such that they a

## LeetCode 第 342 题（Power of Four）

LeetCode 第 342 题(Power of Four) Given an integer (signed 32 bits), write a function to check whether it is a power of 4. Example: Given num = 16, return true. Given num = 5, return false. Follow up: Could you solve it without loops/recursion? 题目很简单,

## Leetcode第五题_Longest Palindromic Substring

Longest Palindromic Substring Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. Leetcode第5题,题目大概意思是给一个字符串,从中找出最长的回文串,所谓回文串,就是