# Weekly Contest 398
日期 2024/05/19

我很難靜下心來寫，等靜下心來後發現題目本身並不困難。這次只有做到第二題。
- [Special Array I](https://leetcode.com/problems/special-array-i/)
- [Special Array II](https://leetcode.com/problems/special-array-ii/)
- [Sum of Digit Differences of All Pairs](https://leetcode.com/problems/sum-of-digit-differences-of-all-pairs/)
- [Find Number of Ways to Reach the K-th Stair](https://leetcode.com/problems/find-number-of-ways-to-reach-the-k-th-stair/)

### 第一題

class Solution {
public:
    bool isArraySpecial(vector<int>& nums) {
        const int n = nums.size();
        if(n == 1)
            return true;
        for(int i = 1; i < n; i++) {
            bool x = !!(nums[i] & 1);
            bool y = !!(nums[i - 1] & 1);
            bool z = x ^ y;
            if(!z)
                return false;
        }
        return true;
    }
};

### 第二題

class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
        const int m = nums.size();
        const int n = queries.size();
        vector<int> dp;
        for(int i = 1; i < m; i++) {
            bool x = !!(nums[i] & 1);
            bool y = !!(nums[i - 1] & 1);
            bool z = x ^ y;
            if(!z) {
                dp.push_back(i - 1);
            }
        }
        
        vector<bool> ret(n);
        for(int i = 0; i < n; i++) {
            if(queries[i][0] == queries[i][1]) {
                ret[i] = true;
                continue;
            }
            auto it = lower_bound(dp.begin(), dp.end(), queries[i][0]);
            if(it != dp.end()) {
                if(*it == queries[i][0]) {
                    ret[i] = false;
                    continue;
                }
                
                if(*it < queries[i][1]) {
                    ret[i] = false;
                    continue;
                }
            }
            ret[i] = true;
        }
        return ret;
    }

與第一題相比多了 `queries`，如果依照第一題的方式跑會超時。因此在第 6 行，先將不符合的位址存入 `dp` 陣列中。
再透過 `lower_bound` 直接尋找位址，檢查 `queries` 是否有在此範圍中。
因此時間複雜度從 $O(MN)$ 降為 $O(NlogM)$，$M$ 為元素個數，$N$ 為 `queries` 元素個數

### 第三題

class Solution {
public:
    long long sumDigitDifferences(vector<int>& nums) {
        using aa = array<int, 2>;
        using ll = long long;
        queue<aa> qq;
        for(int x: nums)
            qq.push({x / 10, x % 10});

        ll ret = 0;
        while(!qq.empty()) {
            const int n = qq.size();
            vector<int> digits(10, 0);
            for(int i = 0; i < n; i++) {
                int num = qq.front()[0];
                int d = qq.front()[1];
                qq.pop();
                digits[d]++;
                if(num > 0)
                    qq.push({num / 10, num % 10});
            }

            for(int i = 0; i < 10; i++)
                for(int j = i + 1; j < 10; j++)
                    ret += digits[i] * digits[j];
        }
        return ret;
    }
};

我剛開始寫的解答是超時的版本，就是很單純按照題目寫。
討論區的解答是沒有按照題目敘述的方式：計算該位數的頻率，之後相乘。
這題只要有想到用頻率解，很快就能解出來了。

<!--
$$S = QK^T \in R^{n \times n}$$

$$P = softmax(S) \in R^{n \times n}$$

$$
O = PV \in R^{n \times d}
$$
-->