這場題目滿難的，基本上是屬於比較麻煩的那種，而且各種 parse 字串，寫起來唉桑。

Leetcode 637. Average of Levels in Binary Tree

給你一棵二元樹，每一個節點上面有一個 32-bit 有號整數。我們定義一個節點的深度為從該節點走到樹根唯一最短路徑所需經過的邊數。請回傳對於每一個深度，所有該深度節點數值的平均值。

實作上可以用一個 int 和一個 double 記錄數量跟總和，然後對二元樹遍歷一次。最後對每個深度輸出總和除以平均的值就好。比較乾淨的寫法是直接開 $深度 \mapsto (數量, 總和)$ 的一個 map。

class Solution {
public:
    map<int, pair<int, double>> data;
    void dfs(TreeNode *root, int depth = 0) {
        if(!root) return;
        data[depth].first ++;
        data[depth].second += root->val;
        dfs(root->left, depth+1);
        dfs(root->right, depth+1);
    }
    vector<double> averageOfLevels(TreeNode* root) {
        dfs(root);
        vector<double> ret;
        for (auto &&x : data) ret.push_back(x.second.second / x.second.first);
        return ret;
    }
};
Leetcode 640. Solve the Equation

給你一個有整係數、一個等號、一個未知數 $x$ 的線性方程式，請你輸出 x=[答案] 或 Infinite solutions 或 No solution。這個方程式輸入的時候不含空白。

這題自己 parse 是一件很崩潰痛苦的事情（就跟我在比賽當下做的事情一樣。） 但如果我們用 python 的 eval 功能，其實可以做一些有趣的事情：比方說，我們先令 $x=0$，找出常數，再令 $x=1$，減去常數就可以知道答案了～是不是很方便呢！ 實作上需要把 $x$ 前面加個乘號，所以我們需要字串取代一下。

class Solution:
    def solveEquation(self, equation):
        """
        :type equation: str
        :rtype: str
        """
        eqs = equation.split("=")
        eqs = list(map(lambda s: re.sub(r'(?<=[0-9])x', '*x', s), eqs))
        def f(eq, x):
            return eval(eq)
        f0 = f(eqs[0], 0) - f(eqs[1], 0)
        f1 = f(eqs[0], 1) - f(eqs[1], 1) - f0
        if f1 == 0 and f0 == 0:
            return "Infinite solutions"
        elif f1 == 0:
            return "No solution"
        else:
            return "x={}".format(int(-f0/f1))

據說有人可以直接代 $x=j$（$=\sqrt{-1}$），利用 python 內建的 complex numbers 運算。

eqs = equation.replace("x", "j").split("=")
z = eval(eqs[0], {'j': 1j}) - eval(eqs[1], {'j': 1j})

這麼一來，z.real 和 z.imag 分別代表常數和一次項係數。

Leetcode 638. Shopping Offers

有 $n$ 樣物品，每一樣物品有個價錢 $price_j$。現在有 $m$ 種特惠組合，第 $i$ 種組合內包含 $a_{ij}$ 個物品 $j$，然後會告訴你整組價錢多少。你想要購買一些物品，第 $j$ 種恰好需要 $need_j$ 個。請問在恰好買到所需的物品的條件下，最便宜的價格是多少呢？至多只有 $n\le 6$ 種物品，每一種物品的需求至多 $need_j\le 6$ 個。

一臉 DP 樣的題目，狀態是湊出 $(a_1, a_2, \ldots, a_n)$ 至少要多少錢。 由於每一種物品可以選取 $0$ 到 $6$ 共七種可能性，因此狀態總數不超過 $7^6=117649$。 我們可以利用七進位制的整數來表示一個狀態。 轉移的部份就是對於每一組特惠組合，試試看能否更新到另一個狀態這樣。 所以複雜度高達 $7^6\times (100+6)\approx 10^7$，時限有點緊啊。

跟修拉拉討論過之後，發現找零錢問題有兩種更新狀態轉移的 DP 方法：第一種是先枚舉當前的狀態 $(a_1, \ldots, a_n)$，然後利用每一種特惠組合去更新他。第二種則是率先枚舉所有特惠組合，然後用一個迴圈跑過去更新他，第二種方法理論上 存取的狀態 locality 相當高，因此實作上 DP 效率會高一些。

