leetcode274周赛

竞赛链接

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

---

思路

遍历数组，判断字符b之后是否还有a出现

Code

class Solution {
public:
    bool checkString(string s) {
        int a=0,b=0;
        for(auto& i:s){
            if(i=='b')
                b++;
            if(i=='a'&&b!=0)
                return false;
        }
        return true;
    }
};

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

T2: 5968. 银行中的激光束数量

---

思路

逐行遍历，过程中维护上一个非空行中的设备数量。

Code

class Solution {
public:
    int numberOfBeams(vector<string>& bank) {
        int n=bank.size(),a=0;
        vector<int>ha(n,0);
        for(auto& i:bank){
            int cnt=0;
            for(auto& j:i){
                if(j=='1')
                    cnt++;
            }
            ha[a]=cnt;
            a++;
        }
        long long num=0,fa=-1;

        for(int i=0;i<n;++i){
            if(ha[i]==0)
                continue;
            if(fa==-1)
                fa=ha[i];
            else{
                num+=fa*ha[i];
                fa=ha[i];
            }
        }
        return num;
    }
};

复杂度分析

• 时间复杂度：O(nm)
• 空间复杂度：O(1)

T3: 5969. 摧毁小行星

---

思路

显然应该从小到大摧毁小行星。排序后逐个检查即可(记得开long long

Code

class Solution {
public:
    bool asteroidsDestroyed(int mass, vector<int>& a) {
        sort(a.begin(),a.end());
        long long num=mass;
        for(auto& i:a){
            if(num>=i)
                num+=i;
            else
                return false;
        }
        return true;
    }
};

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)

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

---

思路

1.正向建图g，然后拓扑排序(为了方便后面找基环
2.反向建图rg，从基环大小为2延伸出去的树枝上最深的链

下面介绍基环树问题的通用写法。

我们可以通过一次拓扑排序「剪掉」所有树枝，这样就可以将基环和树枝分开，从而简化后续处理流程：

• 如果要遍历基环，可以从入度不为 0 的节点出发，在图上搜索；
• 如果要遍历树枝，可以以基环与树枝的连接处为起点，顺着反图来搜索树枝，从而将问题转化成一个树形问题。

对于本题，我们可以遍历所有基环，并按基环大小分类计算：

• 对于大小大于 2 的基环，我们取基环大小的最大值；
• 对于大小等于 2 的基环，我们可以从基环上的点出发，在反图上找到最大的树枝节点深度。

Code

class Solution {
public:
    int maximumInvitations(vector<int> &favorite) {
        int n = favorite.size();
        vector<vector<int>> g(n), rg(n); // rg 为图 g 的反图
        vector<int> deg(n); // 图 g 上每个节点的入度
        for (int v = 0; v < n; ++v) {
            int w = favorite[v];
            g[v].emplace_back(w);
            rg[w].emplace_back(v);
            ++deg[w];
        }

        // 拓扑排序，剪掉图 g 上的所有树枝
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (deg[i] == 0) {
                q.emplace(i);
            }
        }
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int w : g[v]) {
                if (--deg[w] == 0) {
                    q.emplace(w);
                }
            }
        }

        // 寻找图 g 上的基环
        vector<int> ring;
        vector<int> vis(n);
        function<void(int)> dfs = [&](int v) {
            vis[v] = true;
            ring.emplace_back(v);
            for (int w: g[v]) {
                if (!vis[w]) {
                    dfs(w);
                }
            }
        };

        // 通过反图 rg 寻找树枝上最深的链
        int max_depth = 0;
        function<void(int, int, int)> rdfs = [&](int v, int fa, int depth) {
            max_depth = max(max_depth, depth);
            for (int w: rg[v]) {
                if (w != fa) {
                    rdfs(w, v, depth + 1);
                }
            }
        };

        int max_ring_size = 0, sum_list_size = 0,maxx_list=2;
        for (int i = 0; i < n; ++i) {
            if (!vis[i] && deg[i]) { // 遍历基环上的点（拓扑排序后入度不为 0）
                ring.resize(0);
                dfs(i);
                int sz = ring.size();
                if (sz == 2) { // 基环大小为 2
                    int v = ring[0], w = ring[1];
                    max_depth = 0;
                    rdfs(v, w, 1);
                    sum_list_size += max_depth; // 累加 v 这一侧的最长链的长度
                    max_depth = 0;
                    rdfs(w, v, 1);
                    sum_list_size += max_depth; // 累加 w 这一侧的最长链的长度

                    maxx_list=max(sum_list_size,maxx_list);
                } else {
                    max_ring_size = max(max_ring_size, sz); // 取所有基环的最大值
                }
            }
        }
        return max(max_ring_size, maxx_list);
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

个人总结

---

本周题目难度跨度较大，前三题纯纯白给，t3没看数据范围wa了一发(我太蠢了)，来到t4后，紧接着就是漫长的罚坐时间了，对于找环问题不太熟悉，外加拓扑排序需要加强，已经忘得差不多了唔..