今天晚上在朋友家做好饭已经过了比赛时间了，我们是边吃着饭边喝着酒来写代码。牛肉炖土豆是一如既往的美味，新尝试的豆腐煮白菜也很不错。这次朋友买了Habanero，辣味惊人，我是打着喷嚏做菜的😢

第一题Set Mismatch

题目大意：给定一个长度为n数值在1到n之间的数组。已知其中一个数字出现一个，另一个数字没有出现。找出这两个数字。

简单的统计。

class Solution(object):
    def findErrorNums(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ans = [0, 0, 0]
        cnt = [0] * len(nums)
        for i in nums:
            cnt[i-1] += 1
        for i, c in enumerate(cnt):
            ans[c] = i+1
        return [ans[2], ans[0]]

第二题Maximum Length of Pair Chain

题目大意：给定n个数对。每个数对的第一个数都小于第二个数。数对(c, d)可以跟在(a, b)后面当且仅当b < c。问这给定的n个数对能按照这种方式串起来的最大长度是多少。

我印象中在LeetCode出现过两道类似这道题。现在只找到其中一道：435. Non-overlapping Intervals。做法都是贪心。对于这题，我们知道如果两个数对是相交的，那么这两个数对最多只能取一个。如果我们对所有数对按照第一个分量排序，那么我们应该选择相交的数对中第二分量最小的那个，这样就后面的选择就可以多点。

class Solution(object):
    def findLongestChain(self, pairs):
        """
        :type pairs: List[List[int]]
        :rtype: int
        """
        pairs.sort()
        ans, cur = 0, -2**32
        for a, b in pairs:
            if a > cur:
                ans += 1
                cur = b
            else:
                cur = min(b, cur)
        return ans

第三题Palindromic Substrings

题目大意：给定一个字符串，找出字符串中所有回文子字符串的总数目。

比较简单的题目，直接看代码就应该清楚。

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        ans = 0
        for i in xrange(len(s)):
            j = k = i
            while j >= 0 and k < len(s) and s[j] == s[k]:
                ans += 1
                j -= 1
                k += 1
        for i in xrange(len(s)-1):
            if s[i] != s[i+1]:
                continue
            j, k = i, i+1
            while j>=0 and k < len(s) and s[j] == s[k]:
                ans += 1
                j -= 1
                k += 1
        return ans

第四题Replace Words

题目大意：给定一个词根字典以及一句话，将话中的所有单词用其最短词根替换。如果单词没有词根，那么保留原词。

直接模拟。

class Solution(object):
    def replaceWords(self, dict, sentence):
        """
        :type dict: List[str]
        :type sentence: str
        :rtype: str
        """
        words = sentence.split(' ')
        dict = set(dict)
        ans = []
        for word in words:
            for i in xrange(len(word)):
                if word[:i] in dict:
                    ans.append(word[:i])
                    break
            else:
                ans.append(word)
        return ' '.join(ans)
leetcode contest