胖头龙的咸鱼刷题笔记-算法篇

不要鸽好吗

求不鸽+1 555

"并且同学们大多都是二十多岁的中老年人"..........WHO不是40才算中年。。。

感谢楼主 先插个眼

难得的常看常新的帖子

Colley 发表于 2020-11-01 20:36:38
谢谢楼主，楼主用什么软件来记笔记的跟刷题表的呢？

同问，楼主用的是什么软件记笔记呢？

蹲不到更新了555

第七章 宽度优先搜索



基本问题：
（1）如果复杂程度类似， 面试中尽量优先使用BFS
（2）BFS主要几种场景： 层级遍历，拓扑排序，图上搜索（包括二叉树，矩阵）
（3）Queue的使用技巧，BFS的终止条件？
（4）什么时候使用分层？什么时候不需要？实现的时候的区别在哪里？
（5）拓扑排序的概念？如何判断是否存在拓扑排序？是否存在唯一的拓扑排序？找到所有拓扑排序？
（6）什么时候需要使用set记录访问过的节点？（为什么二叉树上的BFS往往不需要set？）什么时候需要map记录到达过的节点距离？
（7）如何在矩阵中遍历下一步的所有节点？如果每次可能走不止一步怎么办（Maze II）？
（8）为什么BFS解决的基本都是简单图（边长为1）问题？如果边长不为1，该怎么办？
（9）BFS的时空复杂度估算？
（10）如何使用双向BFS进行优化？



BFS题目列表：
（必背：紫色；核心：蓝色；重点：绿色；普通：黄色；默认是LeetCode，如果是LintCode会以Lint开头）


二叉树:

297. Serialize and Deserialize Binary Tree
https://leetcode.com/problems/se ... ialize-binary-tree/

102. Binary Tree Level Order Traversal
https://leetcode.com/problems/binary-tree-level-order-traversal/

103. Binary Tree Zigzag Level Order Traversal
https://leetcode.com/problems/bi ... el-order-traversal/

107. Binary Tree Level Order Traversal II
https://leetcode.com/problems/bi ... order-traversal-ii/

513. Find Bottom Left Tree Value
https://leetcode.com/problems/find-bottom-left-tree-value/

Lint-242. Convert Binary Tree to Linked Lists by Depth
https://www.lintcode.com/problem ... y-depth/description



拓扑排序:

Lint-127. Topological Sorting
https://www.lintcode.com/problem/topological-sorting/description

207. Course Schedule
https://leetcode.com/problems/course-schedule/

210. Course Schedule II
https://leetcode.com/problems/course-schedule-ii/

269. Alien Dictionary
https://leetcode.com/problems/alien-dictionary/

444. Sequence Reconstruction
https://leetcode.com/problems/sequence-reconstruction/



矩阵:

200. Number of Islands
https://leetcode.com/problems/number-of-islands/

490. The Maze
https://leetcode.com/problems/the-maze/

505. The Maze II
https://leetcode.com/problems/the-maze-ii/

542. 01 Matrix
https://leetcode.com/problems/01-matrix/

733. Flood Fill
https://leetcode.com/problems/flood-fill/

994. Rotting Oranges
https://leetcode.com/problems/rotting-oranges/

305. Number of Islands II
https://leetcode.com/problems/number-of-islands-ii/

773. Sliding Puzzle
https://leetcode.com/problems/sliding-puzzle/

Lint-573. Build Post Office II
https://www.lintcode.com/problem/build-post-office-ii/description

Lint-598. Zombie in Matrix
https://www.lintcode.com/problem/zombie-in-matrix/description

Lint-611. Knight Shortest Path
https://www.lintcode.com/problem/knight-shortest-path/description

Lint-794. Sliding Puzzle II
https://www.lintcode.com/problem/sliding-puzzle-ii/description



图:

133. Clone Graph
https://leetcode.com/problems/clone-graph/

127. Word Ladder
https://leetcode.com/problems/word-ladder/

261. Graph Valid Tree
https://leetcode.com/problems/graph-valid-tree/

841. Keys and Rooms
https://leetcode.com/problems/keys-and-rooms/

323. Number of Connected Components in an Undirected Graph
https://leetcode.com/problems/nu ... n-undirected-graph/

1306. Jump Game III
https://leetcode.com/problems/jump-game-iii/

Lint-531. Six Degree
https://www.lintcode.com/problem/six-degrees/description

Lint-618. Search Graph Nodes
https://www.lintcode.com/problem/search-graph-nodes/description

Lint-624. Remove Substrings
https://www.lintcode.com/problem/remove-substrings/description

6666强强

居然更新了！