第一题Maximum Distance in Arrays

给定一个包含数组的数组，每个数组都已经递增排序。我们要做的是从两个数组中各选一个数，使得这两个数的差的绝对值最大。问这个最大的值是多少？

对于第i数组中，取出最大值a，最小值b，然后将(a, i)和(b, i)放进一个数组m里。将数组m按照第一个分量排序，那么对我们有用的只是数组m前面两个元素和后面两个元素。如果第一个元素和最后一个元素来自不一样的数组（第二个分量不一样），那么答案就是这两个元素的第一个分量的差。否则，我们要比较两种情况：第一个元素与倒数第二个元素，第二个元素与最后一个元素。

class Solution(object):
    def maxDistance(self, arrays):
        """
        :type arrays: List[List[int]]
        :rtype: int
        """
        m = []
        for i, a in enumerate(arrays):
            m.append((a[0], i))
            m.append((a[-1], i))
        m.sort(key=lambda x: x[0])
        if m[0][1]!=m[-1][1]:
            return m[-1][0]-m[0][0]
        return max(m[-2][0]-m[0][0], m[-1][0]-m[1][0])

第二题Add One Row to Tree

给定一颗二叉树，以及一个值v和深度d。根节点的深度为1。按如下要求在树的第d层加一行值为v的节点：对于每个深度为d-1的非空节点，增加两个值为v的两个节点，原来的左子树变为现在左节点的左子树，原来的右子树变成现在右节点的右子树。

简单的DFS。

# 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 addOneRow(self, root, v, d):
        """
        :type root: TreeNode
        :type v: int
        :type d: int
        :rtype: TreeNode
        """
        if d==1:
            ans = TreeNode(v)
            ans.left = root
            return ans
        def dfs(root, h):
            if not root:
                return
            if h==d-1:
               t = TreeNode(v)
               t.left = root.left
               root.left = t
               t = TreeNode(v)
               t.right = root.right
               root.right = t
            else:
                dfs(root.left, h+1)
                dfs(root.right, h+1)
        dfs(root, 1)
        return root

第三题Minimum Factorization

给定一个正整数a，寻找最小的正整数b，使得b的所有数字之积为a。如果b超出32位整数的范围，则返回0。

从题目可以知道我们尝试的因子只有从2到9。因为我们希望b最小，所以我们要从9到2递减尝试。需要注意边界情况。

class Solution(object):
    def smallestFactorization(self, a):
        """
        :type a: int
        :rtype: int
        """
        ans = ''
        for i in xrange(9, 1, -1):
            t = 0
            while a%i==0:
                t += 1
                a /= i
            ans = str(i)*t + ans
        ans = int(ans) if ans else 1
        ans = ans if ans < 2**31 and a==1 else 0
        return ans

第四题Task Scheduler

给定一个只包含A到Z字母的数组tasks，每消去一个字符需要1个单位的时间，在消除过程中两个相同字符之间必须相隔n个单位时间。问最少需要多长时间能消除所有字符。

因为相同的任务之间需要相隔n个单位的时间，所以我们可以每次考虑往长度为(n+1)的时间段。首先统计出现次数最多的字母的次数m，那么我们至少需要(m-1)个长度为(n+1)的时间段，在最后那段我们只需要长度为t的时间段，其中t是出线次数为m的字母的总数。根据以上分析，我们至少需要的时间为

(m-1)(n+1)+t

但是(m-1)(n+1)+t有可能小于len(tasks)，答案应该是两者中最大值。

class Solution(object):
    def leastInterval(self, tasks, n):
        """
        :type tasks: List[str]
        :type n: int
        :rtype: int
        """
        cnt = [0] * 26
        for t in tasks:
            cnt[ord(t)-ord('A')] += 1
        cnt.sort(key=lambda x:-x)
        t = 1
        for i in xrange(1, 26):
            if cnt[i]==cnt[0]:
                t += 1
        return max((cnt[0]-1)*(n+1)+t, len(tasks))
leetcode contest