周赛小结：leetcode第324场周赛

type

status

date

slug

summary

第四题

提示：

2 <= n <= 30

m == queries.length

1 <= m <= 105

queries[i].length == 2

1 <= ai, bi <= 2n - 1

ai != bi

这道题可以说算是模板题了，在做的时候是有思路的，也知道实际上就是求公共祖先

这样一道模板题，大概在暑假的时候看y总直播有写过这类题（在这里不知道该夸自己记性好还是不好。。）

看了一眼第一名做的题，瞬间就想起来了。。当时根本就没有整理

第三题

提示：

3 <= n <= 105

2 <= edges.length <= 105

edges[i].length == 2

1 <= ai, bi <= n

ai != bi

图中不会有重边

做题的时候想的是染色体二分问题，因为没有看到“最多加两条边的条件”！

加上这个条件以后，这个题目就变成了分类讨论的问题！

图论，分类讨论)O(n+m)O(n+m)

从图论常识中得知，奇度数点的个数一定是偶数。

如果原图奇度数的点的个数为 0，则直接返回成功。

如果原图奇度数的点的个数大于 4 个，则直接返回失败，因为两条边肯定无法全部将其修改为偶度数。

如果原图奇度数的点的个数为 2，则以下两种情况需要满足一种：

如果奇度数的两个点之间没有边，则直接在其之间加一条边解决。

如果奇度数的两个点之间已经存在了一条边，则寻找另外一个点，满足与这两个点之间都不存在边。

如果原图奇度数的点的个数为 44，设为 x0,x1,x2,x3x0,x1,x2,x3，则以下三种情况需要满足一种：

(x0,x1)(x0,x1) 与 (x2,x3)(x2,x3) 之间都不存在边。
(x0,x2)(x0,x2) 与 (x1,x3)(x1,x3) 之间都不存在边。
(x0,x3)(x0,x3) 与 (x1,x2)(x1,x2) 之间都不存在边。

时间复杂度遍历图一遍，故时间复杂度为 O(n+m)O(n+m)。空间复杂度需要 O(n+m)O(n+m) 的额外空间存储图和度数数组。

技巧：

next_permutation 的使用

手写哈希函数

图论的分类讨论思路

第二题

简单的模拟题

提示：

2 <= n <= 105

暴力枚举即可，这里复习一下有关于质数的内容

第一题

记住字符串去重过程：

总结

认真看题，认真看题！！！！！！

复习之前见过的模板

哈希函数的使用

多见题

第四题

第三题

图论，分类讨论)O(n+m)O(n+m)

技巧：

第二题

第一题

总结

GJJ