今晚吃的是烤鱼以及手撕鸡。

这次的比赛让我开始怀疑自己的智商了。

第一题Student Attendance Record I

题目大意：给定一个表示只含A、L和P的字符串，问字符串是否满足以下条件：不含多于1个的A或者不含有长度大于2的连续L子字符串。

简单的字符串处理。

class Solution(object):
    def checkRecord(self, s):
        """
        :type s: str
        :rtype: bool
        """
        a = 0
        for c in s:
            if c == 'A':
                a += 1
        if a > 1:
            return False
        if s.find('LLL') != -1:
            return False
        return True

第二题Optimal Division

题目大意：给定一个正整数的数组，代表一个连除的式子。比如[1, 2, 3]表示1/2/3。现在给这个式子加括号改变优先级，使得结果最大。返回结果最大的加了括号的式子。

我的做法相当蠢！我是用dfs枚举所有可能加括号的式子，从中挑出最大的。但是其实不用这么麻烦，这个题目是有公式的：如果数组长度小于3，那么不加括号直接返回。如果长度大于等于3，假设数组为[a0, a1, ..., an-1]，那么只加一个括号返回

a0/(a1/a2/.../an-1)

我那愚蠢的代码：

class Solution(object):
    def optimalDivision(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        def dfs(cur):
            if len(cur) == 1:
                yield cur[0], str(cur[0])
            elif len(cur) == 2:
                yield float(cur[0])/cur[1], '{}/{}'.format(cur[0], cur[1])
            else:
                x = float(cur[0])
                for n in cur[1:]:
                    x /= n
                s = '/'.join(map(str, cur))
                yield x, s
                for i in xrange(1, len(cur)):
                    left = cur[:i]
                    right = cur[i:]
                    for xl, sl in dfs(left):
                        for xr, sr in dfs(right):
                            x = float(xl) / float(xr)
                            if len(left) > 1:
                                sl = '({})'.format(sl)
                            if len(right) > 1:
                                sr = '({})'.format(sr)
                            s = '{}/{}'.format(sl, sr)
                            yield x, s

        ans = ''
        m = 0.0
        for x, s in dfs(nums):
            if x > m:
                m = x
                ans = s

        return ans

小伙伴机智的想法：

class Solution(object):

    def optimalDivision(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        if len(nums) == 1:
            return str(nums[0])
        elif len(nums) == 2:
            return '{}/{}'.format(nums[0], nums[1])
        else:
            return '{}/({})'.format(nums[0], '/'.join(map(str, nums[1:])))

第三题Split Assembled Strings

题目大意：给定一个字符串的数组，进行以下两种操作，返回得到最大的字符串： 1. 将所有字符串拼成一个圈。在拼之前，允许将字符串反序。 2. 在圈上选一个点，展开成一个字符串。

这题我想了挺久的，也是最后做的一道题。我的想法是生成所有可能的字符串，然后挑出最大的。这里有两个优化。第一个优化是先找出最大的字符，那么我们只需要考虑以该字符开始的字符串。第二个优化是对字符串数组strs做一个预处理：strs[i] = max(strs[i], reverse(strs[i]))，这样的话我们可以快速展开字符串组成的圈。

class Solution(object):

    def splitLoopedString(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        pool = []
        for i, s in enumerate(strs):
            strs[i] = max(s, s[::-1])

        def to_right(s, i, j):
            ans = s[j:]
            for k in xrange(1, len(strs)):
                t = (i+k) % len(strs)
                ans += strs[t]
            ans += s[:j]
            return ans

        mc = max(''.join(strs))
        for i, s in enumerate(strs):
            for j, c in enumerate(s):
                if c == mc:
                    pool.append(to_right(s, i, j))
            s = s[::-1]
            for j, c in enumerate(s):
                if c == mc:
                    pool.append(to_right(s, i, j))

        return max(pool)

第四题Student Attendance Record II

题目大意：这是第一题的扩展。给定一个正整数n，返回满足第一题条件的字符串的数目模109+7。

我的想法：首先考虑没有A的情况。用f(n)表示没有A的情况下满足第一题条件字符串数目。那么很简单的我们有如下递归式子：

f(n) = f(n-1) + f(n-2) + f(n-3)

对于有A的情况，因为我们知道A只能有一个，所以我们可以枚举A的位置，得到有A的字符串数目S:
S = sum{f(i)*f(n-1-i): i = 0, 1, ..., n-1}

那么答案就是f(n) + S。

class Solution(object):
    def checkRecord(self, n):
        """
        :type n: int
        :rtype: int
        """
        f = [0] * max((n+1), 4)
        f[0] = 1
        f[1] = 2
        f[2] = 4
        f[3] = 7
        for i in xrange(4, n+1):
            f[i] = (f[i-1]+f[i-2]+f[i-3]) % (10**9+7)
        ans = f[n]
        for i in xrange(n):
            ans = (ans + f[i] * f[n-1-i]) % (10**9+7)
        return ans

我的做法是需要O(n)的空间的。我那机智的小伙伴们是同时考虑A，L和P的，这样会有6种状态。他们写出了状态转移方程，只需用到O(1)的空间。

leetcode contest