本文主要是介绍BFS 到 Level Order traverse 到 UnionFind 到 Topological Sort 到 Dijkstra 思路总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
====BFS 找联通量,找component.
Number of Islands (BFS, DFS 都可以做)
Surrounded Regions 算法是:先收集四个周边的 O,然后用BFS或者DFS向里面扩展,visited记录connect点,最后如果没有被visited到的O,会变成X;T: O(m*n), Space: O(m*n).
Is Graph Bipartite (用两个color来表示,1 -1, 同时注意可能有多个component,那么必须以for循环来判断每个点,for里面做BFS来标记颜色,这样就相当于用了visite hashset,所以这里就避免了用hashset来判断重复选点)
Clone Graph (BFS, DFS都可以做)
Reconstruction itinerary (DFS + PriorityQueue 来生成path)
====Union Find 找联通量是最合适的方法:对于动态加入的时候,尤其有效果;
Number of Connected Components in an Undirected Graph (BFS, DFS, Union Find 都可以做)
Graph Valid Tree (BFS, Union Find 都可以做) BFS做的时候,一定要判断edge == nodes - 1, 收集到的node数量是n;
Union Find 题型总结
=====Level Order minimum distance 都会用到层级关系;
int size = queue.size(); for(int i = 0; i < size; i++);
Binary Tree Level Order Traversal
Binary Tree Level Order Traversal II
Binary Tree Zigzag Level Order Traversal
Binary Tree Vertical Order Traversal (用两个queue,一个收集node,一个收集col的index,min max收集最小col和最大col);
Binary Tree Right Side View (收集level的最后一个元素即可)
Find Largest Value in Each Tree Row
Shortest Path in a Grid with Obstacles Elimination (一层一层的走,走到最右下角,就是step数最小的, visited需要表示三维的,因为到x,y我可以以好几种方式到达,也就是不remove 1,和remove多个1之后到达,虽然坐标一样,但是状态是不一样的;)
The Maze (球选择一个方向,然后一直走到头,中间的0,不代表能够到达,只有最后一个node才算到达;走的过程就是一个while循环,一直走,技巧就是while(isvalid(maz, nx + dx[k], ny + dy[k]) 这里注意一点就是走的过程中并不需要判断是否visited过,while循环判断下一个点是否合法,不合法跳出循环,但是当前的点是合法的。走到碰墙了,才判断是否visited过。)
N-ary 题目归类总结
==== Tree Traverse, (preorder, Inorder, postorder) 总结
Serialize and Deserialize BST (用queue来做,O(n); 就是传参的时候用Integer.MIN_VALUE 和Integer.MAX_VALUE来作为下限和上限;只serialize有value的node,不管null node;这样如果value不在lower, upper范围之内,那么就是return null;)
Serialize and Deserialize Binary Tree (用preorder traverse,current,left, right来serialize,然后用queue来deserilize,这题跟BST不同的是,这里需要serilize NULL,因为BST有大小关系,这里没有,所以需要满树才行;而且这里就不需要Integer.MAX_VALUE和Integer.MIN_VALUE作为参数来判断是否return null了,这个复杂度是O(N);)
====== minimum distance ====== 层级关系;
int size = queue.size(); for(int i = 0; i < size; i++);
Walls and Gates
Rotting Oranges 注意到空层的时候,step也加1了,最后return的时候需要减去1;
Word Ladder (BFS, 注意分层,还有刚开始不需要加入beginWord, endWord到dict中,相信自己的思维)
Word Ladder II, 求word ladder I 的所有路径;
Remove Invalid Parentheses (这题正确的解法还是收集invalid 左括号和右括号的数量,然后只去remove左括号和右括号的数量的)
Perfect Squares (这题可以BFS, DP两种做法) BFS就是减去j * j <= n的数,然后层级收集下一层的数,如果到0了,return step即可。DP 很像 coin change.
All Nodes Distance K in Binary Tree (先把tree转换成graph,注意parent也是neighbor,然后在图上面做BFS);
=====Topological Sort 总结=====
Course Schedule (标准 Topological 的写法);
Course Schedule II (跟上面一样,只是记录topo的顺序到结果即可)
Course Schedule III (属于Greedy, 参考 Greedy 总结)
Minimum Height Trees (topo排序,一层一层的扒掉最外面的一层的node,返回最里面一层的node,注意n == 1,return list of {0};)
题目类似的还有个叫Minimum Spanning Tree, minimum cost to connect city; 做法是首先按照cost sort connection,然后用Union Find判断两个city是否相连,因为每次都是用最小的cost,所以最后结果就是最小的总cost;
Alien Dictionary 思路,就是拓扑排序,从单词之间的关系来得到图的关系,然后用hashmap来建立图。注意分函数写程序,这样清晰,而且容易debug;注意indegree需要把每个node全部赋值为0;然后再进行+1;注意所有的char都是一个node,都是字母;
这题有个特列:abc, ab, return ""; 就是前面的相等,return "";
Longest Increasing Path in a Matrix 用topo排序来做,也就是 node 指向比自己小的点,那么小的点indegree就加1,那么刚开始就是从最大的点开始走,indegree是0,那么所有的最大的点同时开始走,也就是层级的关系,那么最长的steps就是最长的length;T: O(M*N), space: O(M*N); 这题虽然归类到topo排序,但是记忆化搜索更简单易懂;
Topological sort 总结
====Dijkstra 算法总结=====
Pacific Atlantic Water Flow 思路:用两个boolean矩阵来表示,水往里面走,往高的地势走,看能流向哪里,这样可以减少计算;同时最后两个矩阵重合的地方,就是overlap point which can flow to both side;
Cheapest Flights Within K Stops 思路:核心思想就是,每次走最小的cost的路径,那么到达des的时候,就是最小的cost,那么我们需要做的是把边cost的信息,融入到node里面去,那么node进行排序,也就是cost进行排序;graph怎么建立,graph: HashMap<Integer, HashMap<Integer, Integer>> 存 from , <neighbor, cost>将边的信息(cost信息),整合到node里面去,也就是到达这个city需要的cost是多少,然后剩下的步骤是多少,cost是累加的,剩下的步骤是减少的。pq: 存Node Node<cost, city, step> sort by cost; 搜索:if( step > 0) 继续,if city = dst 表示找到,直接返回当前cost;Time: O(V + ElogE) Space: O(E)
Trapping Rain Water II 思路:一个格子能够盛水的高度,取决于这个格子四个方向能够传进来吃水线的最小值;用priorityqueue,最外围的格子是不能装水的,然后从最小的吃水线往里面渗透,因为每次都是以最小的吃水线往里面传递,那么保证了每次算出来的吃水线-height都是合法的盛水的高度;n*m*log(n*m)
这篇关于BFS 到 Level Order traverse 到 UnionFind 到 Topological Sort 到 Dijkstra 思路总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!