61、调整数组顺序使奇数位于偶数前面
最简单一个数组存偶数一个数组存奇数再合并，稍微快一点的写个冒泡排序O(n^2)。还可以用其它时间复杂度低一些的排序(O(nlogn))，但是要稳定的排序。现在还不会，过几天写
62、包含最小元素的栈
比较简单，记录下最小值就可以了。写的时候发现个问题，当调用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]
64、从上往下打印二叉树的节点
class Solution:
# 返回从上到下每个节点值列表，例：[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、二叉搜索树的后序遍历序列
后序遍历时最后一个节点为根节点，左半边的节点比根节点小，右半边的节点比根节点打，递归判断
# -*- 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、栈的压入弹出序列
虽然给我两个序列我能判断出来，但想了一会不知道如何用代码实现。只好参考别人的思路
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
