Weekly Contest 392

日期：2024/04/07

這是第二次做 LeetCode weekly contest，很可惜卡在第三題沒完全做完。

此次題目：

• Longest Strictly Increasing or Strictly Decreasing Subarray
• Lexicographically Smallest String After Operations With Constraint
• Minimum Operations to Make Median of Array Equal to K
• Minimum Cost Walk in Weighted Graph

第一題

使用兩個變數 cur_inc 與 cur_dec 計算最長遞增與遞減子陣列即可

class Solution {
public:
    int longestMonotonicSubarray(vector<int>& nums) {
        const int n = nums.size();
        int ret = 1;
        int cur_inc = 1;
        int cur_dec = 1;
        for(int i = 1; i < n; i++) {
            if(nums[i] > nums[i - 1]) {
                cur_inc++;
                cur_dec = 1;
            }else if(nums[i] < nums[i - 1]) {
                cur_dec++;
                cur_inc = 1;
            }else {
                cur_dec = 1;
                cur_inc = 1;
            }
            
            ret = max(ret, cur_inc);
            ret = max(ret, cur_dec);
        }
        
        
        return ret;
    }
};

第二題

題目可以轉化成：

1. 實作出距離的計算方式
2. 因為是 Lexicographically Smaller，可以從起始的字母開始處理，最小值是 'a'

class Solution {
public:
    int calDis(char a, char b) {
        int x = a - 'a';
        int y = b - 'a';      
        int r1 = ((x - y) + 26) % 26;
        int r2 = (26 - r1) % 26;
        return min(r1, r2);
    }
    string getSmallestString(string s, int k) {
        const int n = s.size();
        for(int i = 0; i < n; i++) {
            if(k <= 0)
                break;
            
            int d = calDis(s[i], 'a');
            if(d <= k) {
                s[i] = 'a';
                k -= d;
            }else{
                if('a' + k < s[i])
                    s[i] = s[i] - k;
                else
                    s[i] = 'a' + k;
                k = 0;
            }
        }
        return s;
    }
};

第三題

題目本身沒有解釋清楚中位數是哪個位置的數字，是 nums[n / 2] 的數字必須等於k

第一版本的程式碼有點寫錯，還包含幾個 edge cases 沒想到，例如
nums = [1], k = 1000000000 跟 nums = [1000000000], k = 1
它的思路是將大於、小於與等於 k 的分組，使用 check 函式確認中位數是否位於中間。

class Solution {
public:
    long long minOperationsToMakeMedianK(vector<int>& nums, int k) {
//         less than k
        priority_queue<int> ll;
//         greater than k
        priority_queue<int, vector<int>, greater<int>> gg;
//         equal to k
        int ee = 0;
        
        for(int x : nums) {
            if(x > k)
                gg.push(x);
            else if(x < k)
                ll.push(x);
            else
                ee++;
        }
        
        auto check = [&gg, &ll, &ee, &nums] {
            const int mi = nums.size() / 2 + 1;
            bool c1 = ll.size() + 1 == mi;
            bool c2 = ee != 0 && ll.size() < mi && ll.size() + ee >= mi;
            return c1 || c2;
        };
        
        long long ret = 0;
        const int mi = nums.size() / 2 + 1;
        while(!check()) {
            int x;
            if(ll.size() >= mi) {
                x = ll.top();
                ll.pop();
            }else{
                x = gg.top();
                gg.pop();
            }

            int diff = abs(k - x);
            ret += diff;
            ee++;
        }
        return ret;
    }
};

從討論區取得的解答，與上面的程式碼思路一模一樣，當下沒想出來：

class Solution {
public:
    long long minOperationsToMakeMedianK(vector<int>& nums, int k) {
        using ll = long long;
        ll ret = 0;
        const int n = nums.size();
        sort(nums.begin(), nums.end());
        for(int i = 0; i <= n / 2; i++) 
            ret += max(0, nums[i] - k);
        for(int i = n / 2; i < n; i++)
            ret += max(0, k - nums[i]);
        return ret;
    }
};