leetcode 第 324 场算法比赛

零、背景

这次比赛的时候，还在医院，所以就依旧没参加比赛。

之后的一周，前几天是出院等各种个人事情，后面几天是我确认感染新冠病毒，一直没来得及做比赛的题。
如今周六了，病情也好的差不多了，才有时间补一下题解。

最近一周落下的还有每日一题。

2022-12-19日：连通判断，并查集或者DFS。
2022-12-20日：最大值最小问题，经典题，二分答案即可。
2022-12-21日：博弈题，贪心选最大两堆，或者三角形原理直接计算答案。
2022-12-22日：经典题，动态规划之状态压缩。
2022-12-24日：后缀字符串比较，可暴力计算，也可套后缀数组模板。

一、统计相似字符串对的数目

题意：给一些字符串，问字符集合相同的字符串对有多少个？

思路：使用状态压缩来表示一个字符集合，用 hash 表统计个数，最后分别 C(n,2)即可。

二、使用质因数之和替换后可以取到的最小值

题意：给一个数字，质因数之和可以转化为另外一个数字，问可以得到的最小值。

思路：模拟题。
质数的答案是自己，4比较特殊答案也是自己，其他数字的转化都是指数级别降低的。
预先计算数据范围之内的素数表，然后模拟转化即可。

三、添加边使所有节点度数都为偶数

题意：给一个图，至多添加两条边（非重边或自环），问是否可以使得所有顶点的度数是偶数。

思路：
hash所有的边，统计度数为奇数的顶点个数。
对于个数分情况讨论。

情况1：0个顶点，满足要求。

情况2：2个顶点，且两个顶点之间没有边。
那加一条边即可满足要求。

如果两个顶点之间有边，那么需要找到一个中转点，这个中转点到这两个奇度点都没有边。
可以找到，那就添加两条边，即可满足要求。
否则没有答案。

情况3：4个顶点。
此时如果4个顶点能够划分为两组，且两组内部没有边，则存在答案。
否则没有答案。

情况4：更多的顶点，没有答案。

思考题：如果没有边限制，那是否存在答案？或者存在答案时，至少需要多少条边？

四、查询树中环的长度

题意：给一个自然数堆排序对应的完全二叉树，现在给两个点，求着两个点的路径长度。

思路：树满足父节点是子节点的一半，上一层的节点值全部小于下一层的节点值，所以可以通过值大小比较层数，从而求出答案。
复杂度：log(n)

五、最后

下次比赛应该可以正常参加了。

加油，算法人。

《完》

-EOF-

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