LeetCode周賽297，一小時AK你也可以

大家好，日拱一卒，我是樑唐。

今天是週一，我們照慣例來看看昨天的LeetCode周賽。這次周賽是地平線贊助的，如果沒記錯，這已經不是這個公司第一次贊助了。前5名可以獲得直接進入面試的機會，前200名可以獲得內推。

這次比賽的題目總體難度不算很大，沒有涉及一些比較複雜或冷門的演算法，相對來說比較基礎，以思維題為主，適合新人練手。

好了，廢話不多說，讓我們來看題吧。

計算應繳稅款總額

給你一個下標從 0 開始的二維整數陣列 brackets ，其中 brackets[i] = [upperi, percenti] ，表示第 i 個稅級的上限是 upperi ，徵收的稅率為 percenti 。稅級按上限 從低到高排序（在滿足 0 < i < brackets.length 的前提下，upperi-1 < upperi）。

稅款計算方式如下：

• 不超過 upper0 的收入按稅率 percent0 繳納
• 接著 upper1 - upper0 的部分按稅率 percent1 繳納
• 然後 upper2 - upper1 的部分按稅率 percent2 繳納
• 以此類推

給你一個整數 income 表示你的總收入。返回你需要繳納的稅款總額。與標準答案誤差不超 10-5 的結果將被視作正確答案。

題解

資料範圍很小，最多隻有100個區間，並且最大收入不會超過1000，基本上屬於理解了題意之後，隨便操作的問題。

雖然題目說了有精度要求，但實際上由於我們計算稅率的時候，最多隻有兩位小數，所以也不用擔心精度的問題。

```cpp class Solution { public: double calculateTax(vector>& bk, int income) { double ret = 0;

    int n = bk.size();

    int last = 0;
    for (int i = 0; i < n; i++) {
        if (income == 0) break;
        int level = min(income, bk[i][0] - last);
        ret += level * bk[i][1] / 100.0;
        income -= level;
        last = bk[i][0];
    }
    return ret;
}

}; ```

網格中的最小路徑代價

給你一個下標從 0 開始的整數矩陣 grid ，矩陣大小為 m x n ，由從 0 到 m * n - 1 的不同整陣列成。你可以在此矩陣中，從一個單元格移動到 下一行 的任何其他單元格。如果你位於單元格 (x, y) ，且滿足 x < m - 1 ，你可以移動到 (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1) 中的任何一個單元格。注意： 在最後一行中的單元格不能觸發移動。

每次可能的移動都需要付出對應的代價，代價用一個下標從 0 開始的二維陣列 moveCost 表示，該陣列大小為 (m * n) x n ，其中 moveCost[i][j] 是從值為 i 的單元格移動到下一行第 j 列單元格的代價。從 grid 最後一行的單元格移動的代價可以忽略。

grid 一條路徑的代價是：所有路徑經過的單元格的 值之和 加上 所有移動的 代價之和 。從 第一行 任意單元格出發，返回到達 最後一行 任意單元格的最小路徑代價。

題解

由於相鄰兩層的點都能隨意連通，簡單計算一下就會發現可能存在的路徑數量非常龐大，所以直接列舉所有路徑是肯定行不通的。

一般情況下這種時候有兩種思路，一種是將問題抽象成圖論，使用圖論的一些演算法例如最短路、網路流來解決。另外一種就是動態規劃，不去細究路徑中的細節，僅僅關注狀態和狀態之間的轉移關係。

對於這題來說，dijkstra最短路和動態規劃應該都是可行的。不過從程式碼複雜度上來看，顯然動態規劃更加方便一些。

我們用dp[i][j]儲存從第0行至座標(i, j)的最短路徑和，從(i, j)出發，我們可以到達所有的(i+1, k)點。對應的狀態為dp[i+1][k]，這個策略對應的狀態是dp[i][j] + moveCost[grid[i][j]][k] + grid[i+1][k]。我們對於所有的策略，維護最小的狀態即可。

程式碼如下：

```cpp class Solution { public: int minPathCost(vector>& grid, vector>& moveCost) { int n = grid.size(); int m = grid[0].size();

    vector<vector<int>> dp(n+1, vector<int>(m, 0x3f3f3f3f));

    for (int i = 0; i < m; i++) dp[0][i] = grid[0][i];

    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < m; k++) {
                dp[i+1][k] = min(dp[i+1][k], dp[i][j] + moveCost[grid[i][j]][k] + grid[i+1][k]);
            }
        }
    }

    int ret = 0x3f3f3f3f;

    for (int i = 0; i < m; i++) ret = min(ret, dp[n-1][i]);
    return ret;
}

}; ```

公平分發餅乾

給你一個整數陣列 cookies ，其中 cookies[i] 表示在第 i 個零食包中的餅乾數量。另給你一個整數 k 表示等待分發零食包的孩子數量，所有 零食包都需要分發。在同一個零食包中的所有餅乾都必須分發給同一個孩子，不能分開。

