26、重建二叉树
根据先序，中序来构建二叉树。
不会做😔，虽然知道怎么构建，但是没想到如何用代码实现，再次参考别人的思路，不出意外还是递归解决。
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if not preorder:
return None
n = len(preorder)
inorder = dict(zip(inorder, xrange(n)))
def helper(i, j):
if i > j:
return None
root = TreeNode(preorder.pop(0))
iroot = inorder[root.val]
root.left = helper(i, iroot - 1)
root.right = helper(iroot + 1, j)
return root
return helper(0, n - 1)
27、滑动窗口的最大值
能想到的就只有最笨的完全遍历一遍，记录下三个数，找到最大值。然后在此基础上稍微优化一点，一个指针记录下当前窗口最大值和索引，一个指针遍历，当遍历指针跟记录指针距离大于3的时候更新记录指针。
应该还有其它的优化方法。虽然写了很长，但是用到了一点动态规划的东西，写完还是很有成就感的。先把自己写的结果贴上
class Solution():
def __init__(self):
self.res = []
def getmaxperwindow(self, num, size):
def get_top(num, n, size):
'''
:param num: 数组
:param n: 从哪个个索引开始
:param size：窗口大小
:return: 该窗口最大值
'''
rst = [-10e10, -1]
for i in range(size):
if num[n+i] >= rst[0]:
rst = [num[n+i], n+i]
return rst
temp = get_top(num, 0, size)
self.res.append(temp[0])
for j in range(size, len(num)):
if j > size-1+temp[1]:
temp = get_top(num, temp[1]+1, size)
self.res.append(temp[0])
continue
elif num[j] >= temp[0]:
temp = [num[j], j]
self.res.append(temp[0])
else:
self.res.append(temp[0])
return self.res
28、用两个栈实现队列
一道比较经典的题，很多地方都看到过。栈是先入后出，队列是先入先出。
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
# write code here
self.stack1.append(node)
def pop(self):
# return xx
if self.stack2:
return self.stack2.pop()
while(self.stack1):
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
29、旋转数组的最小数字
只想到暴力地遍历，看了下别人的可以用二分查找，找中间数字和左端点，如果中间数字大于左端点，那么最小值肯定在右半部分，如果中间数字小于左端点，那么最小值肯定在左半部分
# -*- coding:utf-8 -*-
class Solution:
def findMinnum(self, num):
l = 0
r = len(num)-1
if num[-1] > num[0]:
return num[0]
while True:
if r - l <= 1:
return min(num[r], num[l])
else:
mid = (l+r)//2
if num[mid] == num[l]:
return num[mid]
elif num[mid] > num[l]:
l = mid
else:
r = mid
30、丑数
class Solution(object):
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""
if num == 0:
return False
while num%2 == 0:
num /= 2
while num%3 == 0:
num /= 3
while num%5 == 0:
num /= 5
if int(num) == 1:
return True
return False
