今晚有手撕鸡，玉米鸡汤，红烧牛排骨和金鲳鱼。本来还准备了要做个豆豉炒苦瓜的，但是那手撕鸡实在太大了，所以就苦瓜没有必要做了。这手撕鸡很好吃：先是用鸡熬两个小时做鸡汤，然后将鸡过冷水去骨撕条，在鸡肉上放上辣椒面与白芝麻并浇以热油，最后加上些许醋拌匀即可。

这次比赛比较简单，但是还是WA了两次了，顺带吐槽一下自己写代码的速度。

第一题Reverse String II

题目大意：给定一个字符串和一个数k，对于字符串的每2k长度的子字符串，逆序前k个字符串。

没什么好说的，就直接干就好：首先将字符串按长度为2k分块，然后处理每一个分块。

class Solution(object):
    def reverseStr(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        lst = []
        for i in xrange(0, len(s), 2*k):
            lst.append(s[i:i+2*k])
        for i, s in enumerate(lst):
            lst[i] = s[:k][::-1]+s[k:]
        return ''.join(lst)

第二题Minimum Time Difference

题目大意：给定一个包含"hh:mm"格式的时间字符串列表，求任意两个时间分钟时间差的最小值。

首先将"hh:mm"转化成分钟形式：60*hh+mm，然后排序。排序后寻找相邻两个数之间的差的最小值，最后处理一下第一个数与最后一个数之间的差。

class Solution(object):
    def findMinDifference(self, timePoints):
        """
        :type timePoints: List[str]
        :rtype: int
        """
        def get(x):
            return int(x[:2])*60+int(x[3:])
        tp = sorted(map(get, timePoints))
        ans = 2 ** 31
        for i in xrange(len(tp)-1):
            ans = min(ans, tp[i+1]-tp[i])
        ans = min(ans, get('24:00')-tp[-1]+tp[0])
        return ans

第三题Construct Binary Tree from String

题目大意：给定一个表示一个二叉树的字符串，要求转化成二叉树。
样例输入："4(2(3)(1))(6(5))"。

# 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 str2tree(self, s):
        """
        :type s: str
        :rtype: TreeNode
        """
        if not s:
            return None
        def build(s):
            i = j = 0
            while i < len(s) and s[i] != '(':
                i += 1
            root = TreeNode(int(s[:i]))
            j = i
            if i < len(s):
                c = 1
                j = i + 1
                while j < len(s) and c != 0:
                    if s[j] == '(':
                        c += 1
                    elif s[j] == ')':
                        c -= 1
                    j += 1
                root.left = build(s[i+1:j-1])
            i = j
            if i < len(s):
                root.right = build(s[i+1:len(s)-1])
            return root

        return build(s)

第四题Word Abbreviation

题目大意：给定一个长度为n各不相同并且非空的字符串数组，要求根据以下规则缩写字符串：
1. 以第一个字符为前缀，然后紧接略去的字符串个数，以字符串最后一个字符结尾；
2. 如果存在不同的字符串却有一样的缩写，那么要以前两个字符为前缀，以此类推，直到所有字符串都有唯一的缩写；
3. 如果缩写并不能减少字符串的长度，那么就保持原来字符串。

样例输入：
["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
样例输出：
["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

我的解法：假设前缀长度为k（初始k为1），然后扫描没有被缩写的字符串，将其缩写后的结果保存在一个哈希表里。这个哈希表是以缩写之后的字符串为键值，其对应的是所有缩写到该键值的字符串的位置的列表。最后扫描这个哈希表，如果只有一个字符串缩写到对应键值，那么就找到了一个可行的缩写了。接着k的值增加1，重复上诉步骤直到所有字符串都有唯一缩写。

需要注意的一点是，在上述扫描的过程中，可能遇到一些不用被缩略的字符串。对于它们，就没有必要放进哈希表了。

from collections import defaultdict

class Solution(object):
    def wordsAbbreviation(self, dict):
        """
        :type dict: List[str]
        :rtype: List[str]
        """
        n = len(dict)
        ans = [''] * n
        visited = [False] * n
        k = 1
        while n > 0:
            tmp = defaultdict(list)
            for i, w in enumerate(dict):
                if visited[i]:
                    continue
                if k + 2 >= len(w):
                    ans[i] = w
                    n -= 1
                    visited[i] = True
                else:
                    tmp[w[:k]+str(len(w)-k-1)+w[-1]].append(i)
            for t, v in tmp.items():
                if len(v) == 1:
                    ans[v[0]] = t
                    visited[v[0]] = True
                    n -= 1
            k += 1
        return ans
leetcode contest