class Solution {
public:
    int dp[117650];
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        dp[0] = 0;
        int h = 0, cnt[7] = {}, n = price.size(), sevens[7] = {1, 7, 49, 343, 2401, 16807, 117649};
        while (cnt[n] == 0) {
            // buy using the regular prices
            dp[h] = 0;
            for (int i = 0; i < n; i++) dp[h] += price[i] * cnt[i];
            
            // update counters and hash values;
            cnt[0]++; h++;
            for(int j=0; j < n && cnt[j] > needs[j]; j++) {
                cnt[j] = 0; h -= sevens[j] * (needs[j]+1);
                cnt[j+1]++; h += sevens[j+1];
            }
        }
        for (auto offers: special) {
            // we can omit this offer if any item exceeds our needs
            int bad = 0;
            for (int i = 0; i < n; i++) if (needs[i] < offers[i]) bad = 1;
            if (bad) continue;
                
            // compute the has value of this state
            int hash = 0;
            for (int i = 0; i < n; i++) hash += sevens[i] * offers[i];
            
            // enumerate all possible states
            h = 0;
            memset(cnt, 0, sizeof(cnt));
            while (cnt[n] == 0) {
                // perform dp update
                dp[h+hash] = min(dp[h+hash], dp[h] + offers.back());
                
                // update counters and hash values;
                cnt[0]++; h++;
                for(int j=0; j < n && cnt[j] > needs[j] - offers[j]; j++) {
                    cnt[j] = 0; h -= sevens[j] * (needs[j] - offers[j] + 1);
                    cnt[j+1]++; h += sevens[j+1];
                }
            }
        }
        // compute needs dp
        int hash = 0;
        for (int i = 0; i < n; i++) hash += sevens[i] * needs[i];
        return dp[hash];
    }
};
Leetcode 639. Decode Ways II

一種將全大寫英文字串編碼的方法，是將每一個字元直接換成他的字母順序然後再全部接起來，比方說 A 換成 1，Z 換成 26 之類的。現在給你一個編碼過的字串，有些位置是 * 代表它可能是 1 到 9 這 9 種數字之中的任一個，請問他可以是幾種不同的字串編碼而來的？輸出答案除以 $10^9+7$ 的餘數。

題目寫得不是很清楚的一題。但基本上就是動態規劃，$\DP(i)$ 表示前 $i$ 個字元可能對應的字串數量。觀察最後一個英文字母，它只能變成一位數或兩位數，因此大致上我們可以把它寫成 $\DP(i) = \DP(i-1) \times ways(s_i) + \DP(i-2) \times ways(s_{i-1}s_i)$，其中 $ways(x)$ 這個函數表示有幾種方法可以把一個英文字母對應成字串 $x$。

比方說 $ways(\mathtt{*})= 9$、$ways(\mathtt{**}) = 16$、$ways(\mathtt{0*})=0$ 之類的。總之有很多種 case 要注意，被表了很多次啊啊啊啊啊啊啊啊。

class Solution {
public:
    const int MOD = 1e9+7;
    long long dp[100005];
    void add(long long &x, long long v) { x+=v; if (x>=MOD) x-=MOD; }
    int numDecodings(string s) {
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for(int i = 0; i < (int) s.size(); i++) {
            dp[i+1] = 0;
            dp[i+1] = dp[i] * (s[i]=='*'? 9LL: (s[i]=='0'? 0:  1LL)) % MOD;
            if(i>0) {
                int ways = 0;
                if(s[i-1]=='*' && s[i]=='*') ways = 15;
                else if(s[i-1]=='*') ways = (s[i]=='0'? 2: (s[i]<='6'? 2: 1));
                else if(s[i-1]=='1' && s[i]=='*') ways = 9;
                else if(s[i-1]=='2' && s[i]=='*') ways = 6;
                else if(s[i-1]!='*' && s[i]!='*') {
                    
                    int v = s[i-1]-'0';
                    v=v*10+(s[i]-'0');
                    ways = (v>=10 && v<=26);
                }
                add(dp[i+1], ways * 1LL * dp[i-1] % MOD);
            }
        }
        return dp[(int)s.size()];
    }
};