比赛链接

第一题Shortest Unsorted Continuous Subarray

给定一个数组，求其中最短的连续子数组长度，使得对该子数组排序就能完成对整个数组的排序。

首先将数组排好序，然后看排好的数组与原来的数组之间的差异。

class Solution(object):
    def findUnsortedSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sn = sorted(nums)
        i = 0
        while i < len(nums) and nums[i] == sn[i]:
            i += 1
        if i == len(nums):
            return 0
        j = len(nums) - 1
        while j >= 0 and nums[j] == sn[j]:
            j -= 1
        return j-i+1

第二题Kill Process

每个进程都有自己的PID，以及代表父进程的PPID。每个进程最多只有一个父进程，但是可以有多个子进程。现在给定两个数组pid和ppid，其中pid表示当前的进程，而ppid则是对应的父进程。问如果结束进程kill的话会导致哪些进程结束。当一个进程被结束的同时，其所有子进程都会被结束。

图／树的遍历问题。DFS和BFS都行。首先建立一个父进程与子进程的一一对应，然后从kill出发，逐一访问它的子进程，并递归下去。我是用BFS实现的。

class Solution(object):
    def killProcess(self, pid, ppid, kill):
        """
        :type pid: List[int]
        :type ppid: List[int]
        :type kill: int
        :rtype: List[int]
        """
        mp = {}
        for c, p in zip(pid, ppid):
            if p not in mp:
                mp[p] = []
            mp[p].append(c)
        visited = {kill}
        ans = [kill]
        p = 0
        while p < len(ans):
            for c in mp.get(ans[p], []):
                if c not in visited:
                    visited.add(c)
                    ans.append(c)
            p += 1
        return ans

第三题Delete Operation for Two Strings

给定两个字符串，每次可以从任意一个中删除一个字符。问至少需要多少次删除能使得剩下的两个字符串一样。

求两个字符串最长公共子字符串的简单变种。本题答案是原来两个字符串长度之和减去最长公共子字符串的长度。下面我们看看怎么用动态规划寻找两个字符串的最长公共子字符串的长度。

假设给定的两个字符串为s和t，长度分别为n和m，用f(i, j)表示s[i:]与t[j:]的最长公共子字符串的长度。那么我们有如下转移方程：
如果s[i]==t[j]

f(i, j) = 1 + f(i+1, j+1)

否则
f(i, j) = max(f(i, j+1), f(i+1, j))

边界条件是：如果i >= n或者j >= m，f(i, j) = 0.

因为之前讨论过DP分别用递归和迭代实现的差异，所以今天就打算用不怎么熟悉的迭代来实现。然后赤裸裸的4次WA打脸了。有三次WA都是因为边界条件没有处理好！

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        if not word1 or not word2:
            return len(word1)+len(word2)
        n = len(word1)
        m = len(word2)
        dp = [[0]*m for _ in xrange(n)]
        if word1[n-1] == word2[m-1]:
            dp[n-1][m-1] = 1
        ml = dp[n-1][m-1]
        for i in xrange(m-2, -1, -1):
            if word1[n-1]==word2[i]:
                dp[n-1][i] = 1
            else:
                dp[n-1][i] = dp[n-1][i+1]
            ml = max(ml, dp[n-1][i])
        for i in xrange(n-2, -1, -1):
            if word1[i]==word2[m-1]:
                dp[i][m-1] = 1
            else:
                dp[i][m-1] = dp[i+1][m-1]
            ml = max(ml, dp[i][m-1])
        for j in xrange(m-2, -1, -1):
            for i in xrange(n-2, -1, -1):
                if word1[i]==word2[j]:
                    dp[i][j] = 1+dp[i+1][j+1]
                else:
                    dp[i][j] = max(dp[i][j+1], dp[i+1][j])
                ml = max(ml, dp[i][j])
        return n+m-2*ml

上面代码奇丑无比。完成比赛后认真想想，上述代码可以简化为：

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        n, m = len(word1), len(word2)
        dp = [[0]*(m+1) for _ in xrange(n+1)]
        ml = 0
        for j in xrange(m-1, -1, -1):
            for i in xrange(n-1, -1, -1):
                if word1[i]==word2[j]:
                    dp[i][j] = 1+dp[i+1][j+1]
                else:
                    dp[i][j] = max(dp[i][j+1], dp[i+1][j])
                ml = max(ml, dp[i][j])
        return n+m-2*ml

第四题Erect the Fence

求凸包。

经典算法了，就不解释了。这个算法我好早之前就练习过了，比赛的时候就直接拷贝过来改改就提交过了。不知道这样做算不算作弊呢 >_<

# Definition for a point.
# class Point(object):
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class ConvexHull(object):

    def __init__(self, points):
        self.pts = points
        self.hull = []

    def get(self):
        if len(self.hull) > 0:
            return self.hull

        pts, hull = self.pts, self.hull
        is_turn_right = self.is_turn_right
        pts.sort(key=lambda p: (p.x, p.y))

        def calc_hull(pts):
            ret = []
            for p in pts:
                if len(ret) < 2:
                    ret.append(p)
                    continue
                while len(ret) > 1 and not is_turn_right(ret, p):
                    ret.pop()
                ret.append(p)
            return ret

        # calculate upper hull
        upper = calc_hull(pts)

        # calculate lower hull
        lower = calc_hull(reversed(pts))

        hull = upper + lower[1:-1]

        return list(set(hull))

    def is_turn_right(self, pts, r):
        p, q = pts[-2], pts[-1]
        u = (q.x - p.x, q.y - p.y)
        v = (r.x - p.x, r.y - p.y)
        return u[0] * v[1] - u[1] * v[0] <= 0

class Solution(object):
    def outerTrees(self, points):
        """
        :type points: List[Point]
        :rtype: List[Point]
        """
        ch = ConvexHull(points)
        return ch.get()
leetcode contest