type
status
date
slug
summary
tags
category
icon
password
Property
Mar 4, 2023 02:38 AM
这次后两题都没做出来
这次其实每道题都有思路，但是因为没有刻意的训练过这方面的题目，导致在代码实现的时候一头雾水
这次倒着来分析：
第四题
提示：
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
暴力枚举即可，这里复习一下有关于质数的内容
第一题
记住字符串去重过程：
总结
- 认真看题，认真看题！！！！！！
- 复习之前见过的模板
- 哈希函数的使用
- 多见题