26-30题

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