LeetCode Biweekly Contest 47 Editorial

LeetCode Biweekly Contest 47 Editorial | Blog | SH Liu | rarakasm

2021/03/06

LeetCode

競賽頁面網址

Q1: Find Nearest Point That Has the Same X or Y Coordinate

掃過一次、每次找到符合條件的對象時對答案進行更新即可。

Time Complexity: $O(N)$

Space Complexity: $O(1)$

class Solution {
public:
    int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
        int best = INT_MAX, ans = -1;
        for(int i = 0; i < points.size(); i++){
            auto p = points[i];
            if(x == p[0] || y == p[1]){
                int dist = abs(x - p[0]) + abs(y - p[1]);
                if(dist < best){
                    best = dist;
                    ans = i;
                }
            }
        }
        return ans;
    }
};

Q2: Check if Number is a Sum of Powers of Three

我們可以觀察到如果找出一個最大的 $a$ 符合 $N \geq 3^a$ ，那 $3^a$ 必定得出場，因為如果我們跳過去使用 $3^{a-1}$ 的話至少必須使用三次，違反題目不重複使用同樣冪次項的前提。因此我們可以從最大的 $a$ 一次一次遞減消除到 $N = 0$ 為止。過程中如果發現 $N \geq 3^a \times 2$ 代表找不到符合答案的結果。

Time Complexity: $O(log_3N)$

Space Complexity: $O(1)$

class Solution {
public:
    bool checkPowersOfThree(int n) {
        int p = 1;
        while(p * 3 <= n) p *= 3;
        while(n){
            while(p > n) p /= 3;
            if(n - p >= p) return false;
            n -= p;
        }
        return true;
    }
};

Q3: Sum of Beauty of All Substrings

$N$ 很小，⭐暴力解⭐

Time Complexity: $O(26 \times N^2)$

Space Complexity: $O(1)$

class Solution {
public:
    int beautySum(string s) {
        int ans = 0;
        for(int i = 0; i < s.size(); i++){
            int cnt[26];
            memset(cnt, 0, sizeof(cnt));
            for(int j = i; j < s.size(); j++){
                cnt[s[j] - 'a']++;
                int mn = INT_MAX, mx = INT_MIN;
                for(int k = 0; k < 26; k++)
                    if(cnt[k]) mn = min(mn, cnt[k]), mx = max(mx, cnt[k]);
                ans += mx - mn;
            }
        }
        return ans;
    }
};

Q4: Count Pairs Of Nodes

因為 $N$ 蠻大的，如果算出每個pair的答案不管怎樣都至少會是 $O(N^2)$ ，會超過時間。

我們可以先把所有節點的度數算出來，並用map的結構紀錄每個節點 $a$ 與其所有相鄰節點 $b_i$ 各有幾個重複的邊（即兩端皆為 $a$ 與 $b_i$ ）。

先將所有度數複製一份然後作排序，這樣我們可以用lower_bound以 $O(log_2N)$ 的時間找出有幾個數字比任意一個指定的 $k$ 還大。

接下來對於每次 query，我們為每個節點算出至少需要找到度數多少以上的節點才有可能滿足這個 $q$ 。這邊可以用上述的排序度數來快速求到答案，不過在得到的數字裡面有可能多算了三種不合乎條件的答案：

自己
自己的鄰居，跟他有很多個邊重複，導致雖然 $deg(a) + deg(b) > q$ 但 $deg(a) + deg(b) - adj(a,b) \leq q$
$b < a$

第三種的部份我們可以在最後對答案除以 $2$ 來解決，而第一種我們可以判斷自己是否在滿足條件的區間中。

至於第二種，我們可以遍歷自己的所有鄰居來把符合這個條件的鄰居從答案中扣掉。這邊感覺複雜度好像很高，但因為 $|edges| \leq 10^5$ ，每次 query 遍歷的鄰居數量不會超過這個數字的兩倍。

...不過我比賽時送出最簡單的版本莫名其妙TLE，後來為lower_bound做了快取跟判斷提早結束跳過遍歷鄰居才AC，但我感覺就算不優化worst case還是可以過，不知道之後重算時間會不會幫我平反QQ

2021/03/07 更新

發現其實可以用2 pointer的方式一次把所有可能的pair算出來再扣掉多算的鄰居，這樣每次就少了 $logN$ 的二分搜尋。

Time Complexity: $O(Nlog_2N + Q(N + |E|))$ with 2-pointer, $O(Q(Nlog_2N + |E|))$ with binary search

Space Complexity: $O(N+|E|)$

class Solution {
public:
    vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
        vector<int> cnt(n);
        vector<unordered_map<int, int>> adj(n);
        for(auto& e : edges){
            e[0]--, e[1]--;
            adj[e[0]][e[1]]++;
            adj[e[1]][e[0]]++;
            cnt[e[0]]++, cnt[e[1]]++;
        }
        vector<int> sorted(cnt);
        sort(sorted.begin(), sorted.end());
        vector<int> ans;
        for(auto q : queries){
            int sum = getSum(sorted, q);
            for(int i = 0; i < n; i++){
                for(auto& p : adj[i]){
                    if(p.first > i  // a < b contraint
                       && cnt[i] + cnt[p.first] > q
                       && cnt[i] + cnt[p.first] - p.second <= q){
                        sum--;
                    }
                }
            }
            ans.push_back(sum);
        }
        return ans;
    }
    
    int getSum(vector<int>& sorted, int q){
        // 2 ptr O(N)
        int l = 0, r = sorted.size() - 1, sum = 0;
        while(l < sorted.size()){
            while(l < r && sorted[l] + sorted[r] > q){
                r--;
            }
            sum += min(sorted.size() - l - 1, 
                       sorted.size() - r - 1);
            l++;
        }
        return sum;
    }
};

< NewerLeetCode Weekly Contest 231 Editorial

Back to blog

Older >LeetCode Weekly Contest 230 Editorial

SHL Blog