leetcode 第 274 场算法比赛

零、背景

这次比赛最后一题有点意思，你是怎么做的呢？

一、检查是否所有 A 都在 B 之前

题意：检查字符串中，是否所有 a 都在 b 之前。

基本思路：遇到 b 后打一个标记状态，再遇到 a 就不满足题意了。

扩展思路：字符串排序，判断与输入的串是否相等。

二、银行中的激光束数量

题意：给一个方阵，某些位置摆放的有激光。
如果两行之间的行都没有激光，则这两行的激光可以上下连接。
问有多少个激光连接。

思路：保存上一个存在激光的行中有多少个激光，再次遇到有激光的行了，计算即可。

三、摧毁小行星

题意：有一个初始质量的大行星，还有一堆小行星。
如果两个行星相撞，大行星会吸收小行星的质量（包括相等）。
问初始行星是否可以以某个顺序把所有小行星吸收掉。

思路：小行星排序，循环判断吸收即可。

四、参加会议的最多员工数

题意：有 n 个员工计划参加圆形桌子的会议。
某个员工参加会议的前提是他喜欢的员工也参加会议，并且坐在他旁边。

现在属于每个员工喜欢的一个其他员工，问最多可以有多少员工参加会议。

思路：答案分两种情况。

第一种是喜欢的员工形成了环，这个环里的员工都参加，就可以满足要求。

第二种是存在互相喜欢对方的员工，这样有第三者的时候，跟着参加就行了。
此时这群人不需要是环，是链就行了。
也因此，多个链都参加，依旧可以满足要求。

两种情况分别如下图。

具体实现的时候，对于第一种情况，一个递归就可以求出最大环。

为了寻找环以及环上的所有员工，我使用 stack 与 set 数据结构来计算。

stack 使用 vector 实现的原因是，发现环之后，需要找到环上的所有节点。

vector<int> stack;
vector<int> hash;
void Dfs(int now){
    stack.push_back(now);
    hash[now] = 1;

    int pre = nums[now];
    if(hash[pre] == 1) { // 形成一个环，递归结束
        maxLoop = max(maxLoop, loopSize); // 第一种答案
    }

    stack.pop_back();
    hash[now] = 0;
}

而对于第二种情况，需要特殊判断，分别统计两个互相喜欢对方员工的尾巴最长是多少。 最后将所有第二种情况的链相加即可。

对于尾巴的合并，当然还有并查集了。
由于还需要计算自己处于哪条链上，还需要维护一个真实的环上父节点以及尾巴长度。

struct Node{
    int flag;    // 是否计算过
    int inLoop;  // 是否在环上
    int pre;     // 并查集，环的唯一标示，选择最小值
    int rank;    // 并查集，尾巴+环的大小
    int realPre; // 真实的环上父节点
    int extNum;  //  环上节点，自己的真实尾巴长度
}

这样，就可以计算出一个亲密环的答案来了。

if(nodes[node.pre].rank == 2) {
    Node& left = nodes[node.realPre];
    Node& right = nodes[nums[node.realPre]];
    ans[node.pre] = max(ans[node.pre], left.extNum + right.extNum - left.rank);
}

复杂度：O(n)

五、最后

这次比赛前三题都是简单题，几分钟做完了。
最后一题有点意思，你是怎么做的呢？

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code