LeetCode Contest 43 | 叶某人的碎碎念

感觉这次比赛除第一题之外都是策略/DP题啊。

第一题Find Duplicate Subtrees

题目大意：给定一棵二叉树，找出所有重复出现的子树。

我们要对树的结构进行统计，因此这题关键是对树进行编码。可以参考 606. Construct String from 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 findDuplicateSubtrees(self, root):
        """
        :type root: TreeNode
        :rtype: List[TreeNode]
        """
        seen = {}
        def dfs(root):
            if not root:
                return ''
            left = dfs(root.left)
            right = dfs(root.right)
            s = '{}({})({})'.format(root.val, left, right)
            if s not in seen:
                seen[s] = [1, root]
            else:
                seen[s][0] += 1
            return s
        dfs(root)
        ans = []
        for c, node in seen.values():
            if c > 1:
                ans.append(node)
        return ans

第二题2 Keys Keyboard

题目大意：一开始的时候记事本中有一个字符'A'，我们允许对记事本进行两个操作：

复制：复制笔记本所有字符
粘贴：粘贴最新一次的复制

问得到n个'A'最少进行多少次操作。

假设n = ab。那么去得到n个'A'，我们可以分成两步：

首先从记事本的那个'A', 计算得到a个'A'的最小次数；
然后将记事本中的那a个'A'当作一个整体s，计算得到b个s的最小次数。

通过这两步我们就得到n个'A'，而两步次数之和就是一个可能的操作次数。枚举n的所有分解，选出最小的操作次数即可。

class Solution(object):
    def minSteps(self, n):
        """
        :type n: int
        :rtype: int
        """
        f = [0] * (n+1)
        for k in xrange(2, n+1):
            f[k] = k
            for i in xrange(2, k):
                if k % i != 0:
                    continue
                f[k] = min(f[i]+f[k/i], f[k])
        return f[n]

第三题Dota2 Senate

题目大意：有两个团队（Radiant和Dire）所有人按照某个顺序投票，每一轮投票每个人都可以选择对方一个人让他无法在本轮和下一轮投票。如果某一轮中能投票的人都是某一团队的人，那么该团队胜出。给定一个只含R和D的字符串表示投票的顺序，假设每个人都能做出最优选择。问哪个团队会胜出。

对于能投票的每个人，最优的操作是让在他后面的对方的一个人不能投票。如果在他后面没有对方的人了，就在选一个排在他之前最先能投票的对方的人。在每轮投票之后我们可以剔除被投了票的人，因为当他们同时恢复投票权时，他们又会被投票而失去投票权。所以每一轮投票都可以使能投票的人大概减少一半。当能投票的人都是同一个团队的人就结束了。

我的做法是这样的。首先将R映射到1，D影射到0，得到一个数组s。这样当sum(s)为0或者len(s)时，能投票的人都是同一个团队的人了。然后依次枚举s的元素，如果当前的元素为i，那么表示当前的团队为i，对方团队为1-i。查看之前有没有1-i的票，如果有的话，那么当前i就不能投票，团队1-i减少一票；否则当前的i能投票，将i放进一个数组t里，团队i添加一票。扫描一次s之后，我们就得到一个数组t。这时侯两个团队可能还有票，因为有可能没有排在后面的对方的人可以被投票。所以我们要遍历一次t，按照剩下的票数剔除一些人，得到最终新的s。

class Solution(object):
    def predictPartyVictory(self, senate):
        """
        :type senate: str
        :rtype: str
        """
        s = [1 if c=='R' else 0 for c in senate]
        c = sum(s)
        while c!=0 and c!=len(s):
            rd = [0, 0]
            t = []
            for i in s:
                if rd[1-i] > 0:
                    rd[1-i] -= 1
                else:
                    rd[i] += 1
                    t.append(i)
            s = []
            for i in t:
                if rd[1-i] > 0:
                    rd[1-i] -= 1
                else:
                    s.append(i)
            c = sum(s)
        return 'Dire' if c==0 else 'Radiant'

第四题4 Keys Keyboard

题目大意：想象只有4个键的键盘

(A): 在屏幕打印一个'A'；
(Ctrl-A): 选择整个屏幕；
(Ctrl-C): 复制选择的区域；
(Ctrl-V): 将复制的内容打印到现有的字符后面。

问现在按N次键盘最多能打印多少个'A'？

如果我们假设粘贴板一开始就有'A'，那么键(A)是多余的。如果我们不改变粘贴板的内容，那么按n次(Ctrl-V)会得到n个'A'。接着考虑改变粘贴板的情况。令f[n]表示n次按键能打印'A"的最大数目。假设经过i(0 < i < n-2)次按键之后我们通过(Ctrl-A)+(Ctrl-C)改变了粘贴板，那么能产生的最大数目为：

f[i]+f[i]*f[n-i-2]
这是因为改变粘贴板需要按下两次键盘，改变键盘后粘贴板最多有f[i]个'A'，剩下的n-i-2次按键，是以这f[i]个'A'为基础的，所以这n-i-2最多能生成f[i]*f[n-i-2]个'A'。

class Solution(object):
    def maxA(self, N):
        """
        :type N: int
        :rtype: int
        """
        f = [0] * (N+1)
        for n in xrange(1, N+1):
            f[n] = n
            for i in xrange(n-2):
                f[n] = max(f[i]+f[i]*f[n-i-2], f[n])
        return f[N]

leetcode contest