分發的 不公平程度 定義為單個孩子在分發過程中能夠獲得餅乾的最大總數。

返回所有分發的最小不公平程度。

題解

本題的資料範圍非常小，最多隻有8個孩子和8份餅乾。那麼我們可以直接列舉所有的分配情況，找到其中不公平程度最小的即可。

雖然思路很簡單，但是要實現還是有一點麻煩，需要用到搜尋的回溯法。我們使用一個數組sums用來儲存每個孩子拿到的餅乾總和。當所有餅乾分配完成之後，sums當中的最大值就是不公平程度。

程式碼如下：

```cpp class Solution { public:

int distributeCookies(vector<int>& cks, int k) {
    int ret = 0x3f3f3f3f;
    int n = cks.size();
    vector<int> sums(n, 0);
    function<void(int)> func;
    func = [&](int c) {
        if (c == n) {
            int maxi = sums[0];
            for (int i = 1; i < n; i++) maxi = max(sums[i], maxi);
            ret = min(ret, maxi);
            return ;
        }
        for (int i = 0; i < k; i++) {
            sums[i] += cks[c];
            func(c+1);
            // 回溯
            sums[i] -= cks[c];
        }
    };
    func(0);
    return ret;
}

}; ```

公司命名

給你一個字串陣列 ideas 表示在公司命名過程中使用的名字列表。公司命名流程如下：

1. 從 ideas 中選擇 2 個 不同 名字，稱為 ideaA 和 ideaB 。
2. 交換 ideaA 和 ideaB 的首字母。
3. 如果得到的兩個新名字 都 不在 ideas 中，那麼 ideaA ideaB（串聯 ideaA 和 ideaB ，中間用一個空格分隔）是一個有效的公司名字。
4. 否則，不是一個有效的名字。

返回 不同 且有效的公司名字的數目。

題解

首先觀察資料範圍，顯然1e4的量級下，我們直接列舉兩兩字串是不行的，一定會超時。如果不列舉所有的字串pair，應該怎麼辦呢？

我們稍作分析可以發現，對於某個idea來說，如果它和另外一個idea構成衝突，本質上是它和對應的首字母衝突。比如說coffee和toffee，對於coffee來說，所有t開頭的idea都不能構成答案。

進一步可以想到，我們可以找到所有和coffee衝突的首字母，排除掉這些字母對應的所有idea。然而這又帶來了新的問題，因為和coffee衝突的除了t開頭的idea以外，還有那些和字母c開頭衝突的idea，這部分也要排除掉。

所以我們也需要維護所有和c字母衝突的idea，但是進一步分析又會發現，和c衝突的idea以及和coffee衝突的idea這兩個集合之間是可能有交集的。我們需要保證這些交集的idea只會被去除一次……

顯而易見，這樣一來問題會變得非常複雜，我們要考慮若干集合的交併情況。對於這個問題又該如何解決呢？

我們可以列舉首字母，比如首字母c和首字母t。確定了首字母之後，首先這兩個首字母對應的idea都確定了，並且衝突關係也都確定了。我們可以很容易確定c字母開頭的idea有多少和字母t衝突，反之，我們也可以知道首字母t的idea當中又有多少和c字母衝突。

兩邊的數量減去衝突的數量一乘，就是這兩個首字母組合對答案的貢獻。由於英文當中只有26個字母，兩兩字母的組合非常有限，我們完全可以進行列舉。

```python class Solution: def distinctNames(self, ideas: List[str]) -> int: n = len(ideas) chars = 'abcdefghijklmnopqrstuvwxyz' ret = 0

    ideas = set(ideas)

    from collections import defaultdict

    # 首字母之間的衝突關係，如字母c和t衝突，記作forbid[c][t]++
    forbid = {c : defaultdict(int) for c in chars}
    # 首字母對應的idea數量
    cnts = defaultdict(int)

    for wd in ideas:
        c = wd[0]
        cnts[c] += 1
        for nc in chars:
            if c == nc:
                continue
            nword = nc + wd[1:]
            # 如果更換首字母之後依然在idea中能找到，說明存在衝突
            if nword in ideas:
                forbid[c][nc] += 1

    for c in chars:
        for nc in chars:
            if c == nc:
                continue
            lef = cnts[c]
            rig = cnts[nc]
            if lef == 0 or rig == 0:
                continue
            # 去掉衝突的數量
            lef -= forbid[c][nc]
            rig -= forbid[nc][c]
            ret += lef * rig

    return ret

```

這個程式碼和演算法本身都不難，但是要把題目中的含義以及思路理清楚並不容易，這才是最鍛鍊人的。

我個人也比較喜歡這樣的問題，它對於演算法的考察不是硬性的。不是你不知道某個演算法就一定解不出來的題目，而是本身就沒有特定的解決方案，就是需要依靠你的思考和分析從問題當中自己找到答案。

尤其是靈光乍現，找到解法的那一刻，真的是成就感爆棚，非常暢快。

希望各位都能體會到演算法和思考的魅力，找到自己的暢快時刻。