LeetCode Contest 78 | 叶某人的碎碎念

好久没有比赛了，上次比赛还是去年11月了。这次比赛表现比较差，只做出了前两道。后来发现，第三道我跟小伙伴都有正确的想法了，只是没有意识到答案允许有10^-6的误差。

第一题Subdomain Visit Count

给定一个列表，其中的元素形如

"9001 discuss.leetcode.com"
这里的数字表示后面域名（各级域名）的访问量。统计各级域名的访问量。

比较简单的统计。

class Solution:
    def subdomainVisits(self, cpdomains):
        """
        :type cpdomains: List[str]
        :rtype: List[str]
        """
        cnt = collections.defaultdict(int)
        for cp in cpdomains:
            n, addr = cp.split(' ')
            n, addr, p = int(n), '.'+addr, 0
            while p != -1:
                addr = addr[p+1:]
                cnt[addr] += n
                p = addr.find('.')
        return ['{} {}'.format(v, k) for k, v in cnt.items()]

第二题Expressive Words

给定一个单词，我们可以按照相同的字母分组，比如aabcddd可以分组成aa, b, c, ddd。我们可以对单词进行如下操作：用相同的字母延长某个分组，使得其长度大于或者等于3。现在有个字符串S和一个字符串列表words，问words里有多少个单词可以通过操作得到S。

如何判断word是否能通过操作得到S：首先将word和S按字母分组，然后判断word每个分组是否能通过操作得到S相对应的分组。

class Solution:
    def expressiveWords(self, S, words):
        """
        :type S: str
        :type words: List[str]
        :rtype: int
        """
        def group(word):
            return [''.join(g) for _, g in itertools.groupby(word)]

        ps= group(S)
        def check(word):
            pw = group(word)
            if len(ps) != len(pw):
                return False
            for a, b in zip(ps, pw):
                if a[0] != b[0] or len(a) < len(b):
                    return False
                if len(a) == 2 and a != b:
                    return False
            return True

        return sum(check(word) for word in words)

第三题Soup Servings

现在各有Nml的A和B两种汤，以及4种操作：

消耗100ml汤A和0ml汤B
消耗75ml汤A和25ml汤B
消耗50ml汤A和50ml汤B
消耗25ml汤A和75ml汤B

每种操作的执行概率均为0.25。求汤A先被消耗完的概率＋1/2（汤A和汤B同时被消耗完的概率）。答案的误差在10^-6之内被视为正确。

注意到每种操作消耗的数量都是25的倍数，所以我们可以除以25，让数字变得更小更好处理。假设$P(n, m) = <a, b, c>$表示在初始有n个单位汤A和有m个单位汤B的情况下，A先消耗完的概率是a，B先消耗完的概率是b，同时消耗完的概率是c。根据题目我们很容易得到递推公式：

$$P(n, m) = 0.25(P(n-4, m)+P(n-3, m-1)+P(n-2, m-2)+P(n-1, m-3))$$

我的时间全部耗在找出$P(n, m)$公式上了。其实因为答案允许有一定的误差，我们没有必要求出$P(n,m)$的准确公式，只需利用上述递推公式就行。

令$f(n, m) = a+0.5c$, 其中$<a, b, c> = P(n, m)$. 那么$f(n, m)$同样满足上述递推公式：

$$f(n, m) = 0.25(f(n-4, m)+f(n-3, m-1)+f(n-2, m-2)+f(n-1, m-3))$$

因为$f(n, m) \le 1$，所以当迭代次数够多时，$f(n-i, m-j)$对$f(n, m)$的影响是在误差范围之内的。对于这些$f(n-i, m-j)$，我们可以认为$f(n-i, m-j)=1$，因为根据我们的操作，汤A“几乎”总是先消耗完的。

class Solution:
    def soupServings(self, N):
        """
        :type N: int
        :rtype: float
        """
        N = (N+24) // 25

        memo = {}
        def f(n, m):
            if n <= 0 and m <= 0:
                return 0.5
            if n <= 0 or 2*N-m-n > 400:
                return 1.0
            if m <= 0:
                return 0
            if (n,  m) in memo:
                return memo[n, m]
            memo[n, m] = 0.25 * sum(f(n+i-4, m-i) for i in range(4))
            return memo[n, m]

        return f(N, N)

第四题Chalkboard XOR Game

给定一个非负整数数组，Alice和Bob轮流消除其中一个数字。如果消除之后的数组的所有数字的xor为0，那么就判定为输。如果Alice先手，问她是否有必赢策略。注意：如果初始数组的xor为0，规定Alice自动成为赢家。

这题的关键在于：如果数组长度为偶数，且总xor不为0，那么先手必胜。这是因为先手总是可以找到一个数字，使得剩下来的数组总xor不为0。不然的话，一开始的数字会全部一样并等于总xor，但是这样一来偶数个一样的数的总xor为0，跟假设矛盾。

class Solution:
    def xorGame(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        x = 0
        for n in nums:
            x ^= n
        return x == 0 or len(nums) & 1 == 0

leetcode contest