leetcode 第 345 场算法比赛

零、背景

这次比赛题目比较简单，排名几百名之外了。

一、找出转圈游戏输家

题意：n 个人坐成一圈，从第一个人开始传球。
第一次传给后面的第 k 个人。
第二次传给后面的第 2k 个人。
第 p 次传给后面的低 pk 个人。
当某个人第二次拿到球时游戏结束。
问哪些人从来没摸到过球。

思路：按题意模拟即可。

二、相邻值的按位异或

题意：有一个原始数组，每个位置通过与后面一个位置的值异或，得到一个加密数组。
注：最后一个位置与第一个位置的值异或。
现在给你一个加密数组，问是否可以得到合法的原始数组。

思路：枚举第一个位置的值，按顺序解密，判断是否可以得到无冲突的原始数组即可。

三、矩阵中移动的最大次数

题意：给一个矩阵，可以按条件从第一列开始向右走，问可以走的最大步数。
条件1：可以向右上、右、右下三个位置走。
条件2：下个位置的值需要大于当前位置的值，才能走。

思路：动态规划。

一列列的计算当前列哪些位置可以到达。

首先：第一列都可以到达。
对于下一列的某个位置，上一列三个位置只要有一个可以到达，就算可以到达。

答案是可以到达的最大列数。

四、统计完全连通分量的数量

题意：给一个无向图，问有几个完全连通分量。
连通分量：一个子图，图中的所有顶点之间存在路径，且与图外的顶点没有边。
完全连通分量：子图中，任何两个顶点之间都有边。

思路：

1）遍历边，通过并查集合并连通分量的顶点。
2）通过顶点，通过并查集计算每个连通分量的顶点个数（第一步也可以一起计算）。
3）遍历边，计算并查集计算每个连通分量的边个数（第一步也可以一起计算）。
4）遍历顶点，对于是并查集根节点的顶点，根据顶点个数与边的个数，判断是不是完全图。

五、最后

题目比较简单，没啥说的。

《完》

-EOF-

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