Leetcode 周赛题解 220

ACM算法日常

发布于 2020-12-31 10:18:26

4120

发布于 2020-12-31 10:18:26

文章被收录于专栏：ACM算法日常ACM算法日常

这场全是经典套路题。最后一题给了两种做法，锻炼算法。

难度顺序：

A\le B\le C\le D

。

5629. 重新格式化电话号码

给你一个字符串形式的电话号码 number 。number 由数字、空格 ' '、和破折号 '-' 组成。

请你按下述方式重新格式化电话号码。

首先，「删除」 所有的空格和破折号。
其次，将数组从左到右每 3 个一组分块，直到剩下 4 个或更少数字。剩下的数字将按下述规定再分块：
- 2 个数字：单个含 2 个数字的块。
- 3 个数字：单个含 3 个数字的块。
- 4 个数字：两个分别含 2 个数字的块。

最后用破折号将这些块连接起来。注意，重新格式化过程中 「不应该」 生成仅含 1 个数字的块，并且 「最多」 生成两个含 2 个数字的块。

返回格式化后的电话号码。

「提示：」

2 <= number.length <= 100
number 由数字和字符 '-' 及 ' ' 组成。
number 中至少含 「2」 个数字。

「思路：」

按题意模拟即可。

时间复杂度：

O(n)

class Solution {
public:
    string reformatNumber(string number) {
        string ret = "", ans = "";
        for(char c: number) {
            if(isdigit(c)) ret += c;
        }
        int n = ret.length();
        for(int i = 0; i < n; ) {
            if(n - i > 4) {
                if(ans.length()) ans += '-';
                for(int j = 0; j < 3; ++j) ans += ret[i++];
            }else if(n - i == 4) {
                if(ans.length()) ans += '-';
                for(int j = 0; j < 2; ++j) ans += ret[i++];
                if(ans.length()) ans += '-';
                for(int j = 0; j < 2; ++j) ans += ret[i++];
            }else if(n - i == 3) {
                if(ans.length()) ans += '-';
                for(int j = 0; j < 3; ++j) ans += ret[i++];
            }else if(n - i == 2) {
                if(ans.length()) ans += '-';
                for(int j = 0; j < 2; ++j) ans += ret[i++];
            }else {
                if(ans.length()) ans += '-';
                for(int j = 0; j < 1; ++j) ans += ret[i++];
            }
        }
        return ans;
    }
};

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

给你一个正整数数组 nums ，请你从中删除一个含有 「若干不同元素」 的子数组**。**删除子数组的 「得分」 就是子数组各元素之 「和」 。

返回 「只删除一个」 子数组可获得的 「最大得分」 。

如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。

「提示：」
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4

「思路：」双指针。每次移动右指针，当某个数字出现两次之后，移动左指针直到合法为止。

时间复杂度：

O(n)

const int MXN = 1e4 + 5;
class Solution {
public:
    int vis[MXN];
    int maximumUniqueSubarray(vector<int>& nums) {
        int l = 0, n = nums.size();
        int ans = 0, ret = 0;
        for(int i = 0; i < n; ++i) {
            ++ vis[nums[i]];
            ret += nums[i];
            while(vis[nums[i]] >= 2) {
                -- vis[nums[l]];
                ret -= nums[l];
                ++ l;
            }
            ans = max(ans, ret);
        }
        return ans;
    }
};

5631. 跳跃游戏 VI

给你一个下标从 「0」 开始的整数数组 nums 和一个整数 k 。

一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 「包含」 两个端点的任意位置。

你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 「得分」 为经过的所有数字之和。

请你返回你能得到的 「最大得分」 。

「提示：」
- 1 <= nums.length, k <= 10^5
- -10^4 <= nums[i] <= 10^4

「思路」

单调队列优化

。

dp[i]=max(dp[i-1],...,dp[i-k])+nums[i]

。

用单调队列来维护后连续

个

值的最大值即可。

时间复杂度：

O(n)

const int MXN = 1e5 + 5;
class Solution {
public:
    int dp[MXN], dq[MXN];
    int maxResult(vector<int>& nums, int k) {
        int l = 0, r = 0, n = nums.size();
        dq[r++] = 0;
        dp[0] = nums[0];
        for(int i = 1; i < n; ++i) {
            dp[i] = nums[i] + dp[dq[l]];
            while(l < r && i - dq[l] + 1 >= k + 1) {
                ++ l;
            }
            while(l < r && dp[dq[r - 1]] <= dp[i]) -- r;
            dq[r++] = i;
        }
        return dp[n - 1];
    }
};

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

给你一个 n 个点组成的无向图边集 edgeList ，其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边。请注意，两个点之间可能有 「超过一条边」 。

给你一个查询数组queries ，其中 queries[j] = [pj, qj, limitj] ，你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径，且这条路径上的每一条边都 「严格小于」 limitj 。

请你返回一个 「布尔数组」 answer ，其中 answer.length == queries.length ，当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false 。

「提示：」
- 2 <= n <= 10^5
- 1 <= edgeList.length, queries.length <= 10^5
- edgeList[i].length == 3
- queries[j].length == 3
- 0 <= ui, vi, pj, qj <= n - 1
- ui != vi
- pj != qj
- 1 <= disi, limitj <= 10^9
- 两个点之间可能有 「多条」 边。

「思路」

本题肯定构成出一颗最小生成树是最优的选择。

接下来只需要判断在最小生成树上，询问的

p_i

和

q_i

路径上的最大值是否小于

limit_i

即可。

我们把询问按照权值从小到大排序，然后枚举每一个询问，每次把边权小于

limit_j

的边用来构造

kruskal

最小生成树，然后判断此时

p_j

和

q_j

