LeetCode Weekly Contest 230 Editorial | Blog | SH Liu | rarakasm

LeetCode Weekly Contest 230 Editorial

競賽頁面網址

Q1: Count Items Matching a Rule

先判斷要找的rule的index是多少,再遍歷一次即可。

Time Complexity: O(N)O(N)

Space Complexity: O(1)O(1)

class Solution {
public:
    int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
        int t = 0;
        int ans = 0;
        if(ruleKey == "color") t = 1;
        else if(ruleKey == "name") t = 2;
        for(auto& a : items){
            if(a[t] == ruleValue) ans++;
        }
        return ans;
    }
};

Q2: Closest Dessert Cost

base 跟 toppings 的數量都很小 (N,M10N, M\leq 10),且每種 topping 的數量只有 [0,1,2][0,1,2] 三種可能,可以用暴力 DFS 把所有 base 跟 toppings 組合算出來。

Time Complexity: O(3MN)O(3^MN)

Space Complexity: O(M)O(M),遞迴時的 call stack 最多不超過 toppings 數量

class Solution {
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        int ans = INT_MAX;
        for(auto b : baseCosts){
            dfs(toppingCosts, 0, target, b, ans);
        }
        return ans;
    }
    
    void dfs(vector<int>& toppingCosts, int idx, int target, int curr, int& ans){
        if(idx >= toppingCosts.size()){
            int currDiff = abs(curr - target), ansDiff = abs(ans - target);
            if(currDiff < ansDiff){
                ans = curr;
            }else if(currDiff == ansDiff){
                ans = min(ans, curr);
            }
            return;
        }
        for(int i = 0; i < 3; i++){
            dfs(toppingCosts, idx + 1, target, curr, ans);
            curr += toppingCosts[idx];
        }
    }
};

Q3: Equal Sum Arrays With Minimum Number of Operations

每次操作最有效率能讓兩個陣列和更靠近的方法有兩種可能:

  1. 把較小陣列中最小值設為66
  2. 把較大陣列中最大值設為11

把兩個陣列各自排序,使用兩個指標,一個指在較小陣列的最小值,一個指在較大陣列的最大值,每次選擇兩者之間效益最大者,直到兩個陣列和相等為止。

Note

  1. 可以先判斷較大陣列的數量是否大於較小陣列數量的六倍,如果是的話就算把較大陣列所有元素都設成11、較小陣列設為66也沒辦法相等
  2. 實作時固定讓第一個陣列是較大陣列寫起來比較方便

Time Complexity: O(Nlog2N+Mlog2M)O(Nlog_2N + Mlog_2M)

Space Complexity: O(1)O(1)

class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int sum1 = 0, sum2 = 0, diff = 0;
        for(auto a : nums1) sum1 += a;
        for(auto a : nums2) sum2 += a;
        if(nums2.size() * 6 < nums1.size() || nums1.size() * 6 < nums2.size()) return -1;
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        // 1 bigger
        if(sum1 < sum2){
            swap(nums1, nums2);
            swap(sum1, sum2);
        }
        diff = sum1 - sum2;
        if(diff == 0) return 0;
        
        int ptr1 = nums1.size() - 1;
        int ptr2 = 0;
        int ans = 0;
        while(diff){
            ans++;
            if(ptr1 < 0){
                diff -= min(diff, 6 - nums2[ptr2++]);
            }else if(ptr2 == nums2.size()){
                diff -= min(diff, nums1[ptr1--] - 1);
            }else{
                int d1 = nums1[ptr1] - 1, d2 = 6 - nums2[ptr2];
                if(d1 > d2){
                    diff -= min(diff, d1);
                    ptr1--;
                }else{
                    diff -= min(diff, d2);
                    ptr2++;
                }
            }
        }
        return ans;
    }
};

Q4: Car Fleet II

比賽結束後晚了幾秒送出結果AC QAQ,寫出了O(N)O(N)的 monotonic stack 解法但過程打結好多次,後來才想到其實用O(Nlog2N)O(Nlog_2N)解法邏輯變單純很多...

O(Nlog2N)O(Nlog_2N) 解法:用 priority queue 每次都挑最早撞在一起的相鄰兩台合併,然後更新前一台撞到的時間 。這邊關鍵是要用 tree set 紀錄哪些車還沒被合併,這樣可以每次都用O(Nlog2N)O(Nlog_2N)找到前一台還沒被合併的是誰。

O(N)O(N) 解法:基本概念就是每台車都只在乎自己什麼時候會撞到前面的路隊長,如果這個時間比目前這個路隊長撞到他前面的路隊長的時間還要晚的話,代表自己實際撞到的時間是受更前面的路隊長影響。計算時一路 pop 到找到比自己晚才撞到的路隊長為止,所以最後這個 stack 裡每台車往前撞到的時間會呈遞增。

Time Complexity: O(Nlog2N)O(Nlog_2N) with priority queue, O(N)O(N) with stack

Space Complexity: O(N)O(N)

class Solution {
public:
    vector<double> getCollisionTimes(vector<vector<int>>& cars) {
        vector<double> ans(cars.size());
        // pair: { 路隊長id, 撞到的時間 }
        vector<pair<int, double>> mono;
        ans.back() = -1;
        for(int i = ans.size() - 2; i >= 0; i--){
            double t;
            int last = -1; // 自己會撞到的路隊長id
            // 以撞到前面一台的時間為基準開始往前找
            if(cars[i + 1][1] >= cars[i][1]) t = INT_MAX;
            else{
                t = (double)(cars[i + 1][0] - cars[i][0]) / (cars[i][1] - cars[i + 1][1]);
                last = i + 1;
            }
            while(mono.size() && mono.back().second < t){
                t = (cars[mono.back().first][1] >= cars[i][1])
                    ? INT_MAX
                    : (double)(cars[mono.back().first][0] - cars[i][0]) / (cars[i][1] - cars[mono.back().first][1]);
                last = mono.back().first;
                mono.pop_back();
            }
            ans[i] = t == INT_MAX ? -1 : t;
            mono.emplace_back(last, t);
        }
        return ans;
    }
};

< NewerLeetCode Biweekly Contest 47 Editorial
Back to blog