就着Gin的酒劲，我还能一次不WA的过了这次比赛哈哈。

第一题Longest Harmonious Subsequence

给定一个数组，找出长度最长的子数组，使得其最大值与最小值恰好相差1，返回最大长度。

既然最大值与最小值恰好相差1，那么此子数组必定恰好有两个不一样的元素。我们只要统计每个元素出现的次数，然后枚举找出相邻两个元素出现次数之和的最大值就好。

class Solution(object):
    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cnt = {}
        for n in nums:
            cnt[n] = cnt.get(n, 0) + 1
        ans = 0
        for k, v in cnt.items():
            if k-1 in cnt:
                ans = max(ans, v+cnt[k-1])
            if k+1 in cnt:
                ans = max(ans, v+cnt[k+1])
        return ans

第二题Valid Square

给定二维平面四个点，问它们是否构成一个正方形。

如果给定一个正方形，那么正方形任意两个顶点之间的距离构成一个只有两个元素的集合：边长与对角线长度。这个结论反过来一般来说是不正确的，但是现在顶点的坐标都是整数，在这种特殊的情况下，我们有：

如果任意两个顶点之间的距离构成一个两个元素的集合，那么该四边形是正方形。

class Solution(object):
    def validSquare(self, p1, p2, p3, p4):
        """
        :type p1: List[int]
        :type p2: List[int]
        :type p3: List[int]
        :type p4: List[int]
        :rtype: bool
        """
        def dist(p, q):
            a = p[0]-q[0]
            b = p[1]-q[1]
            return a*a+b*b
        ls = {dist(p1, p2), dist(p1, p3), dist(p1, p4),
            dist(p2, p3), dist(p2, p4), dist(p3, p4)}
        return len(ls) == 2 and 0 not in ls

第三题Fraction Addition and Subtraction

计算分数加减法。分子分母保证在1到10之间。分数个数保证在10个以内。

因为数据量极小，所以可以直接通分算。关键记得最后要约分。因为输入的分母都小于10，所以约分的时候只需约2，3，5，7的因子。

class Solution(object):
    def fractionAddition(self, expression):
        """
        :type expression: str
        :rtype: str
        """
        import re
        if expression[0] == '-':
            expression = '0/1'+expression
        fs = re.split('(\+|-)', expression)
        ns = [int(fs[i].split('/')[0]) for i in xrange(0, len(fs), 2)]
        ds = [int(fs[i].split('/')[1]) for i in xrange(0, len(fs), 2)]
        cd = 1
        for d in ds:
            cd *= d
        cn = ns[0] * cd / ds[0]
        for i in xrange(len(ns)-1):
            if fs[2*i+1]=='+':
                cn += ns[i+1] * cd / ds[i+1]
            else:
                cn -= ns[i+1] * cd / ds[i+1]
        if cn == 0:
            return "0/1"
        for d in (2, 3, 5, 7):
            while cn % d == 0 and cd % d == 0:
                cn /= d
                cd /= d
        return "{}/{}".format(cn, cd)

第四题Design In-Memory File System

设计一个文件系统，支持ls，mkdir，addContentToFile和readContentFromFile。详细描述到leetcode上看。

不难，就是有点麻烦。

class file(object):
    def __init__(self, name="", is_dir=True):
        self.name = name
        self.is_dir = is_dir
        self.content = ""
        self.subf = {}

    def addContent(self, content):
        self.content += content

class FileSystem(object):

    def __init__(self):
        self.root = file("/")

    def go_to(self, path):
        if path=="/":
            return self.root
        path = path.split("/")[1:]
        ans = self.root
        for name in path:
            if name not in ans.subf:
                ans.subf[name] = file(name)
            ans = ans.subf[name]
        return ans

    def ls(self, path):
        """
        :type path: str
        :rtype: List[str]
        """
        cur = self.go_to(path)
        if cur.is_dir:
            ans = sorted([x for x in cur.subf])
        else:
            ans = [cur.name]
        return ans


    def mkdir(self, path):
        """
        :type path: str
        :rtype: void
        """
        self.go_to(path)


    def addContentToFile(self, filePath, content):
        """
        :type filePath: str
        :type content: str
        :rtype: void
        """
        cur = self.go_to(filePath)
        cur.is_dir = False
        cur.addContent(content)


    def readContentFromFile(self, filePath):
        """
        :type filePath: str
        :rtype: str
        """
        cur = self.go_to(filePath)
        return cur.content

# Your FileSystem object will be instantiated and called as such:
# obj = FileSystem()
# param_1 = obj.ls(path)
# obj.mkdir(path)
# obj.addContentToFile(filePath,content)
# param_4 = obj.readContentFromFile(filePath)
leetcode contest