明年本科毕业刷题贴

433. Minimum Genetic Mutation (M) BFS 解题套路，利用queue 进行循环，创建HashSet记住已访问节点，以免重新多次访问Infinite loop。 对加入queue条件进行判断

815. Bus Routes (Hard) BFS

补充内容 (2022-10-26 08:16 +8:00):
BFS注意问题就是避免访问重复节点

补充内容 (2022-10-26 09:08 +8:00):
863. All Nodes Distance K in Binary Tree (M) 不看解答写出了build graph+ BFS解法，但是时间有点慢。由于题目给出了target node。 第二种解法可以先计算从 root到target node的dis，然后再找出对应target node 上面距离为k的节点和以target展开的距离为k的子节点

1128. Number of Equivalent Domino Pairs

补充内容 (2022-10-29 07:58 +8:00):
1129. Shortest Path with Alternating Colors

复习了点Tree

684(medium)
685(hard)
两个都是用union find解决，找cycle。 第二题用于是direct graph，需要解决common parent的问题，找到对应的common parent后存下来，然后第二次unionfind时不连其中一个边，来判断是哪一个union构成cycle。总体难度不难，主要是第二题的思路有些不一样

补充内容 (2022-10-31 04:52 +8:00):
1319(M) 不看答案自己写出来，用的同样是UnionFind。 最后loop一遍找不同的parent个数

总结一下：

目前码量122 vs 81（18天前）刷了41。中间midterm week荒废了几天。坚持就是胜利。刷多了最近感觉解题比上课有意思多了。

补充内容 (2022-10-31 07:49 +8:00):
743(M) Djikstra

787. Cheapest Flights Within K Stops （M）Bellman Ford。
这题比最短路径题多了限制 k stop以内。 可以用Dji，不过对应要用matrix存储答案。
Bellman ford只需要array size of n。 模版很简单 外层用 for loop 跑 k次，里面判断每个节点是否可以用k步到达，更新所有k步的答案，每走一步更新对应的 ans。模版相对简单，不需要重新建图

882. Reachable Nodes In Subdivided Graph (H)
924. Minimize Malware Spread (H)

Floyd Warshall ( For Small graph) O(v^3)

模版code