LeetCode Biweekly Contest 48 Editorial

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

2021/03/20

LeetCode

競賽頁面網址

Q1: Second Largest Digit in a String

應該沒什麼難度只是看哪個實作方法比較快，我是用排序的 tree set 方便找到倒數第二個數。

Time Complexity: $O(N)$

Space Complexity: $O(1)$ , $|d| \leq 10$

class Solution {
public:
    int secondHighest(string s) {
        set<int> d;
        for(auto a : s){
            if(isdigit(a)) d.insert(a - '0');
        }
        if(d.size() < 2) return -1;
        auto it = d.end();
        it--;
        it--;
        return *it;
    }
};

Q2: Design Authentication Manager

實作題，重點就是用priority queue來進行時間的模擬以及hash map/set記錄不同ID的狀態，然後用一個變數renewed追蹤priority queue裡面有幾個已經被更新過的紀錄。

Time Complexity: $O(Nlog_2N)$

Space Complexity: $O(N)$

struct P{
    string tokenId;
    int exp;
    P(string tokenId, int exp) : tokenId(tokenId), exp(exp){}
    bool operator < (const P& other) const {
        return exp > other.exp; // inverted to make min heap
    }
};

class AuthenticationManager {
    int ttl;
    unordered_map<string, int> expireTime;
    unordered_set<string> expired;
    priority_queue<P> pq;
    int renewed = 0;
public:
    AuthenticationManager(int timeToLive) {
        ttl = timeToLive;
    }
    
    void update(int curr){
        while(pq.size() && pq.top().exp <= curr){
            if(expireTime[pq.top().tokenId] != pq.top().exp){
                renewed--; // 這個tokenId已經更新過，目前手上的是舊的過期事件
            }else{
                expired.insert(pq.top().tokenId);
            }
            pq.pop();
        }
    }
    
    void generate(string tokenId, int currentTime) {
        update(currentTime);
        
        expireTime[tokenId] = currentTime + ttl;
        pq.emplace(tokenId, currentTime + ttl);
    }
    
    void renew(string tokenId, int currentTime) {
        update(currentTime);
        if(expired.find(tokenId) != expired.end()
         || expireTime.find(tokenId) == expire.end()) 
            return;
        expireTime[tokenId] = currentTime + ttl;
        pq.emplace(tokenId, currentTime + ttl);
        renewed++;
    }
    
    int countUnexpiredTokens(int currentTime) {
        update(currentTime);
        return pq.size() - renewed;
    }
};

Q3: Maximum Number of Consecutive Values You Can Make

寫的時候有點腦袋當機... 先將所有硬幣排序，再從小到大掃，如果目前的數值 $coins[i]$ $\leq$ 目前可以湊到的最大數字 $curr +1$ ，代表從 $curr$ 到 $curr + coins[i]$ 之間每個整數也都有辦法湊到。若否則無法繼續接龍，提早結束回傳答案。

Time Complexity: $O(Nlog_2N)$

Space Complexity: $O(1)$

class Solution {
public:
    int getMaximumConsecutive(vector<int>& coins) {
        sort(coins.begin(), coins.end());
        int curr = 0;
        for(int i = 0; i < coins.size(); i++){
            if(coins[i] <= curr + 1){
                curr += coins[i];
            }else{
                break;
            }
        }
        return curr + 1;
    }
};

Q4: Maximize Score After N Operations

用 bitmask 紀錄用過哪些數字的狀態下最高分是多少，然後一次一次為每個狀態選擇所有沒拿過的組合來作狀態轉移。

Time Complexity: $O(2^NN^3)$

Space Complexity: $O(2^NN)$ ，可以壓成 $O(2^N)$

class Solution {
public:
    int maxScore(vector<int>& nums) {
        int gcdTable[nums.size()][nums.size()];
        for(int i = 0; i < nums.size(); i++){
            for(int j = 0; j < nums.size(); j++){
                gcdTable[i][j] = gcd(nums[i], nums[j]);
            }
        }
        int n = nums.size() / 2;
        int score[n + 1][1 << nums.size()];
        memset(score, -1, sizeof(score));
        score[0][0] = 0;
        for(int i = 1; i <= n; i++){ 
            for(int j = 0; j < (1 << nums.size()); j++){
                if(score[i - 1][j] != -1){ // 合法狀態，嘗試所有可能的轉移
                    for(int p = 0; p < nums.size(); p++){
                        if((1 << p) & j) continue; // p 拿過了，跳過
                        for(int q = p + 1; q < nums.size(); q++){
                            if((1 << q) & j) continue; // q 拿過了，跳過
                            // 新的狀態 = 原本拿的 + p + q
                            int target = j | (1 << p) | (1 << q);
                            score[i][target] = score[i][target] == -1
                                ? score[i - 1][j] + gcdTable[p][q] * i
                                : max(score[i][target], score[i - 1][j] + gcdTable[p][q] * i);
                        }
                    }
                }
            }
        }
        int ans = 0;
        for(int i = 0; i < (1 << nums.size()); i++) ans = max(ans, score[n][i]);
        return ans;
    }
};

Back to blog

Older >A year of LeetCode

SHL Blog