LeetCode Weekly Contest 231 Editorial

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

2021/03/07

LeetCode

競賽頁面網址

Q1: Check if Binary String Has at Most One Segment of Ones

從左往右掃，用一個boolean紀錄遇到 $0$ 了沒，如果遇到 $1$ 的時候發現之前已經遇到 $0$ 就回傳false。

Time Complexity: $O(N)$

Space Complexity: $O(1)$

class Solution {
public:
    bool checkOnesSegment(string s) {
        bool hasMetZero = false;
        for(auto c : s){
            if(c == '1'){
                if(hasMetZero){
                    return false;
                }
            }else{
                hasMetZero = true;
            }
        }
        return true;
    }
};

Q2: Minimum Elements to Add to Form a Given Sum

limit代表我們每次加入一個數字最多可以讓sum往goal靠近多少，所以答案其實就是 $\lceil \frac {|goal - sum|} {limit} \rceil$ 。

Time Complexity: $O(N)$

Space Complexity: $O(1)$

class Solution {
public:
    int minElements(vector<int>& nums, int limit, int goal) {
        long sum = 0;
        for(auto a : nums) sum += a;
        long diff = abs((long)goal - sum);
        int ans = diff / limit;
        if(diff % limit) ans += 1;
        return ans;
    }
};

Q3: Number of Restricted Paths From First to Last Node

Dijkstra's Algorithm on a medium question? Really? 而且還要再做一層 greedy？雖然不是真的很難但寫的時候一直在懷疑是不是有比較快的做法...

演算法分成三個階段：

將edges轉為 adjacent maps
將每個節點與最後節點的最短距離 $z_i$ 算出來 (Dijkstra's)
因為只有當 $z_i > z_j$ 時 $i$ 才能走向 $j$ ，我們從有最大 $z$ 的節點開始考慮有多少走法可以走到這個節點。

Time Complexity: $O((|E| + N)log_2N)$

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

struct P{
    int to;
    long c;
    P(int to, long c) : to(to), c(c) {}
    bool operator < (const P& other) const {
        return c > other.c; // invert operator to make a min heap
    }
};

struct Q{
    int i, c;
    Q(int i, int c) : i(i), c(c) {}
    bool operator < (const Q& other) const {
        return c < other.c; // max heap by default
    }
};

class Solution {
public:
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        vector<unordered_map<int, int>> adj(n);
        for(auto& e : edges){
            e[0]--, e[1]--;
            adj[e[0]][e[1]] = e[2];
            adj[e[1]][e[0]] = e[2];
        }
        vector<long> toLast(n, -1);
        
        priority_queue<P> pq;
        pq.emplace(n - 1, 0);
        while(pq.size()){
            auto [to, c] = pq.top();
            pq.pop();
            if(toLast[to] != -1) continue;
            toLast[to] = c;
            for(auto& e : adj[to]){
                if(toLast[e.first] == -1){
                    pq.emplace(e.first, c + e.second);
                }
            }
        }
        
        priority_queue<Q> pq2;
        for(int i = 0; i < n; i++) pq2.emplace(i, toLast[i]);
        vector<long> ans(n);
        ans[0] = 1;
        int mod = 1e9 + 7;
        while(pq2.size()){
            auto [i, c] = pq2.top();
            pq2.pop();
            if(i == 0) continue;
            for(auto& e : adj[i]){
                if(toLast[e.first] > c){
                    ans[i] = (ans[i] + ans[e.first]) % mod;
                }
            }
        }
        
        return ans[n - 1];
    }
};

Q4: Make the XOR of All Segments Equal to Zero

比賽時沒寫出來，想到最基本的DP解法但TLE，結束後看別人答案發現其實是對的方向但要進一步做優化。

可以觀察到最後產出的陣列裡對於所有 $i$ （ $0 \leq i < k$ ）來說， $a_i = a_{i+k} = a_{i + 2k} = ...$ ，所以我們可以算出如果要把 $a_i$ 換成某個數字 $p$ 需要一併改多少數字。

用 $dp(t, x)$ 代表「讓前 $t$ 個元素互 XOR 為 $x$ 最少要改幾個數字」，從下而上做出來把所有可能的組合都做轉移的話複雜度會是 $O(2^{20}k)$ 。

要節省時間的話，我們可以發現對於任何可能的結果 $a$ 來說，如果有 $b$ 個數字位於 $i_b \pmod k = t$ ，則：

dp(t + 1, a) \leq min(dp(t, s = 0...1023)) + b

因為不管有最小 $dp(t, s)$ 的 $s$ 為何，我們必定可以將所有的數字換成 $a \oplus s$ 來得到 $a$ 的結果。有了這個上界之後，我們就可以跳過沒出現過的數字不做轉移；因為對每個 $t$ 來說至多只會有 $\lceil \frac N k \rceil$ 種不同的數字需要做轉移，最後複雜度會是 $O(k \times 2^{10} \times {\frac N k}) = O(2^{10}N)$ 。

Time Complexity: $O(2^{10}N)$

Space Complexity: $O(2^{10}k)$ ，但可以壓到 $O(2^{10})$

class Solution {
public:
    int minChanges(vector<int>& nums, int k) {
        int cnt[k][1024];
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < nums.size(); i++){
            cnt[i % k][nums[i]]++;
        }
        int cost[k][1024];
        int sum[k];
        for(int i = 0; i < k; i++){
            sum[i] = 0;
            for(int j = 0; j < 1024; j++){
                sum[i] += cnt[i][j];
            }
            for(int j = 0; j < 1024; j++){
                cost[i][j] = sum[i] - cnt[i][j];
            }
        }
        int dp[k + 1][1024];
        memset(dp, -1, sizeof(dp));
        dp[0][0] = 0;
        for(int t = 0; t < k; t++){
            int lastMin = INT_MAX;
            for(int i = 0; i < 1024; i++){
                if(dp[t][i] != -1) lastMin = min(lastMin, dp[t][i]);
            }
            for(int i = 0; i < 1024; i++){
                dp[t + 1][i] = lastMin + sum[t];
            }
            for(int j = 0; j < 1024; j++){
                if(sum[t] != cost[t][j]){
                    for(int i = 0; i < 1024; i++){
                        if(dp[t][i] == -1) continue;
                        dp[t + 1][i ^ j] = dp[t + 1][i ^ j] == -1
                            ? dp[t][i] + cost[t][j]
                            : min(dp[t + 1][i ^ j], dp[t][i] + cost[t][j]);
                    }
                }
            }
        }
        return dp[k][0];
    }
};

< NewerLeetCode Weekly Contest 232 Editorial

Back to blog

Older >LeetCode Biweekly Contest 47 Editorial

SHL Blog