—— 棧 AND 列
A软舌、棧
棧是一種特殊的列表殉疼，棧內(nèi)的元素只能通過列表的一端訪問梯浪，這一端稱為棧頂捌年。咖啡廳內(nèi)的一摞盤子是現(xiàn)實(shí)世界中常見的棧的例子挂洛。只能從最上面取盤子礼预，盤子洗凈后，也只能摞在這一摞盤子的最上面虏劲。棧被稱為一種后入先出（LIFO托酸，last-in-first-out）的數(shù)據(jù)結(jié)構(gòu)。
由于棧具有后入先出的特點(diǎn)柒巫，所以任何不在棧頂?shù)脑囟紵o法訪問励堡。為了得到棧底的元素，必須先拿掉上面的元素堡掏。
對棧的兩種主要操作是將一個(gè)元素壓入棧和將一個(gè)元素彈出棧应结。入棧使用push()方法，出棧使用pop()方法泉唁。下圖演示了入棧和出棧的過程鹅龄。
棧演示
另一個(gè)常用的操作是預(yù)覽棧頂?shù)脑亍op()方法雖然可以訪問棧頂?shù)脑赝ば螅钦{(diào)用該方法后扮休，棧頂元素也從棧中被永久性地刪除了。peek()方法則只返回棧頂元素拴鸵，而不刪除它肛炮。
為了記錄棧頂元素的位置，同時(shí)也為了標(biāo)記哪里可以加入新元素宝踪，我們使用變量top侨糟，當(dāng)向棧內(nèi)壓入元素時(shí)，該變量增大瘩燥；從棧內(nèi)彈出元素時(shí)秕重，該變量減小。
push()厉膀、pop()和peek()是棧的3個(gè)主要方法溶耘，但是棧還有其他方法和屬性。
Stack() # 建立一個(gè)空的棧對象
push() # 把一個(gè)元素添加到棧的最頂層
pop() # 刪除棧最頂層的元素服鹅，并返回這個(gè)元素
peek() # 返回最頂層的元素凳兵，并不刪除它
isEmpty() # 判斷棧是否為空
size() # 返回棧中元素的個(gè)數(shù)
python 實(shí)現(xiàn)stack的模擬實(shí)現(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實(shí)例
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)建一個(gè)空棧，用來存儲(chǔ)尚未找到的左括號企软；
- 便利字符串庐扫，遇到左括號則壓棧，遇到右括號則出棧一個(gè)左括號進(jìn)行匹配；
- 在第二步驟過程中形庭，如果空棧情況下遇到右括號铅辞，說明缺少左括號，不匹配萨醒；
- 在第二步驟遍歷結(jié)束時(shí)斟珊，棧不為空，說明缺少右括號富纸，不匹配囤踩；
源碼如下：
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、隊(duì)列
隊(duì)列（queue）：即只允許一端（隊(duì)尾）進(jìn)行插入操作辞州，另一端（隊(duì)頭）進(jìn)行刪除動(dòng)作的線性表怔锌；是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)（FIFO）
隊(duì)列主要應(yīng)用與順序操作問題上寥粹，比如打印機(jī)進(jìn)程緩沖变过、計(jì)算機(jī)進(jìn)程以及銀行排隊(duì)等；
對象的抽象數(shù)據(jù)類型涝涤，主要操作有Enqueue（入隊(duì)）媚狰，Dequeue(出隊(duì))，GetLength(獲取隊(duì)列長度)等操作阔拳；
其結(jié)構(gòu)代碼如下：
class Queue(object):
def __init__(self): #使用list模擬隊(duì)列
self.items=[]
def isEmpty(self):
return len(self.items)==0
def Enqueue(self,item): #入隊(duì)
self.items.append(item)
def Dequeue(self): #出隊(duì)
return self.items.pop(0)
def Getlength(self): #獲取隊(duì)列長度
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].
