61齐苛、調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
最簡(jiǎn)單一個(gè)數(shù)組存偶數(shù)一個(gè)數(shù)組存奇數(shù)再合并，稍微快一點(diǎn)的寫個(gè)冒泡排序O(n^2)。還可以用其它時(shí)間復(fù)雜度低一些的排序(O(nlogn))钉蒲，但是要穩(wěn)定的排序。現(xiàn)在還不會(huì)型将，過幾天寫
62寂祥、包含最小元素的棧
比較簡(jiǎn)單，記錄下最小值就可以了七兜。寫的時(shí)候發(fā)現(xiàn)個(gè)問題丸凭，當(dāng)調(diào)用pop后如果把最小值pop了的話，就會(huì)出問題腕铸。所以改了一下用列表去記錄最小值
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack = []
self.small = []
def push(self, node):
# write code here
self.stack.append(node)
if not self.small:
self.small.append(node)
else:
for index in range(len(self.small)):
if node < self.small[index]:
self.small.insert(index, node)
break
else:
self.small.append(node)
def pop(self):
# write code here
temp = self.stack[-1]
print(temp)
print(self.stack)
print(self.small)
self.stack = self.stack[:-1]
self.small.remove(temp)
return temp
def top(self):
# write code here
return self.stack[-1]
def min(self):
# write code here
if not self.small:
return None
return self.small[0]
63惜犀、二叉樹中值為某一值的路徑
代碼寫了很長(zhǎng)，先把所有的路徑求出來再判斷是否等于該值最后按長(zhǎng)度排序
class Solution(object):
def FindPath(self, root, expectNumber):
def binaryTreePaths(root):
if not root:
return []
queue = [[root]]
rst = []
while queue:
temp = queue.pop(0)
if not temp[-1].left and not temp[-1].right:
rst.append(temp)
else:
if temp[-1].left:
temp1 = temp[:]
temp1.append(temp[-1].left)
queue.append(temp1)
if temp[-1].right:
temp2 = temp[:]
temp2.append(temp[-1].right)
queue.append(temp2)
for i in range(len(rst)):
rst[i] = [x.val for x in rst[i]]
return rst
allpath = binaryTreePaths(root)
temp = []
for i in allpath:
if sum(i) == expectNumber:
i.append(len(i))
temp.append(i)
sort_temp = sorted(temp, key=lambda x:x[-1], reverse=True)
return [x[:-1] for x in sort_temp]
class Solution:
# 返回從上到下每個(gè)節(jié)點(diǎn)值列表虽界，例：[1,2,3]
def PrintFromTopToBottom(self, root):
# write code here
if not root:
return []
queue = [root]
rst = [root]
while queue:
temp = queue.pop(0)
if temp.left:
rst.append(temp.left)
queue.append(temp.left)
if temp.right:
rst.append(temp.right)
queue.append(temp.right)
return [x.val for x in rst]
65、二叉搜索樹的后序遍歷序列
后序遍歷時(shí)最后一個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)酪耳，左半邊的節(jié)點(diǎn)比根節(jié)點(diǎn)小浓恳，右半邊的節(jié)點(diǎn)比根節(jié)點(diǎn)打，遞歸判斷
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
def verify(sequence):
if not sequence:
return False
root = sequence[-1]
for i in range(len(sequence)):
if sequence[i] > root:
break
for j in sequence[i:]:
if j < root:
return False
l = sequence[:i]
r = sequence[i:-1]
left = True
if i > 0:
left = verify(l)
right = True
if i < len(sequence)-1 and left:
right = verify(r)
return right
return verify(sequence)
66碗暗、棧的壓入彈出序列
雖然給我兩個(gè)序列我能判斷出來颈将，但想了一會(huì)不知道如何用代碼實(shí)現(xiàn)。只好參考別人的思路
https://blog.csdn.net/Jillian_sea/article/details/80339471
class Solution:
def IsPopOrder(self, pushV, popV):
# write code here
if not (pushV and popV and len(pushV) == len(popV)):
return False
i=0
top=0
while pushV:
key = self.find(pushV,popV[i])
if not (type(key) == int) :
return False
if key >= top :
del pushV[key]
if key>0:
top = key-1
else:
top = 0
i += 1
else:
return False
return True
def find(self,stack,node):
if not stack:
return False
for i in range(0,len(stack)):
if stack[i] == node :
return i
return False
