# Weekly Contest 391

日期： 2024/03/31

這是我第一次去做 LeetCode Weekly Contest，一題 Easy、兩題 Medimum、一題 Hard，除了 Hard 沒想出來之外，其它題目約在 5 分鐘內解出來。

此次題目（測驗當下題目不會顯示標題）：
- [3099. Harshad Number](https://leetcode.com/problems/harshad-number/description/)
- [3100. Water Bottles II](https://leetcode.com/problems/water-bottles-ii/description/)
- [3101. Count Alternating Subarrays](https://leetcode.com/problems/count-alternating-subarrays/description/)
- [3102. Minimize Manhattan Distances](https://leetcode.com/problems/minimize-manhattan-distances/description/)

第一題跟第二題只要按照題目敘述去做即可解決
#### 第一題

class Solution {
public:
    int sumOfTheDigitsOfHarshadNumber(int x) {
        int y = x;
        int s = 0;
        while(y) {
            s += y % 10;
            y /= 10;
        }
        if(x % s == 0)
            return s
        return -1;
    }
};

#### 第二題

class Solution {
public:
    int maxBottlesDrunk(int numBottles, int numExchange) {
        int ret = 0;
        int empty_bottles = 0;
        while(true) {
//             drink
            ret += numBottles;
            empty_bottles += numBottles;
            numBottles = 0;
            if(empty_bottles >= numExchange) {
//                 Exchange
                numBottles++;
                empty_bottles -= numExchange;
                numExchange++;
            }else{
                break;
            }
        }
        return ret;
    }
};

#### 第三題

class Solution {
public:
    long long countAlternatingSubarrays(vector<int>& nums) {
        using ll = long long;
        const int n = nums.size();
        if(n <= 1)
            return n == 1;
        
        ll ret = 0;
        
        int i = 0;
        int j = 1;
        
        while(i < n) {
            while(j < n && nums[j] != nums[j - 1]) {
                j++;
            }
            
            ll length = j - i;
            ret += ((length + 1) * length) / 2;
            
            i = j;
            j++;
        }
        
        
        return ret;
    }
};

從題目給予的範例來看：
- `[0, 1, 1, 1]` 符合的有 `[0], [1], [1], [1], [1]` 總共 5 個
- `[1, 0, 1, 0]` 有 10 組，任意子陣列都符合
- 取 1 個：`[1], [0], [1], [0]`
- 取 2 個：`[1, 0], [0, 1], [1, 0]`
- 取 3 個：`[1, 0, 1], [0, 1, 0]`
- 取 4 個：`[1, 0, 1, 0]`
- 4 + 3 + 2 + 1 得出計算總和公式：`(length + 1) * length / 2`

解題當下我多想了一組測試資料：`[1, 0, 1, 0, 0]`，總共 11 個。
比起上面的在最後多了個 `0`，答案只多了個 `[0]`，與 `[1, 0, 1, 0]` 是分開計算的子陣列。
因此陣列可以切割成數個子陣列，再利用子陣列長度計算答案的數量。

#### 第四題
這裡的程式碼是當下想到的，我自己從題目限制得到一些線索，演算法 $O(N^2)$ 可能可以接受。只是目前只能做出 TLE 版本的。

class Solution {
public:
    int minimumDistance(vector<vector<int>>& points) {
        const int n = points.size();
        vector<vector<int>> dd(n, vector<int>(n, 0));
        
        for(int i = 0 ; i < n; i++) {
            for(int j = 0; j < n ; j++) {
                int x1 = points[i][0];
                int y1 = points[i][1];
                
                int x2 = points[j][0];
                int y2 = points[j][1];
                int diff = abs(x1 - x2) + abs(y1 - y2);
                dd[i][j] = diff;
                dd[j][i] = diff;
            }
        }
        
        int ret = INT_MAX;
        
        for(int rp = 0; rp < n; rp++) {
//             rp --> removed points
            
            int local_max = 0;
            for(int i = 0; i < n; i++) {
                if(i == rp)
                    continue;
                for(int j = 0; j < n; j++) {
                    if(j == rp)
                        continue;
                    local_max = max(local_max, dd[i][j]);
                }
            }
            
            ret = min(ret, local_max);
        }
        
        return ret;
    }
};

這題考的是知識面，知道的就能做出來，參考 [Youtube 官神影片](https://www.youtube.com/live/cumosO16uB4)，影片看完就發現概念很簡單。

根據題目敘述，The Manhattan Distance between two cells $(x_i, y_i)$ and $(x_j, y_j)$ is $|x_i - x_j| + |y_i - y_j|$
可以將絕對值拆解成四個數字：
- $(x_i - x_j) + (y_i - y_j)$
- $(x_i - x_j) + (y_j - y_i)$
- $(x_j - x_i) + (y_i - y_j)$
- $(x_j - x_i) + (y_j - y_i)$

使用 C++ 的四個 `multiset` 去儲存這些數值，計算後即為 Manhattan Distance。另，題目要求移除一顆的答案，只要遍歷每個點，移除該數值後再取 Manhattan Distance 即題目要求，之後把將該點加回去，繼續下次計算。

class Solution
{
public:
    int minimumDistance(vector<vector<int>> &points)
    {
        if (points.size() <= 1)
            return 0;

        vector<multiset<int>> arr(4);
        for (vector<int> &p : points)
        {
            int t[4] = {p[0] + p[1], p[0] - p[1],
                        -p[0] + p[1], -p[0] - p[1]};
            for (int i = 0; i < 4; i++)
                arr[i].insert(t[i]);
        }

        int ret = INT_MAX >> 1;
        for (vector<int> &p : points)
        {
            int t[4] = {p[0] + p[1], p[0] - p[1],
                        -p[0] + p[1], -p[0] - p[1]};
//             移除該點數值
            for (int i = 0; i < 4; i++)
                arr[i].erase(arr[i].find(t[i]));
//             計算答案
            int local_max = 0;
            for (int i = 0; i < 4; i++) {
                int diff = *prev(arr[i].end()) - *arr[i].begin();
                local_max = max(local_max, diff);
            }

            ret = min(ret, local_max);
//             加回去
            for (int i = 0; i < 4; i++)
                arr[i].insert(t[i]);
        }
        return ret;
    }
};

看解答區還有更好的演算法，我自己是覺得這類型的題目這樣就好。