Leetcode Contest 38 | 叶某人的碎碎念

这次比赛我表现得比较差，只能做出第一题和第三题。第四题比赛结束之后很快也写出来了，而第二题确实花了我一个多小时才能想出来。

第一题Maximum Product of Three Numbers

给定一个长度不小于3的数组，问任选三个数得到的最大乘积是多少。

先将数组排序，那么最大值必然在下面四种情况中：

第一个数 X 第二个数 X 第三个数
倒数第一个数 X 倒数第二个数 X 倒数第三个数
第一个数 X 倒数第一个数 X 倒数第二个数
第一个数 X 第二个数 X 倒数第一个数

class Solution(object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        return max(nums[0]*nums[1]*nums[2],
                    nums[-1]*nums[-2]*nums[-3],
                    nums[0]*nums[-1]*nums[-2],
                    nums[0]*nums[1]*nums[-1])

第二题Course Schedule III

我们有编号从1到n的n个不同的课程。每个课程有时间长度t和截止日期d。这代表该课程必须连续上t天，而且必须在第d天之前（包括第d天）完成。我们从第1天开始算起。现在给定每个课程的(t, d)，问我们最多能上几门课程。假设我们每天只能上一门课。

首先分析一下在什么条件下我们能上[(t₁, d₁), ..., (t_m, d_m)]中的所有课。不妨假设

$$d_1 \le d_2 \le \cdots \le d_m.$$

那么我们要保证第k门课的完成时间不晚于第d_k天，所以对任意的k=1, 2, ..., m，我们都有

$$\sum_{i=1}^k t_i \le d_k.$$

根据以上的分析，我构造了如下的贪心算法。

首先要对所有课程按照d从小到大排序。假设知道课程1到课程m一共m门课时的最优解，对于新加入的第m＋1门课程，我按照以下规则处理：如果之前最优解的总时长加上第m＋1门课的时长还不晚于第m＋1门的截止时间，我们就直接将第m＋1门课加入最优解中。也就是说如果我们能继续上第m＋1门课程的话就直接上。如果不能直接上的话，我们找出之前最优解中最耗时间的课程，如果这门课程比第m＋1门课更耗时间，那么我们就将它换成第m＋1门课。虽然我们没有增加最优解的课程数目，但是替换课程可以使得最优解的总时长变短。

因为希望能快速找出特定变化集合的最大值，所以实现中我用到了堆。算法的时间复杂度为O(nlog n)。

from heapq import heappush, heappop

class Solution(object):
    def scheduleCourse(self, courses):
        """
        :type courses: List[List[int]]
        :rtype: int
        """
        courses.sort(key=lambda c: c[1])
        h = []
        s = courses[0][0]
        heappush(h, -s)
        for t, d in courses[1:]:
            if s+t<=d:
                heappush(h, -t)
                s += t
            elif h[0]+t<0:
                s += h[0]+t
                heappop(h)
                heappush(h, -t)
        return len(h)

第三题K Inverse Pairs Array

对于一个数组a，我们叫(i, j)为一个逆对，如果 i < j 但是 a[i] > a[j]。给定整数n和k，问有多少个由1到n构成并恰好有k个逆对的数组的个数。要求将答案mod 10⁹+7。

令f(i, j)表示由1到i构成并恰好有j个逆对的数组的个数。对于由1到i构成的数组，如果第1位的数为x，那么我们知道跟x构成逆对的数字有x－1个。而x的取值可能为1，2，...，i，所以我们有关于f(i, j)的如下公式。

如果$j=0$，$f(i, 0)=1$.
如果$1 \le j \le i-1$，

$$f(i, j) = f(i-1, j) + f(i-1, j-1) + \cdots + f(i-1, 0);$$

如果$i \le j \le k$，

$$f(i, j) = f(i-1, j) + f(i-1, j-1) + \cdots + f(i-1, j-i+1).$$

如果我们直接根据上面的递归公式实现，那么得到的算法时间复杂度是O(n³)（假设n和k很接近）。因为n最大可能是1000，所以是会超时的。我们需要更好的公式。

观察上面的公式，我们不难发现f(i, j)与f(i, j-1)的递归公式相差很少的。事实上，通过分析f(i, j)-f(i, j-1)，我们可以得到以下公式。

如果$j=0$，$f(i, 0)=1$.
如果$1 \le j \le i-1$，

$$f(i, j) = f(i, j-1) + f(i-1, j);$$

如果$i \le j \le k$，

$$f(i, j) = f(i, j-1) + f(i-1, j) - f(i-1, j-i).$$

这个更好的递归公式能给我们一个O(n²)的算法。不过这个递归公式有点瑕疵，因为给定i个数字，逆对的个数最多是i(i-1)/2。因此我们还要根据j和i(i-1)/2的大小关系做出细微的调整。

class Solution(object):
    def kInversePairs(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        M = 10**9+7
        f = [[0]*(k+1) for _ in xrange(n+1)]
        for i in xrange(1, n+1):
            f[i][0] = 1
            c = min(k, i*(i-1)/2)
            for j in xrange(1, min(i, c+1)):
                f[i][j] = (f[i][j-1]+f[i-1][j]) % M
            for j in xrange(i, c+1):
                f[i][j] = (f[i][j-1]+f[i-1][j]-f[i-1][j-i]) % M
        return f[n][k]

第四题Design Excel Sum Formula

这题比我想象中简单，只是题目比较长而已。这个问题的难度我觉得在set的设计上。每次设置一个值时，我们都要正确的更新整个表中的值。我用了带记忆的深度搜索实现更新的。

class Excel(object):

    def __init__(self, H,W):
        """
        :type H: int
        :type W: str
        """
        self.cell = {}
        self.sums = {}
        for i in xrange(1, H+1):
            for j in xrange(ord(W)-ord('A')):
                self.cell[i, j] = 0
                self.sums[i, j] = []


    def set(self, r, c, v):
        """
        :type r: int
        :type c: str
        :type v: int
        :rtype: void
        """
        self.cell[r, ord(c)-ord('A')] = v
        self.sums[r, ord(c)-ord('A')] = []

        seen = set()
        def dfs(r, c):
            if not self.sums[r, c] or (r, c) in seen:
                return self.cell[r, c]
            ans = 0
            for s in self.sums[r, c]:
                if ':' not in s:
                    ans += dfs(int(s[1:]), ord(s[0])-ord('A'))
                else:
                    s = s.split(':')
                    rb, cb = int(s[0][1:]), ord(s[0][0])-ord('A')
                    re, ce = int(s[1][1:]), ord(s[1][0])-ord('A')
                    for i in xrange(rb, re+1):
                        for j in xrange(cb, ce+1):
                            ans += dfs(i, j)
            seen.add((r, c))
            self.cell[r, c] = ans
            return ans

        for r, c in self.cell.keys():
            dfs(r, c)


    def get(self, r, c):
        """
        :type r: int
        :type c: str
        :rtype: int
        """
        return self.cell[r, ord(c)-ord('A')]


    def sum(self, r, c, strs):
        """
        :type r: int
        :type c: str
        :type strs: List[str]
        :rtype: int
        """
        c = ord(c) - ord('A')
        self.sums[r, c] = strs
        ans = 0
        for s in strs:
            if ':' not in s:
                ans += self.cell[int(s[1:]), ord(s[0])-ord('A')]
            else:
                s = s.split(':')
                rb, cb = int(s[0][1:]), ord(s[0][0])-ord('A')
                re, ce = int(s[1][1:]), ord(s[1][0])-ord('A')
                for i in xrange(rb, re+1):
                    for j in xrange(cb, ce+1):
                        ans += self.cell[i, j]
        self.cell[r, c] = ans
        return ans


# Your Excel object will be instantiated and called as such:
# obj = Excel(H, W)
# obj.set(r,c,v)
# param_2 = obj.get(r,c)
# param_3 = obj.sum(r,c,strs)

leetcode contest