昨天晚上有红烧牛排骨，白灼罗非鱼，烤翅和我喜欢的草莓蛋糕。

这次比赛我表现比较弱，只做出了前三道，而且第三道还WA了5次。最后一题是很有趣的DP，可惜比赛的时候做不出来。

第一题Perfect Number

题目大意：给定一个整数num，判断是否为完美数。如果num是一个正整数，并且其所有正因子（除num本身之外）之和等于本身，那么num是一个完美数。

思路：关键的观察是正因子是成对出现的，例如d是num的一个因子，那么num/d也是num的一个因子，所以我们只要搜索到\(\sqrt{num}\)就行。

class Solution(object):
    def checkPerfectNumber(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num <= 1:
            return False

        s = 1
        for i in xrange(2, int(num**(0.5))+1):
            if num % i == 0:
                s += i
                if i != num/i:
                    s += num/i
        return s == num

第二题Complex Number Multiplication

题目大意：以a+bi的形式输入两个复数，以同样的方式输出它们的乘积。

简单的字符串处理，就不多说了。

class Solution(object):
    def complexNumberMultiply(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        def getri(s):
            p = s.find('+')
            r = int(s[:p])
            i = int(s[p+1:-1])
            return r, i

        ra, ia = getri(a)
        rb, ib = getri(b)
        r = ra*rb - ia*ib
        i = ra*ib + ia*rb

        return '{}+{}i'.format(r, i)

第三题Boundary of Binary Tree

题目大意：给定一颗二叉树，以逆时针的顺序输出边界。

我这题的思路是这样的：先求左右边界和所有叶子，然后按照左边界，叶子，右边界（逆序）的顺序将边界输出。WA了5次的原因大概是一开始的时候我没有正确求得左右边界，或者说是没有意识到根节点的特殊性。

左边界：从根节点的左子树p开始（不能从根节点开始！！！）。如果p不为空，那么将其加进左边界，并且如果p的左子树非空，将p更新为p的左子树，否则将p更新为p的右子树，直到p为空停止。

右边界：根左边界求法一样，只是在更新p时要先考虑右子树。

叶子：这个比较简单，用DFS。对于当前节点root，如果root有子树，那么它不可能是叶子，递归先后考虑它的左右子树。相反地，如果root没有子树，那么root就是叶子了。

在输出边界的时候要注意判重。

# 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 boundaryOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []

        p = root.left
        left = []
        while p:
            left.append(p)
            p = p.left if p.left else p.right
        p = root.right

        right = []
        while p:
            right.append(p)
            p = p.right if p.right else p.left

        def dfs(root, lst):
            if not root:
                return
            if root.left or root.right:
                dfs(root.left, lst)
                dfs(root.right, lst)
            else:
                lst.append(root)
        leaves = []
        dfs(root, leaves)

        ans = [root.val]
        visited = set([root])
        for p in left:
            if p not in visited:
                ans.append(p.val)
                visited.add(p)

        for p in leaves:
            if p not in visited:
                ans.append(p.val)
                visited.add(p)

        for p in reversed(right):
            if p not in visited:
                ans.append(p.val)
                visited.add(p)

        return ans

第四题Remove Boxes

题目大意：给定一个含有正整数的数组，我们按照如下规则消除数组的元素。每次消除只能消除一个连续的元素都一样的子数组，如果这个子数组长度为k，那么这次消除的得分为k*k。求完全消除给定数组的最大得分。

思路：动态规划，我是用记忆化搜索实现的。dp(l, r)表示消除位置l到r之间所有元素的最大得分。边界条件有两种情况，一是l>r，返回0；二是l=r，返回1。

我们考虑如何消除位置l上的元素。首先扫描l到r之间的元素，标记所有跟l位置一样的元素。现在消除位置l大致上分成两种方法，一是单独消除位置l的元素，得分为1+dp(l+1, r)；二是选某些之前标记过的元素与位置l一起消除，这种情况的最大得分需要另外一个动态规划算法来快速求出。这就是这题有趣的地方！

假设标记出来跟位置l一样的元素位置组成的位置数组为[j0=l, j1, ..., jn]。如果我们让f(j, i)表示使得j位置成为跟l位置一起消除时变成第i个的最大得分。那么转移方程是：

f(j, i) = max{f(k, i-1)+dp(k+1, j-1): k < j}

具体实现看下面代码。下面的实现还有个简单的优化，没有这个优化会TLE。

class Solution(object):
    def removeBoxes(self, boxes):
        """
        :type boxes: List[int]
        :rtype: int
        """
        memo = {}
        def dp(l, r):
            if l > r:
                return 0
            if l == r:
                return 1
            if (l, r) in memo:
                return memo[l, r]

            k = boxes[l]
            lp = []
            for i in xrange(l, r+1):
                if k == boxes[i]:
                    lp.append(i)
            n = len(lp)
            if n == r-l+1:
                memo[l, r] = ans = n * n
                return ans

            ans = 1 + dp(l+1, r)
            tmp = [[0]*n for _ in xrange(n)]
            for i in xrange(1, n):
                for j in xrange(i, n):
                    for k in xrange(i-1, j):
                        if k+1 < j and lp[k]+1 == lp[k+1]:
                            continue
                        tmp[j][i] = max(tmp[j][i], tmp[k][i-1]+dp(lp[k]+1, lp[j]-1))
                    ans = max(ans, tmp[j][i]+(i+1)*(i+1)+dp(lp[j]+1,r))
            memo[l, r] = ans
            return ans

        return dp(0, len(boxes)-1)
leetcode contest