LeetCode Contest 44 | 叶某人的碎碎念

这次比赛很遗憾只能做出三题，没有做出第三题。第三题其实不难，只是比赛的时候脑袋就像面粉加水一团浆糊没有反应过来。

第一题Two Sum IV - Input is a BST

题目大意：给定一颗二叉搜索树和一个目标值，问是否存在树中的两个数使得它们的和为目标值。

好吧，我是写博客的时候才发现原来输入的是一颗搜索树。题目大概是想让我们快速判定一个数是否在给定的二叉搜索树中吧。我是首先遍历二叉树统计每个数出现的次数，然后枚举每个出现的数a，如果目标值减去a也出现过则返回True。注意要考虑a和目标值减去a是一样的情况。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        nums = collections.defaultdict(int)
        def dfs(root):
            if not root:
                return
            n = root.val
            nums[n] += 1
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        for n in nums.keys():
            m = k - n
            if n != m and m in nums:
                return True
            if n == m and nums[n] > 1:
                return True
        return False

第二题Maximum Binary Tree

题目大意：给定一个不含重复数字的数组，按照以下规则构造一颗二叉树：

根节点是数组中最大的数字
左子树是最大数字左边的子数组按照此规则构造的二叉树
右子树是最大数字右边的子数组按照此规则构造的二叉树

比较简单的递归。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        def build(i, j):
            if i > j:
                return None
            k = i
            for x in xrange(i, j+1):
                if nums[k] < nums[x]:
                    k = x
            ans = TreeNode(nums[k])
            ans.left = build(i, k-1)
            ans.right = build(k+1, j)
            return ans
        return build(0, len(nums)-1)

第三题Print Binary Tree

题目大意：将一颗二叉树按照规定输出为一个 m x n 的二维矩阵：

行的数目m为树的高度
列的数目总是奇数
根节点要居中，使得整个矩阵分成左右两部分
左右子树按照同样的规则输出在矩阵的左右两部分
空节点用空字符串""表示

首先计算树的高度h，那么我们有

m = h, n = 2^h-1
然后根据规则递归构造数组就行。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def printTree(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[str]]
        """
        def height(root):
            if not root:
                return 0
            return max(height(root.left), height(root.right))+1
        h = height(root)
        def pt(root, h):
            if not root:
                tmp = ['']*((1<<h)-1)
                ans = []
                for _ in xrange(h):
                    ans.append(tmp[:])
                return ans
            if h > 0:
                left = pt(root.left, h-1)
                right = pt(root.right, h-1)
                ans = [['']*((1<<h)-1)]
                ans[0][(1<<(h-1))-1] = '{}'.format(root.val)
                for a, b in zip(left, right):
                    ans.append(a+['']+b)
                return ans
        return pt(root, h)

第四题Coin Path

题目大意：给定一个下标从1开始长度为N的数组A和一个整数B。A[i]如果大于等于0则表示去第i位置需要消耗的金钱，如果为-1则表示第i个位置无法到达。数字B代表最大可跳跃的步数。现在要从第1个位置跳到第N个位置，问消耗金钱最小的路径是什么。如果有多条可行方案，输出排序最小的路径。

用f[i]表示从第1个位置跳到第i个位置的最小花费（如果f[i]=-1表示第i个位置无法到达），那么我们有如下转移方程：

f[k] = min(f[i]+A[k]: i=k-B, k-B+1, ..., k-1)
而且在更新f[k]时，我们可以顺便存储一条从第1个位置出发到第k个位置的路径。

class Solution(object):
    def cheapestJump(self, A, B):
        """
        :type A: List[int]
        :type B: int
        :rtype: List[int]
        """
        n = len(A)
        f = [0] * n
        ans = [[] for _ in xrange(n)]
        ans[0] = [1]
        for k in xrange(1, n):
            if A[k] == -1:
                f[k] = -1
                continue
            f[k] = 2**31
            for i in xrange(max(k-B, 0), k):
                if f[i] == -1:
                    continue
                if f[k] > f[i]+A[k]:
                    f[k] = f[i]+A[k]
                    ans[k] = ans[i] + [k+1]
                elif f[k] == f[i]+A[k]:
                    tmp = ans[i] + [k+1]
                    if ans[k] > tmp:
                        ans[k] = tmp
            if f[k] == 2**31:
                f[k] = -1
        return ans[n-1]

leetcode contest