61、調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
最簡單一個數(shù)組存偶數(shù)一個數(shù)組存奇數(shù)再合并，稍微快一點的寫個冒泡排序O(n^2)。還可以用其它時間復(fù)雜度低一些的排序(O(nlogn))，但是要穩(wěn)定的排序。現(xiàn)在還不會，過幾天寫
62、包含最小元素的棧
比較簡單，記錄下最小值就可以了。寫的時候發(fā)現(xiàn)個問題，當(dāng)調(diào)用pop后如果把最小值pop了的話，就會出問題。所以改了一下用列表去記錄最小值
# -*- 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、二叉樹中值為某一值的路徑
代碼寫了很長，先把所有的路徑求出來再判斷是否等于該值最后按長度排序
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:
# 返回從上到下每個節(jié)點值列表，例：[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、二叉搜索樹的后序遍歷序列
后序遍歷時最后一個節(jié)點為根節(jié)點，左半邊的節(jié)點比根節(jié)點小，右半邊的節(jié)點比根節(jié)點打，遞歸判斷
# -*- 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、棧的壓入彈出序列
雖然給我兩個序列我能判斷出來，但想了一會不知道如何用代碼實現(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
