首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >不愧是自动驾驶公司,周赛考大家基环树

不愧是自动驾驶公司,周赛考大家基环树

作者头像
ACM算法日常
发布2022-01-06 20:32:24
5130
发布2022-01-06 20:32:24
举报
文章被收录于专栏:ACM算法日常ACM算法日常

本场周赛由 AutoX 联名,作为新年第一场力扣周赛,题目还挺有意思的,是个头脑风暴的好选择。

涉及的知识点:贪心,拓扑排序,动态规划,图数据挖掘

5967. 检查是否所有 A 都在 B 之前

给定一个只包含 A, B 的字符串,判断是否所有的字符 A 都出现在字符 B

题解

容易归纳出,符合题意的字符串要么是 A..AB..B 式,要么是 B..B 式,用一个 flag 标记即可

// cpp
class Solution {
public:
    bool checkString(string s) {
        bool flag = false;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == 'b') flag = true;
            else if (flag && s[i] == 'a') return false;
        }
        return true;
    }
};

5968. 银行中的激光束数量

给定 n 个长为 m 01 字符串,对于相邻的两个字符串,它们任意两个 1 可以组成一个激光束,计算所有激光束数量

题解

先处理出每个字符串含有的 1 的数量,并且把不含 1 的字符串剔除

然后相邻的两个值乘起来即可,求和即为答案

// cpp
class Solution {
public:
    int numberOfBeams(vector<string>& bank) {
        vector<int> vec;
        for (auto& i: bank) {
            int cnt = 0;
            for (auto& j: i) if (j == '1') cnt++;
            if (cnt) vec.push_back(cnt);
        }
        int ans = 0;
        for (int i = 0; i < static_cast<int>(vec.size()) - 1; ++i) {
            ans += vec[i] * vec[i + 1];
        }
        return ans;
    }
};

5969. 摧毁小行星

有一个质量为 m 的行星,以及 n 个质量为 a_{i} 的小行星你可以任意排列小行星的顺序,让行星与之相撞,相撞的条件是 m\geq a_{i} ,同时相撞之后由于相吸效应,行星质量要加上a_{i} 请你判断行星是否可以撞毁所有小行星?

数据规定1\leq n,\ m,\ a_{i}\leq 10^5

题解

考虑贪心,我们选取剩下的小行星中最大的不超过 m 的行星,拿出来和行星撞一下,这样可以保证行星的质量局部最大,在之后的相撞中不落下风

可以用一个有序集和来存储数据,找到相撞的行星后将其删除,时间复杂度\mathcal{O}(n\log n)

// cpp
class Solution {
public:
    bool asteroidsDestroyed(int m, vector<int>& a) {
        typedef long long LL;
        multiset<LL> st(a.begin(), a.end());
        LL sum = m;
        int n = static_cast<int>(a.size());
        for (int i = 0; i < n; ++i) {
            auto x = st.upper_bound(sum);
            if (x == st.begin()) return false;
            x--;
            sum += (*x);
            st.erase(x);
        }
        return true;
    }
};

也可以从最小的开始吸收,代码更简单

// cpp
class Solution {
public:
    bool asteroidsDestroyed(int m, vector<int>& a) {
        sort(a.begin(), a.end());
        typedef long long LL;
        LL sum = m;
        for (int i = 0; i < static_cast<int>(a.size()); ++i) {
            if (sum < a[i]) return false;
            sum += a[i];
        }
        return true;
    }
};

5970. 参加会议的最多员工数

n 个员工,每个员工有一个心仪的对象(保证不是自己)

有一个无限大的圆桌,如果一个员工旁边坐着自己心仪的对象,那么他就会参加会议

请问最多有多少员工参加会议?

数据规定1\leq n\leq 10^5

题解

考虑建图,我们发现如下性质

  • 每个点有且仅有一个出边
  • 无自环

实际上这个是基环树的概念,每个点有且仅有一个出边,叫做基环内向树;如果每个点有且仅有一个入边,叫做基环外向树

不过管他什么图论模型,用到的算法基本上就是搜索、拓扑排序、最短路和动态规划

分析一下,能够上桌的只有两种情况

  • 首尾相连的环
  • 局部有一个二元环,环的两边分别拉下去一条链

我们可以用拓扑排序做一个图挖掘,最终子图上只会剩下环

1 -- 2 -- 3     5 -- 6
 \       /
  \     /       7 --- 8
   \   /         \   /
     4             9

在拓扑排序的过程中,我们可以依据拓扑序做动态规划,计算到每个员工最大的依赖数,这样统计第二种情况答案的时候直接用最长链的长度相加即可

时间空间复杂度均为\mathcal{O}(n)

// cpp
class Solution {
public:
    int maximumInvitations(vector<int>& f) {
        int n = static_cast<int>(f.size());
        vector<int> dp(n);
        vector<int> ind(n);
        for (int i = 0; i < n; ++i) {
            ind[f[i]]++;
        }
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            if (!ind[i]) q.push(i);
        }
        while (!q.empty()) {
            int temp = q.front(); q.pop();
            int to = f[temp];
            dp[to] = max(dp[to], dp[temp] + 1);
            ind[to]--;
            if (!ind[to]) q.push(to);
        }
        int ans1 = 0, ans2 = 0;
        vector<bool> vis(n);
        for (int i = 0; i < n; ++i) {
            if (!ind[i] || vis[i]) continue;
            if (f[f[i]] == i) {
                vis[f[i]] = true, vis[i] = true;
                ans1 += dp[f[i]] + dp[i];
            }
            else {
                int cnt = 1;
                for (int j = f[i]; j != i; j = f[j]) {
                    vis[j] = true;
                    cnt++;
                }
                ans2 = max(ans2, cnt);
            }
        }
        return max(ans1, ans2);
    }
};
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2022-01-03,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 5967. 检查是否所有 A 都在 B 之前
    • 题解
    • 5968. 银行中的激光束数量
      • 题解
      • 5969. 摧毁小行星
        • 题解
        • 5970. 参加会议的最多员工数
        相关产品与服务
        图数据库 KonisGraph
        图数据库 KonisGraph(TencentDB for KonisGraph)是一种云端图数据库服务,基于腾讯在海量图数据上的实践经验,提供一站式海量图数据存储、管理、实时查询、计算、可视化分析能力;KonisGraph 支持属性图模型和 TinkerPop Gremlin 查询语言,能够帮助用户快速完成对图数据的建模、查询和可视化分析。
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档