LeetCode Weekly Contest 232 Editorial

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

2021/03/14

LeetCode

競賽頁面網址

Q1: Check if One String Swap Can Make Strings Equal

先比對是不是不用做任何操作，接著從左往右掃，找到兩個不同字母的位置就互換然後終止掃描來做判斷。

Time Complexity: $O(N)$

Space Complexity: $O(1)$

class Solution {
public:
    bool areAlmostEqual(string s1, string s2) {
        if(s1 == s2) return true;
        int lastDiff = -1;
        for(int i = 0; i < s1.size(); i++){
            if(s1[i] != s2[i]){
                if(lastDiff == -1){
                    lastDiff = i;
                }else{
                    swap(s1[i], s1[lastDiff]);
                    break;
                }
            }
        }
        return s1 == s2;
    }
};

Q2: Find Center of Star Graph

因為邊只有 $N-1$ 個，所以如果有一個中心節點的話一定所有邊都有跟他連結，檢查前兩個邊找到共通的端點即可。

Time Complexity: $O(1)$

Space Complexity: $O(1)$

class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        unordered_map<int, int> cnt;
        for(int i = 0; i < 2; i++){
            auto& e = edges[i];
            cnt[e[0]]++;
            cnt[e[1]]++;
        }
        for(auto p : cnt) if(p.second > 1) return p.first;
        return -1;
    }
};

Q3: Maximum Average Pass Ratio

可以觀察到最有效率的方式就是把好學生安插到人數小又最小比例學生合格的班級，但因為加進去之後這個狀態會改變，我們可以使用一個priority queue在任何時間都貪心地挑效益最高的班級把下個好學生放進去。

Time Complexity: $O((M + N)log_2N)$

Space Complexity: $O(N)$

struct P {
    int p, t; // pass, total
    double g; // expected gain if we add a good student here
    P(int p, int t, double g) : p(p), t(t), g(g) {}
    bool operator < (const P& other) const {
        return g < other.g; // max heap
    }
};

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        priority_queue<P> pq;
        for(auto& c : classes){
            pq.emplace(c[0], c[1], (double)(c[0] + 1) / (c[1] + 1) - (double)c[0] / c[1]);
        }
        for(int i = 0; i < extraStudents; i++){
            auto p = pq.top();
            pq.pop();
            p.p++;
            p.t++;
            p.g = (double)(p.p + 1) / (p.t + 1) - (double)p.p / p.t;
            pq.push(p);
        }
        double sum = 0;
        while(pq.size()){
            auto p = pq.top();
            sum += (double)p.p / p.t;
            pq.pop();
        }
        sum /= classes.size();
        return sum;
    }
};

Q4: Maximum Score of a Good Subarray

有點像反方向的 11. Container With Most Water，從中間往外擴張，每次從左右兩邊挑一個數字最大的方向走，這樣可以確保我們在擴張的同時用最慢的速度降低區間的最小值。

Time Complexity: $O(N)$

Space Complexity: $O(1)$

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int l = k, r = k, ans = nums[k], currMn = nums[k];
        while(l > 0 || r < nums.size() - 1){
            if(r == nums.size() - 1){
                l--;
            }else if(l == 0){
                r++;
            }else if(nums[l - 1] > nums[r + 1]){
                l--;
            }else{
                r++;
            }
            currMn = min({currMn, nums[l], nums[r]});
            ans = max(ans, currMn * (r - l + 1));
        }
        return ans;
    }
};

< NewerA year of LeetCode

Back to blog

Older >LeetCode Weekly Contest 231 Editorial

SHL Blog