HackMD
Weekly Contest 391
日期： 2024/03/31
這是我第一次去做 LeetCode Weekly Contest，一題 Easy、兩題 Medimum、一題 Hard，除了 Hard 沒想出來之外，其它題目約在 5 分鐘內解出來。
此次題目（測驗當下題目不會顯示標題）：
- 3099. Harshad Number
- 3100. Water Bottles II
- 3101. Count Alternating Subarrays
- 3102. Minimize Manhattan Distances
第一題跟第二題只要按照題目敘述去做即可解決
第一題
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 個：
解題當下我多想了一組測試資料：[1, 0, 1, 0, 0]，總共 11 個。
比起上面的在最後多了個 0，答案只多了個 [0]，與 [1, 0, 1, 0] 是分開計算的子陣列。
因此陣列可以切割成數個子陣列，再利用子陣列長度計算答案的數量。
第四題
這裡的程式碼是當下想到的，我自己從題目限制得到一些線索，演算法
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 官神影片，影片看完就發現概念很簡單。
根據題目敘述，The Manhattan Distance between two cells
可以將絕對值拆解成四個數字：
使用 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;
}
};
看解答區還有更好的演算法，我自己是覺得這類型的題目這樣就好。