是否联通即可。

这题有一坑在于给你的不一定是一个连通图。

时间复杂度：

O(n*log(n))

const int MXN = 1e5 + 5;
class Solution {
public:
    struct Query {
        int u, v, w, id;
    }Q[MXN];
    struct node {
        int u, v, w;
    }edge[MXN];
    int FA[MXN];
    static bool cmp(const node&a, const node&b) {
        return a.w < b.w;
    }
    static bool cmp2(const Query&a, const Query&b) {
        return a.w < b.w;
    }
    int Fi(int x) {
        return FA[x] == x? x: FA[x] = Fi(FA[x]);
    }
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
        int m = edgeList.size();
        int qm = queries.size();
        vector<bool> ans(qm, true);
        for(int i = 1; i <= n; ++i) FA[i] = i;
        for(int i = 0; i < m; ++i) {
            edge[i].u = edgeList[i][0] + 1;
            edge[i].v = edgeList[i][1] + 1;
            edge[i].w = edgeList[i][2];
        }
        for(int i = 0; i < qm; ++i) {
            Q[i].u = queries[i][0] + 1;
            Q[i].v = queries[i][1] + 1;
            Q[i].w = queries[i][2];
            Q[i].id = i;
        }
        sort(edge, edge + m, cmp);
        sort(Q, Q + qm, cmp2);
        int j = 0;
        for(int i = 0; i < qm; ++i) {
            while(j < m && edge[j].w < Q[i].w) {
                int pa = Fi(edge[j].u), pb = Fi(edge[j].v);
                if(pa != pb) FA[pb] = pa;
                ++ j;
            }
            ans[Q[i].id] = (Fi(Q[i].u) == Fi(Q[i].v));
        }
        return ans;
    }
};

还有另一种在线做法，就是用树上倍增+

lca

直接莽那个询问。

树上倍增求出

dis[u][i]

每个点

向上走

2^i

步路径上的最大边权的权值，

up[u][i]

每个点

向上走

2^i

步走到的点是谁。然后询问就是一个求

lca

的过程，跳

lca

的时候维护这个最大值即可。

一定要注意，给你的不是连通图。

所以倍增预处理的时候，一定要把每一个联通块都处理一遍。

求答案的时候判断一下是否两点是否联通。

const int MXN = 1e5 + 5;
const int MXE = MXN * 2 + 1;
class Solution {
public:
    struct lp {
        int v, w, nex;
    }cw[MXE];
    struct node {
        int u, v, w;
    }edge[MXE];
    int _n, m, tot, head[MXN], dep[MXN], FA[MXN], up[MXN][21], dis[MXN][21];
    int vis[MXN];
    void init() {
        tot = -1;
        for(int i = 1; i <= _n; ++i) head[i] = -1, FA[i] = i, vis[i] = 0;
    }
    void add_edge(int u, int v, int w) {
        cw[++tot].v = v, cw[tot].w = w, cw[tot].nex = head[u];
        head[u] = tot;
        cw[++tot].v = u, cw[tot].w = w, cw[tot].nex = head[v];
        head[v] = tot;
    }
    static bool cmp(const node&a, const node&b) {
        return a.w < b.w;
    }
    int Fi(int x) {
        return FA[x] == x? x: FA[x] = Fi(FA[x]);
    }
    void dfs(int u, int ba, int d) {
        vis[u] = 1;
        up[u][0] = ba;
        dep[u] = d;
        for(int i = 1; i < 21; ++i) {
            int cf = up[u][i - 1];
            up[u][i] = up[cf][i - 1];
            dis[u][i] = max(dis[u][i - 1], dis[cf][i - 1]);
        }
        for(int i = head[u]; ~i; i = cw[i].nex) {
            int v = cw[i].v;
            if(v == ba) continue;
            dis[v][0] = cw[i].w;
            dfs(v, u, d + 1);
        }
    }
    int LCA(int x, int y) {
        int ans = 0;
        if(dep[x] < dep[y]) swap(x, y);
        for(int i = 20; i >= 0; --i) {
            if(dep[up[x][i]] >= dep[y]) {
                ans = max(ans, dis[x][i]);
                x = up[x][i];
            }
        }
        if(x != y) {
            for(int i = 20; i >= 0; --i) {
                if(up[x][i] != up[y][i]) {
                    ans = max({ans, dis[x][i], dis[y][i]});
                    x = up[x][i];
                    y = up[y][i];
                }
            }
            ans = max({ans, dis[x][0], dis[y][0]});
        }
        return ans;
    }
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
        _n = n;
        m = edgeList.size();
        init();
        for(int i = 0; i < m; ++i) {
            edge[i].u = edgeList[i][0] + 1;
            edge[i].v = edgeList[i][1] + 1;
            edge[i].w = edgeList[i][2];
        }
        sort(edge, edge + m, cmp);
        int cnt = 0;
        for(int i = 0; i < m; ++i) {
            int pa = Fi(edge[i].u), pb = Fi(edge[i].v);
            if(pa == pb) continue;
            FA[pb] = pa;
            add_edge(edge[i].u, edge[i].v, edge[i].w);
            ++ cnt;
            if(cnt == n - 1) break;
        }
        for(int i = 1; i <= n; ++i) if(vis[i] == 0) dfs(i, i, i);
        m = queries.size();
        vector<bool> ans(m, 0);
        for(int i = 0; i < m; ++i) {
            int tmp = LCA(queries[i][0] + 1, queries[i][1] + 1);
            if(tmp < queries[i][2]) ans[i] = true;
            if(Fi(queries[i][0] + 1) != Fi(queries[i][1] + 1)) ans[i] = false;
        }
        return ans;
    }
};

温馨提示

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-12-20，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度