09 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列仿吞。隊(duì)列的聲明如下昏滴，請實(shí)現(xiàn)它的兩個(gè)函數(shù) appendTail 和 deleteHead 痴鳄，分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能钝的。(若隊(duì)列中沒有元素及塘，deleteHead 操作返回 -1 )
class CQueue:
def __init__(self):
self.a = []
self.b = []
def appendTail(self, value: int) -> None:
self.a.append(value)
def deleteHead(self) -> int:
if self.b:
return self.b.pop()
if not self.a:
return -1
while self.a:
self.b.append(self.a.pop())
return self.b.pop()
思路：維護(hù)兩個(gè)棧封锉，一個(gè)輸入棧绵跷，一個(gè)刪除棧膘螟。
心得：list.pop()是最后輸入的一個(gè)元素，empty判斷可以直接用list碾局。
30 包含min函數(shù)的棧
定義棧的數(shù)據(jù)結(jié)構(gòu)荆残，請?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧的最小元素的 min 函數(shù)在該棧中，調(diào)用 min净当、push 及 pop 的時(shí)間復(fù)雜度都是 O(1)内斯。
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.a = []
self.b = []
def push(self, x: int) -> None:
self.a.append(x)
if not self.b or self.b[-1] >= x:
self.b.append(x)
def pop(self) -> None:
if self.a.pop() == self.b[-1]:
self.b.pop()
def top(self) -> int:
return self.a[-1]
def min(self) -> int:
return self.b[-1]
思想：主要在于最小值的計(jì)算，維護(hù)兩個(gè)棧像啼，一個(gè)存儲所有的元素俘闯，一個(gè)存儲最小的。
注:>=忽冻，因?yàn)楫?dāng)=時(shí)真朗，就被移除，因此push的時(shí)候也要考慮等號的情況僧诚。
32 從上到下打印二叉樹
從上到下打印出二叉樹的每個(gè)節(jié)點(diǎn)遮婶，同一層的節(jié)點(diǎn)按照從左到右的順序打印。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from queue import Queue
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
record = Queue()
result = []
if not root:
return result
record.put(root)
while not record.empty():
tmp = record.get()
result.append(tmp.val)
if tmp.left:
record.put(tmp.left)
if tmp.right:
record.put(tmp.right)
return result
思想：創(chuàng)建一個(gè)隊(duì)列湖笨，將新節(jié)點(diǎn)的子節(jié)點(diǎn)不斷放入隊(duì)列中蹭睡，直到隊(duì)列為空。
32 從上到下打印二叉樹 II
從上到下按層打印二叉樹赶么，同一層的節(jié)點(diǎn)按從左到右的順序打印肩豁，每一層打印到一行。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from queue import Queue
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
result = []
record = Queue()
if not root:
return result
record.put(root)
while not record.empty():
tmp1 = []
for i in range(record.qsize()):
tmp = record.get()
tmp1.append(tmp.val)
if tmp.left:
record.put(tmp.left)
if tmp.right:
record.put(tmp.right)
result.append(tmp1)
return result
思想：維護(hù)新的一層的載入節(jié)點(diǎn)辫呻，size只在開始的時(shí)候計(jì)算清钥。
32 從上到下打印二叉樹 III
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
result = []
record = collections.deque()
if not root:
return result
record.append(root)
while record:
tmp = collections.deque()
for i in range(len(record)):
tmp1 = record.popleft()
if len(result)%2:
tmp.appendleft(tmp1.val)
else:
tmp.append(tmp1.val)
if tmp1.left:
record.append(tmp1.left)
if tmp1.right:
record.append(tmp1.right)
result.append(list(tmp))
return result
思想：保持原有的順序讀數(shù)據(jù)，但是將存數(shù)據(jù)的方式設(shè)置為一個(gè)雙向隊(duì)列放闺，以保存數(shù)據(jù)的results作為層數(shù)的隱式指標(biāo)祟昭，用于確定從左往右還是從右往左。
tips：
-
collection.deque()// 雙端隊(duì)列怖侦； -
appendleft()：從右邊往左插入篡悟；append()：從左邊往右插入； -
list(collections.deque())//將queue轉(zhuǎn)化為list匾寝。
