這次的題目多了一點點要思考的成份，第四題忘了歸零有點可惜。不過總算是可以拿 T-shirt 了，開心～

Leetcode 628. Maximum Product of Three Numbers

給你 $n$ 個數字 $(3\le n\le 1000)$，問從中挑選三個數字，最大的乘積為何？數字範圍 $[-1000, 1000]$。

把數字都排好序以後，不難發現答案只會跟最小 & 最大的三個數有關。 因此我們可以把四種情形逐一嘗試：

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int ans = nums[0] * nums[1] * nums[2];
        ans = max(ans, nums[0] * nums[1] * nums[n-1]);
        ans = max(ans, nums[0] * nums[n-2] * nums[n-1]);
        ans = max(ans, nums[n-3] * nums[n-2] * nums[n-1]);
        return ans;
    }
};
Leetcode 630. Course Schedule III

有 $n$ 堂課，每一堂課長度為 $t$，若收看的話必須在時間 $d$ 之前看完。請問至多可以看完幾堂課？$(1\le n, t, d\le 10000)$

首先，我們可以證明：假設 $C_1, C_2, \ldots, C_k$ 是一組可以被完成的課程，那麼依照他們的 deadline 時間排序依序進行課程必定是個合法的解。

（這題題解好難寫喔，尤其是證明。以後再說吧 :P ）

這題的一個解法是先把所有課程依照結束時間排序，接下來依序檢查：看看能不能加入當前的課程集合，如果可以，就直接把它加進去。如果不行，就比較看看這堂課花的時間比「目前課程集合當中花最久的課」哪一個比較短，留比較短的課程下來。

下面的寫法用的是 multiset，但用 priority_queue 比較恰當。

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        for(auto &&x: courses) {
            swap(x[0], x[1]);
        }
        sort(courses.begin(), courses.end());
        multiset<int> all;
        int ans=0, now=0;
        for(auto &&x: courses) {
            if(now + x[1] <= x[0]) {
                now += x[1];
                all.insert(x[1]);
                ans=max(ans, (int)all.size());
            } else if (!all.empty() && *all.rbegin() > x[1] ) {
                now -= *all.rbegin();
                all.erase(all.find(*all.rbegin()));
                all.insert(x[1]);
                now += x[1];
            }
        }
        return ans;
    }
};
Leetcode 629. K Inverse Pairs Array

給定 $n, k$ $(0\le n, k\le 1000)$，請問有多少個 $1$ 到 $n$ 的排列其逆序數對的數量恰好有 $k$ 個？

我們可以依序考慮插入的第 $i=1, 2, \ldots, n$ 個數字，每一個數字插入當前的排列都有可能造成逆序數對 $+0, +1, \ldots, +(i-1)$。因此我們可以把它寫成一個動態規劃的樣子：令 $\DP(i, j)$ 表示 $1$ 到 $i$ 的排列其逆敘述對數量恰好是 $j$ 的排列數。

我們可以列出他的遞迴式：

然後我們就會發現這個總和是一個連續和，因此若我們預處理 $S(i, j) = \DP(i, 0) + \DP(i, 1) + \cdots + \DP(i, j)$ 那麼前面便可以化簡成 $\DP(i, j) = S(i, j) - S(i, j-i)$。

int dp[1005][1005];
int S[1005][1005];

class Solution {
public:
    int kInversePairs(int n, int k) {
        const int MOD = 1e9+7;
        // initialize
        dp[0][0] = 1;
        for (int j = 0; j <= k; j++) S[0][j] = 1;
        // run dynamic programming
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= k; j++) {
                dp[i][j] = (S[i-1][j] - (j<i? 0: S[i-1][j-i])) % MOD;
                S[i][j] = ((j? S[i][j-1]: 0) + dp[i][j]) % MOD;
            }
        if (dp[n][k] < 0) dp[n][k] += MOD;
        return dp[n][k];
    }
};
Leetcode 631. Design Excel Sum Formula

在一個 $26\times 26$ 的 Excel 表格中，進行以下一些操作：

  • set(row, col, value): 將 (row, col) 這格的資料設定為 value
  • get(row, col): 取得 (row, col) 這格的數值
  • sum(row, col, ranges): 將 (row, col) 這格的值設為後面一連串 range 的總和 要注意的是 sum 操作是間接的，只要被 ranges 包含的任何一個格子資料有修改，這一格就會接著變動。 請寫一隻程式模擬這些操作。

硬做吧，每次 query 重算，關鍵是重疊的範圍至多算一次。 感覺上這題用 python 寫起來會方便很多很多。

class Excel {
public:
    int a[27][27];
    vector<string> refs[27][27];
    int mode[27][27];
    int dirt[27][27];
    int H, W;
    int dirt_cnt;
    Excel(int H, char W) {
        memset(a, 0, sizeof(a));
        memset(mode, 0, sizeof(mode));
        memset(dirt, 0, sizeof(dirt));
        this->H = H;
        this->W = (int)(W-'A')+1;
        this->dirt_cnt = 0;
    }
    
    void set(int r, char c, int v) {
        a[r][c-'A'+1] = v;
        mode[r][c-'A'+1] = 0;
        ++dirt_cnt;
    }
    
    int get(int r, char c) {
        ++dirt_cnt;
        return calc(r, c-'A'+1);
    }
    
    int sum(int r, char c, vector<string> strs) {
        ++dirt_cnt;
        refs[r][c-'A'+1] = strs;
        mode[r][c-'A'+1] = 1;
        return calc(r, c-'A'+1);
    }
    
    private:
    int calc(int x, int y) {
        
        if (dirt_cnt == dirt[x][y]) return a[x][y];
        dirt[x][y] = dirt_cnt;
        if (mode[x][y] == 0) return a[x][y];
        
        a[x][y] = 0;
        for(auto &&xt: refs[x][y]) {
            int p = xt.find(":");
            if (p != string::npos) {
                string u = "";
                for(int i=0;i<p;i++) u += xt[i];
                
                string v = xt.substr(p+1);
                int r1, c1, r2, c2;
                c1 = u[0]-'A'+1;
                r1 = atoi(u.substr(1).c_str());
                c2 = v[0]-'A'+1;
                r2 = atoi(v.substr(1).c_str());
                
                for(int i=r1;i<=r2;i++)
                    for(int j=c1;j<=c2;j++)
                        a[x][y] += calc(i, j);    
                //printf("x=%d, y=%d, cur=%d (%d,%d)->(%d,%d)\n", x, y, a[x][y], r1, c1, r2, c2);
            } else {
                string u = xt;
                int r1, c1;
                c1 = u[0]-'A'+1;
                r1 = atoi(u.substr(1).c_str());
                a[x][y] += calc(r1, c1);
            }
        }
        return a[x][y];
    }
};