Leetcode 220 周赛 题解

• 2020 年 12 月 20 日
• 筆記
• leetcode

5629. 重新格式化电话号码

模拟

注意一些细节，最后位置是否取值。

class Solution {
public:
    string reformatNumber(string number) {
        string s;
        for (auto c: number)
            if (c != ' ' && c != '-')
                s += c;
        string res;
        for (int i = 0; i < s.size();) {
            if ((int)s.size() - i > 4) res = res + s[i] + s[i + 1] + s[i + 2] + '-', i += 3;
            else {
                int x = s.size() - i;
                if (x == 2) res = res + s[i] + s[i + 1];
                else if (x == 3) res = res + s[i] + s[i + 1] + s[i + 2];
                else res = res + s[i] + s[i + 1] + '-' + s[i + 2] + s[i + 3];
                res += '-';
                i += 4;
            }
        }
        res.pop_back();
        return res;
    }
};

5630. 删除子数组的最大得分

优先队列

class Solution {
public: 
    deque<int> q;
    map<int,int> mp;
    int maximumUniqueSubarray(vector<int>& nums) {
       
        int num = 0,mn = 0;
        for(int i = 0; i < nums.size(); i++){
            if(!mp[nums[i]]) mp[nums[i]] = 1;
            else {
                while(q.size() && nums[q.front()] != nums[i]) mp[nums[q.front()]] = 0,num -= nums[q.front()],q.pop_front();
                if(q.size() && nums[q.front()] == nums[i]) num -= nums[q.front()],q.pop_front();
            }
            q.push_back(i);
            num += nums[i];
            mn = max(num,mn);
        }
        return mn;
    }
};

1686. 石子游戏 VI

优先队列优化dp

class Solution {
public:
//dp[i] = max(dp[i-1]~dp[(i-k)] + nums[i]);
    int dp[100000 + 10];
    deque<int> q;
    int maxResult(vector<int>& nums, int k) {
        memset(dp,128,sizeof dp);
        int n = nums.size();
        dp[0] = nums[0];
        q.push_back(0);

        for(int i = 1; i < n; i ++){
            while(i - q.front() > k) q.pop_front();
            dp[i] = dp[q.front()] + nums[i];
            while(q.size() && dp[q.back()] < dp[i]) q.pop_back();
        }
        return dp[n-1];
    }
};

也可以用multiset优化

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> f(n);
        multiset<int> S;
        f[0] = nums[0];
        S.insert(f[0]);
        for (int i = 1; i < n; i ++ ) {
            if (i - k - 1 >= 0)
                S.erase(S.find(f[i - k - 1]));
            f[i] = nums[i] + *S.rbegin();
            S.insert(f[i]);
        }
        return f[n - 1];
    }
};

5632. 检查边长度限制的路径是否存在

排序 + 并查集

考虑边，对判断和原始边都进行从小到大排序，对满足限制边的原始边进行建图连边，判断是否存在/满足条件的结果。

排序后可以保证小的边限制能满足的情况下，大边同样能满足。

用并查集判断是否存在相应的边即可。

const int MAXN = 1e5 + 50;

int m, Q;
struct Node{ int u, v, w, i; } edge[MAXN], query[MAXN];
bool ans[MAXN];
bool cmp(const Node &a, const Node &b){ return a.w < b.w;  }

int father[MAXN];
int getFather(int x){ return father[x] = (father[x] == x ? x: getFather(father[x])); }
void mergeFather(int x, int y){
    int fx = getFather(x), fy = getFather(y);
    if (fx == fy) return;
    if (fx > fy) swap(fx, fy);
    father[fx] = fy;
}

class Solution {
public:
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
        m = edgeList.size(); Q = queries.size();
        
        for (int i = 0; i < m; i++){
            edge[i].u = edgeList[i][0];
            edge[i].v = edgeList[i][1];
            edge[i].w = edgeList[i][2];
        }
        for (int i = 0; i < Q; i++){
            query[i].u = queries[i][0];
            query[i].v = queries[i][1];
            query[i].w = queries[i][2];
            query[i].i = i;
        }
        
        sort(edge, edge + m, cmp); sort(query, query + Q, cmp);
        
        for (int i = 0; i <= n; i++) father[i] = i;
        for (int i = 0, k = 0; i < Q; i++){
            while(k < m && edge[k].w < query[i].w) {
                mergeFather(edge[k].u, edge[k].v); 
                k++;
            }
            ans[query[i].i] = (getFather(query[i].u) == getFather(query[i].v));
        }
        
        vector<bool> ret;
        for (int i = 0; i < Q; i++) ret.push_back(ans[i]);
        return ret;
    }
};