—— 棧 AND 列
A、棧
棧是一種特殊的列表，棧內(nèi)的元素只能通過列表的一端訪問，這一端稱為棧頂?？Х葟d內(nèi)的一摞盤子是現(xiàn)實世界中常見的棧的例子。只能從最上面取盤子，盤子洗凈后，也只能摞在這一摞盤子的最上面。棧被稱為一種后入先出（LIFO，last-in-first-out）的數(shù)據(jù)結(jié)構(gòu)。
由于棧具有后入先出的特點，所以任何不在棧頂?shù)脑囟紵o法訪問。為了得到棧底的元素，必須先拿掉上面的元素。
對棧的兩種主要操作是將一個元素壓入棧和將一個元素彈出棧。入棧使用push()方法，出棧使用pop()方法。下圖演示了入棧和出棧的過程。
棧演示
另一個常用的操作是預(yù)覽棧頂?shù)脑亍op()方法雖然可以訪問棧頂?shù)脑?，但是調(diào)用該方法后，棧頂元素也從棧中被永久性地刪除了。peek()方法則只返回棧頂元素，而不刪除它。
為了記錄棧頂元素的位置，同時也為了標(biāo)記哪里可以加入新元素，我們使用變量top，當(dāng)向棧內(nèi)壓入元素時，該變量增大；從棧內(nèi)彈出元素時，該變量減小。
push()、pop()和peek()是棧的3個主要方法，但是棧還有其他方法和屬性。
Stack() # 建立一個空的棧對象
push() # 把一個元素添加到棧的最頂層
pop() # 刪除棧最頂層的元素，并返回這個元素
peek() # 返回最頂層的元素，并不刪除它
isEmpty() # 判斷棧是否為空
size() # 返回棧中元素的個數(shù)
python 實現(xiàn)stack的模擬實現(xiàn)：
class stack(object): # define 類
def __init__(self):
self.items=[]
def isEmpty(self):
return len(self.items)==0
def push(self,item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
if not self.isEmpty():
return self.items[-1]
def size(self):
return len(self.items)
Leetcode實例
20. Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
解題思路：
- 創(chuàng)建一個空棧，用來存儲尚未找到的左括號；
- 便利字符串，遇到左括號則壓棧，遇到右括號則出棧一個左括號進(jìn)行匹配；
- 在第二步驟過程中，如果空棧情況下遇到右括號，說明缺少左括號，不匹配；
- 在第二步驟遍歷結(jié)束時，棧不為空，說明缺少右括號，不匹配；
源碼如下：
class stack(object):
def __init__(self):
self.items=[]
def isEmpty(self):
return len(self.items)==0
def push(self,item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
if not self.isEmpty():
return self.items[-1]
def size(self):
return len(self.items)
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
LEFT = ['(', '[', '{']
RIGHT = [')', ']', '}']
t=stack()
for i,st in enumerate(s):
if st in LEFT:
t.push(st)
elif st in RIGHT:
if not t or not 1 <= ord(st) - ord(t.peek()) <= 2:#查看ASCII碼
return False
t.pop()
return t.isEmpty()
result = Solution().isValid('[(){([)}]')
print(result)
#------------示例如下---------#
result = Solution().isValid('[(){([)}]')
print(result)
##result##
Flase
42. Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
sample
解題思路：【分治法】
a、先找到max高的一列，將數(shù)據(jù)一分為2；
源碼如下：
class stack(object):
def __init__(self):
self.items=[]
def isEmpty(self):
return len(self.items)==0
def push(self,item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
if not self.isEmpty():
return self.items[-1]
def size(self):
return len(self.items)
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
#dic={'(':')','[':']','{'}
LEFT = ['(', '[', '{']
RIGHT = [')', ']', '}']
t=stack()
for i,st in enumerate(s):
if st in LEFT:
t.push(st)
elif st in RIGHT:
if not t or not 1 <= ord(st) - ord(t.peek()) <= 2:
return False
t.pop()
return t.isEmpty()
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
Left = stack()
Right = stack()
maxnum=height.index(max(height))
Left.push(maxnum)
Right.push((maxnum))
leftTrap=0
rightTrap=0
while (Left.peek() != 0 and not Left.isEmpty()):
leftTrap += max(height[0:Left.peek()]) * (
Left.peek() - height[0:Left.peek()].index(max(height[0:Left.peek()]))) - self.sum(height[height[0:Left.peek()].index(max(height[0:Left.peek()])):Left.peek()])
Left.push(height[0:Left.peek()].index(max(height[0:Left.pop()])))
while (Right.peek()!=len(height)-1 and not Right.isEmpty()):
if height[Right.peek()+1:len(height)]:
maxs = max(height[Right.peek() + 1:len(height)])
else:
maxs=height[-1]
s=height[Right.peek()+1:len(height)].index(maxs)
rightTrap += maxs *(s) - self.sum(
height[Right.peek()+1:s+Right.peek()+1])
Right.push(height[Right.peek()+1:len(height)].index(maxs)+Right.pop()+1)
print(rightTrap+leftTrap)
def sum(self,lists):
num=0
for l in lists:
num+=l
return num
height=[0,1,0,2,1,0,1,3,2,1,2,1,1.5]
Solution().trap(height)
#------------示例如下---------#
height=[0,1,0,2,1,0,1,3,2,1,2,1,1.5]
Solution().trap(height)
##result##
6.5
B、隊列
隊列（queue）：即只允許一端（隊尾）進(jìn)行插入操作，另一端（隊頭）進(jìn)行刪除動作的線性表；是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)（FIFO）
隊列主要應(yīng)用與順序操作問題上，比如打印機(jī)進(jìn)程緩沖、計算機(jī)進(jìn)程以及銀行排隊等；
對象的抽象數(shù)據(jù)類型，主要操作有Enqueue（入隊），Dequeue(出隊)，GetLength(獲取隊列長度)等操作；
其結(jié)構(gòu)代碼如下：
class Queue(object):
def __init__(self): #使用list模擬隊列
self.items=[]
def isEmpty(self):
return len(self.items)==0
def Enqueue(self,item): #入隊
self.items.append(item)
def Dequeue(self): #出隊
return self.items.pop(0)
def Getlength(self): #獲取隊列長度
return len(self.items)
舉例
621. Task Scheduler
Given a char array representing tasks CPU need to do. It contains
capital letters A to Z where different letters represent different
tasks.Tasks could be done without original order. Each task could
be done in one interval. For each interval, CPU could finish one
task or just be idle.
However, there is a non-negative cooling interval n that means
between two same tasks, there must be at least n intervals that
CPU are doing different tasks or just be idle.
You need to return the least number of intervals the CPU will take
to finish all the given tasks.
Example
Input: tasks = ['A','A','A','B','B','B'], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
Note
1、The number of tasks is in the range [1, 10000].
2、The integer n is in the range [0, 100].
