- 宽度优先搜索：能够用BFS解决的问题都不要用DFS！！！
- BFS写的目的：不用递归，用循环实现！！！
- 常见的BFS用来解决什么问题？(1) 简单图（有向无向皆可）的最短路径长度，注意是长度而不是具体的路径（2）拓扑排序 （3） 遍历一个图（或者树）
- 数据结构：使用队列作为主要的数据结构 Queue（先进先出）
1、如果不需要确定当前遍历到了哪一层，BFS 模板如下。
while queue 不空：
cur = queue.pop()
for 节点 in cur的所有相邻节点：
if 该节点有效且未访问过：
queue.push(该节点)2、如果要确定当前遍历到了哪一层，BFS 模板如下。 这里增加了 level 表示当前遍历到二叉树中的哪一层了，也可以理解为在一个图中，现在已经走了多少步了。size 表示在当前遍历层有多少个元素，也就是队列中的元素数，我们把这些元素一次性遍历完，即把当前层的所有元素都向外走了一步。
level = 0
while queue 不空：
size = queue.size()
while (size --) {
cur = queue.pop()
for 节点 in cur的所有相邻节点：
if 该节点有效且未被访问过：
queue.push(该节点)
}
level ++;不需要专门一个set来记录访问过的节点
- 0102.Binary Tree Level Order Traversal (!!M, youtubed)
BFS的铁律就是用queue, 在while q: 循环里做两件事 1. 处理这一层。那就需要把这一层的node逐个pop出，然后append到res里，有时候需要用for循环for _ in range(len(q))来遍历这一层所有的node; 2. append下一层进q。BFS is O(N) since each node is processed exactly once. - 0103.Binary_Tree_Zigzag_Level_Order_Traversal (!M)
same as 102, 在res.append(level)的时候间隔性选择res.append(level) or res.append(level[::-1]).level[::-1]是从后往前输出array. - 0314.Binary_Tree_Vertical_Order_Traversal.py (!M)
record the position of each node as we dfs to traverse the tree. 记录在遍历过程中记录node位置的思想非常重要！
TODO 297
- 0107.Binary Tree Level Order Traversal II(E)
same as 102，只是题目要求从下至上输出，只需要return res[::-1]即可. - 0199.Binary_Tree_Right_Side_View (M)
same as 102, just need record most right node. - 0637.Average_of_Levels_in_Binary_Tree.py (M)
level order traversal using a q. - 0515.Find_Largest_Value_in_Each_Tree_Row (M)
solution: 返回每一层的最大值的集合. - 0242.Convert Binary Tree to Linked Lists by Depth (LintCode) 将二叉树转换成层序遍历的linked list，然后输出.
- 0513.Find_Bottom_Left_Tree_Value (M)
首先想到的是要求bottom的node, 所以用bfs渠道最下面一层，然后要求left_most, 所以我们可以在bfs append下一层的时候先append right, then append left, 这样最后一个node就是botoom left node了. - 1161.Maximum_Level_Sum_of_a_Binary_Tree (M)
solution: 返回最大的level，这个level上的最大sum. - 0111.Minimum_Depth_of_Binary_Tree (!!!E)
solution 1: recursion; soluiton 2: BFS; for _ in range(lens): if not node.left and not node.right: return depth. - 0662.Maximum_Width_of_Binary_Tree.py (M)
涉及到处理level的信息，就用bfs, q里面存放(node, the postion of the node), 注意这里的pos到下一层的转换关系: q.append((node.left, 2* pos)). - 0987.Vertical_Order_Traversal_of_a_Binary_Tree.py (H)
same as 314. in 314, left nodes output first, in 987, smaller value comes first. So the only difference is at sort
TODO: 116-117-104都是层序遍历
- 0997.Find_the_Town_Judge.py (!!E)
one dict to store the inDegree (beingTrusted), one dict to store the outDegree (trustOthers). there exsit a town judge only if there is a node with inDegree==N-1(beiing trusted by all others), and at the same time the node should have outDegree==0(not trust anyone) - 0277.Find_the_Celebrity.py (!!M)
main algorithm: each comparing kowns(i, j), we are sure either i is definitely not a celebrity (knows(i, j)=True), or j is definitely not a celebrity (knows(i, j)=False). step 1: one pass, find a candidate by making sure other people are not candidates; step 2: one pass, double check the candidate selected in step 1 is indeed a celebrity - 1267.Count_Servers_that_Communicate.py (!!M)
找计算机每一行每一列只有一个的，就是我们要找的计算机 - 0531.Lonely_Pixel_I.py (!!M)
same as the above problem. one pass to store number of "B" in col_cnt and row_cnt; another pass to find the isolated pixels
区别：图上的宽搜 BFS in Graph，和树上有什么区别？图中存在环，存在环意味着，同一个节点可能重复进入队列，所以HashMap很好用 <br>
图的几种表示方式：
数组： [head][tail] 长度是边数
链表： Map<Integer, Set<Integer>> graph <br>
- 0261.Graph Valid Tree (!!!M)
判断图是不是树？
- 1.边树刚好等于n-1，点数和边数差1
- 2.n-1条边一定要把整个图连起来，判断连通性，就是通过一个点把其他的点都能找到
实现方法：1.BFS 2.DFS非递归 3.DFS递归
- 0133.Clone Graph (!!!M)
方法一：BFS step1:先BFS找到所有的node step2:复制新的node放入mapping step3:复制边
方法二：DFS 用一个mapping 保存node-->node_copy. 然后一边dfs一边新建copied nodes
TODO:问一下 - 0618.Search Graph Nodes (LintCode) 图的遍历(由点及面)
找所有最近的value=target的点?最近用BFS,直接遍历，第一个找到的就是最近。
图 Graph
N个点，M条边
M最大是 O(N^2) 的级别 图上BFS时间复杂度 = O(M) 所以最坏情况可能是 O(N^2)
矩阵 Matrix
N行M列
N*M个点，N*M*2 条边(每个点上下左右4条边，每条边被2个点共享)。 矩阵中BFS时间复杂度 = O(N * M)
layer = -1 or 0 什么时候用-1，什么时候用0
1. 当next_i, next_j要用layer去更新的时候就要用 layer = 0 当前的layer代表当时next所在的层数, 最后不用return layer， 或者return layer - 1
2. 当next_i, next_j不用layer更新的时用layer = -1 当前的layer代表当时curr所在的层数, 最后return layer
- 0200.Number_of_Islands (!!M)
Linear scan the 2d grid map, if a node contains a '1', then it is a root node that triggers a Breadth First Search. Solution 2: dynamic connection problem, Union Find. Follow up: 如何找到这些岛屿有多少种不同的形状，union find就做不了了，只能dfs. - 0598.Zombie in Matrix (!!LintCode)
- 0994.Rotting_Oranges (M)
Step 1. append the rotten ones to the first level, Step 2: 层序遍历的bfs to turn the adjacent fresh ones into rotten ones. 必须层序遍历才能保证最少时间make all fresh ones rotten 在class solution(): 后面定义全局变量 EMPTY = 0; FRESH = 1; MOVES = [(1, 0), (-1, 0), (0, 1), (0, -1)]. - 0286.Walls_and_Gates (M)
求最小距离问题，必须用bfs. Step 1: append all the gates into the queue; Step 2: change all the EMPTY rooms to a value that equals the layer number, 必须层序遍历才可以保证每次都能变成最小距离. - 1730.Shortest_Path_to_Get_Food.py (M)
Simple BFS will do it. - 1162.As_Far_from_Land_as_Possible (!!M)
Solution:从地找水，最晚找到的就是水距离最近的陆地的最大值.bfs: the maximum distance is steps needed to change all WATER to be LAND, so we append all land into the first layer of q, and do a level order bfs. the maxumum distance is then the answer we want. solution 2: DP same as 542. 01 matrix. - 0542.01_Matrix (M)
方法是先把所有0放入q的第一层，然后一层层遍历，同时更新遇到的1为当前的层数，层数就是1离0的距离; solution 2: DP same as 542. 01 matrix.
- 0127.Word_Ladder.java (!!M)
node是某个单词，_get_next(curr_node)是这一题的难点，构造一个dictionary, key is all possible combination of the word, value is the word, 这样就可以快速查询了。Time complexity: O(NL^2), where N is the number of words in word_set, and L is avg length of words - 0433.Minimum_Genetic_Mutation.java (!!M)
same as 127. Word Ladder. 双端bfs大大提高速度 - 0752.Open_the_Lock.py (!!M Google)
题目蛮有意思的, 带层序遍历的bfs, 遇到currNode in deadends 就不再去访问其neighbor了, find neighbor 函数比较有意思，这里第一次学到了yield; - 1129.Shortest_Path_with_Alternating_Colors.py (!!M)
这一题的题眼是visiting the same node with same color is not allowed, with same color is not. 所以color信息要放到adjacency list 里，也要放到q里，还要放到visited里 - 1197.Minimum_Knight_Moves.py (!!M)
solution 1: 利用对称性质: x,y=abs(x),abs(y); q.append(neighbor) only if (-2 <= next_x <= x + 2 and -2 <= next_y <= y + 2); 1816 ms solution 2!!!: 从source和destination两端同时进行bfs!!!!注意双端bfs传进去的参数包含q and visited, bfs返回值是updated q and visited. cnt+=1的操作在主函数中进行. while true的结束条件: if visited_src & visited_des: return cnt_src + cnt_des; 452 ms solution 3: recurrsion with memorization: cache[(x, y)] = min(dp(abs(x-1), abs(y-2)), dp(abs(x-2), abs(y-1))) + 1; 60 ms - 0611.Knight Shortest Path (!!LintCode)(M)
Solution:棋盘中从start调到end，求最短路径。 - 0573.Build Post Office II (!!LintCode)(H)
Solution:枚举邮局位置:for 邮局位置 => O(SPACE),计算所有点离邮局的距离=计算邮局离所有点的距离 => O(nm).总体时间复杂度 O(SPACEnm)，最坏情况 O(n^2*m^2) - 0279.Perfect_Squares.py (!!M)
f[j]=the least number of perfect square numbers which sum to i; f[j] = min(f[j-i^2]+1) for i^2<=j; Time complexity: j is from 0 to n, i is from 0 to j^0.5, so O(N^1.5); solution 2: level order BFS. Given a N-ary tree, where each node represents a remainder of the number n subtracting a square number, our task is to find a node in the tree, which should meet the conditions or remainder=0. bfs的层数就代表了所需要perfect squares的个数. Time complexity: 比较复杂最后是 O(n^(h/2)), where h is the height of the N-ary tree, h is 0 to 4. - 0397.Integer_Replacement.py (!!M)
similar with 991. Broken Calculator (bfs). backtrack with memo - O(n)
序列化：将“内存”中结构化的数据变成“字符串”的过程 序列化:object to string 反序列化:string to object
什么时候需要序列化?
1. 将内存中的数据持久化存储时
内存中重要的数据不能只是呆在内存里，这样断电就没有了，所需需要用一种方式写入硬盘，在需要的 时候，能否再从硬盘中读出来在内存中重新创建
2. 网络传输时 机器与机器之间交换数据的时候，不可能互相去读对方的内存。只能讲数据变成字符流数据(字符串)后
通过网络传输过去。接受的一方再将字符串解析后到内存中。 常用的一些序列化手段:
• XML
• Json
• Thrift (by Facebook)
• ProtoBuf (by Google)
序列化算法：一些序列化的例子:
• 比如一个数组，里面都是整数，我们可以简单的序列化为”[1,2,3]”
• 一个整数链表，我们可以序列化为，”1->2->3”
• 一个哈希表(HashMap)，我们可以序列化为，”{\”key\”: \”value\”}”
序列化算法设计时需要考虑的因素:
• 压缩率。对于网络传输和磁盘存储而言，当然希望更节省。
• 如 Thrift, ProtoBuf 都是为了更快的传输数据和节省存储空间而设计的。
• 可读性。我们希望开发人员，能够通过序列化后的数据直接看懂原始数据是什么。
• 如 Json，LintCode 的输入数据
- 0449.Serialize and Deserialize BST (M)
Same as 297. Solution says since BST, the answer could be as compact as possible. Don't know how? 记不住
有向图的问题，可以检测有向图是否有环！必考，其实也非常模板化，一定要记住。
Three steps:
1. 从数字关系求出每个节点的inDegrees（就是找节点与相邻节点的依赖关系） (inDegrees = collections.defaultdict(int))，key是node, val是这个node的indegree值;
2. 和每个节点的neighbors （neighbors = collections.defaultdict(list)), key是node, val是装有这个node的neighbor的list;
3. 然后 BFS，背诵模板就可以了。
Three steps:
1. construct a dictoinary of adjacency list for the graph hashmap存储临接关系
2. get in_degree information for all nodes
3. topological sort - bfs
step I: initialze q by putting all in_degree = 0 into q
step II: keep adding in_degree = 0 node into q and pop out while updating res
- 0127.Topological Sorting.java (!!LintCode)
有向图的问题，可以检测有向图是否有环！必考，其实也非常模板化，一定要记住。Three steps: 1. 从数字关系求出每个节点的inDegrees（就是找节点与相邻节点的依赖关系） (inDegrees = collections.defaultdict(int))，key是node, val是这个node的indegree值; 2. 和每个节点的neighbors （neighbors = collections.defaultdict(list)), key是node, val是装有这个node的neighbor的list; 3. 然后 BFS，背诵模板就可以了。 利用双端BFS大大提高速度，注意双端bfs传进去的参数包含q and visited, bfs返回值是updated q and visited. 双端bfs是src/des每走一步判断一下if visited_src & visited_des: return step; 在双端BFS的过程中判断if not q_src or not q_des: 则说明q_src或q_des里面的所有possible neighbor都不在wordList里面，也就是没有必要继续进行了; The idea behind bidirectional search is to run two simultaneous searches: one forward from the initial state and the other backward from the destination state — hoping that the two searches meet in the middle. The motivation is that b^(d/2) + b^(d/2) is much less than b^d. b is branch number, d is depth. 这题最好定义一个wordSet = set(wordList)来降低时间寻找下一个neighborWord的复杂度到O(26L); - 0207.Course_Schedule (!!M)
套用模板分三步：1. construct a dictoinary of adjacency list for the graph; 2. get in_degree information for all nodes; 3. topological sort - bfs: step I: initialze q by putting all in_degree = 0 into q; step II: keep adding in_degree = 0 node into q and pop out while updating res - 0210.Course_Schedule_II (!!M)
套用模板 return res if len(res) == numCourses else []. Google follow up: 打印出所有可能的选课组合，感觉有点像word ladder I and II. - 1136.Parallel_Courses (M)
Solution:注意课程是从1到N - 0444.Sequence_Reconstruction.py (!!M)
这个题目要做三个判断：1. 判断seqs的拓扑排序是否存在，只需判断len(res) 是否等于len(graph) or len(inDegrees), 如果小于说明有孤立节点，如果大于说明有环，两者都不存在拓扑排序; 2. 判断是否只存在一个拓扑排序的序列, 只需要保证队列中一直最多只有1个元素, 即每一层只有一个选择: if len(q)>1: return False; 3. 最后判断这个唯一的拓扑排序res是否等于org - 0269.Alien_Dictionary.py (!!H)
只需要比较word[i]与word[i+1]中每个char，即可得到inDegree的关系以及neighbors的关系 - 0310.Minimum_Height_Trees.py (!!M)
想想如果是一个很大的图，那minimum height trees的root就应该是这个图的最中心，所以我们就去找图的最中心就可以了，采用从外围(inDegree=1的node)往中间走的方法，解法类似topological sort, 走到最后留下的顶点就是最中心的顶点，也就是距离所有外围顶点最小的顶点
---------------------------------------------------------------记不住---------------------------------------------------------------------------------
无权图最短路径：BFS, DFS
有权有向图最短路径：
Dijkstra's:不包含负权边 (Greedy)
Bellman-Ford algorithm:可包含负权边 (Dynamic Programming)
有权无向图最小生成树：
Spanning Tree:(Minimum Spanning Tree) 不能有环
Prim’s Minimum Spanning Tree （Greedy）
Kruskal’s Minimum Spanning Tree Algorithm （Greedy）
1.Dijkstra算法原理
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止
每次计算的是距离固定起点的最近距离。
原理：算法思路跟Prim算法类似，以某一确定的点开始，寻找当前该点可以访问的所有的点，计算起始点距离当前所有点的距离，取距离最小的点，加入visited集合。
2.Bellman-Ford algorithm算法原理
[S, A, B, C]
原理：
从某一确定的点开始S，更新所有可以访问到的节点(A,B)的距离，然后用A更新所有可以访问到的节点的距离.直到end:C.
重新从S开始，更新。如果此次更新没有更新任何操作，就结束。
3.Prim算法原理：
1）以某一个点开始，寻找当前该点可以访问的所有的边；
2）在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还没有访问的点加入我们的集合，记录添加的边；
3）寻找当前集合可以访问的所有边，重复2的过程，直到没有新的点可以加入；
4）此时由所有边构成的树即为最小生成树。
Prim算法和Dijkstra算法十分相似，惟一的区别是： Prim算法要寻找的是离已加入顶点距离最近的顶点； Dijkstra算法是寻找离固定顶点距离最近的顶点。
4.Kruskal算法原理：
1. 现在我们假设一个图有m个节点，n条边。
2. 首先，我们需要把m个节点看成m个独立的生成树，并且把n条边按照从小到大的数据进行排列。
3. 在n条边中，我们依次取出其中的每一条边，如果发现边的两个节点分别位于两棵树上，那么把两棵树合并成为一颗树；
4. 如果树的两个节点位于同一棵树上，那么忽略这条边，继续运行。等到所有的边都遍历结束之后，如果所有的生成树可以合并成一条生成树，那么它就是我们需要寻找的最小生成树，反之则没有最小生成树。
Dijkstra's - 用于问题：起点和终点定了，寻找有权图的最短路径，又叫best first search, 类贪心算法，实现方式和bfs很像.
个人感觉Dijkstra就是贪心版的bfs, bfs是勤勤恳恳一层一层推进，一层没访问完绝不访问下一层。Dijkstra就很贪心了，才不一层一层地走呢，他每次都想走最low cost的。
如何实现每次走最low cost的呢？用一个heapq来store a pair: (currCost to reach the node, node)
为什么Dijkstra算法比bfs快？首先很类似，为什么快呢？因为Dijkstra 的heapq pop出每一层的时候和bfs 普通q pop出每一层的元素顺序是不一样的。
Dijkstra's代码时需要注意的点：
需要一个heapq, heapq sotres (curr_cost, curr_node)
需要一个额外的空间distance/costs, 定义成dictionary, 快速记录和查找到从源节点某个节点的distance/cost, 同时可以当visited set用.
- 0743.Network_Delay_Time (!!M)
带权值的有向图求单源节点出发的最短路径问题马上就想到Dijkstra, O(NlogN + E) N is # nodes, E is # edges Dijkstra就是贪心版的bfs, bfs是勤勤恳恳一层一层推进，一层没访问完绝不访问下一层。Dijkstra就很贪心了，才不一层一层地走呢，他每次都想走最low cost的。如何实现每次走最low cost的呢？用一个heapq来store a pair: (currCost to reach the node, node), 这样每次pop出来的就都最low cost的node了，再去访问这个node的neighbors，把这些neighbors都加到hq中，代码比较短。思路其实与23. Merge k Sorted Lists非常类似，把23里的linked list加上一个虚拟头节点连接所有的头节点，然后把Linked list node的val改成边的权值，那就变成了单源节点出发求访问到所有节点的最短路径。 - 0787.Cheapest_Flights_Within_K_Stops (!!M)
有向图，带权值，找从单源出发最佳路径问题：Dijkstra's algorithm O(NlogN + E) hq 需要 store (cost, stops, airports), 与743相比少了一个currNode in costs: continue因为次好路径也可能是最后的结果，这是由于最好路径可能不满足stops < K; 这题需要加一个 if currStops >= K: continue - 1334.Find_the_City_With_the_Smallest_Number_of_Neighbors_at_a_Threshold_Distance.py
(!!M)
从每一个节点单独出发做一个Dijkstra, 比较每一个节点出发能到达的neighbors node的个数即可 - 1514.Path_with_Maximum_Probability.py (!!M)
把probability换成log表示就变第一种情况最大/最小 sum of the path - 0490.The_Maze.py (!!M)
Solution1: dfs更容易做 since the ball cannot stop at an empty place, must stop at wall, the tricky part is from the curr_stoppable position, find the next_stoppable position: use a while loop to find where is the next stop position. - 0505.The_Maze_II.py (!!M)
need to find the shortest path to reach destination. So dfs won't work. solution 1: Each stoppable pos is the node, while the steps needed from one stoppable pos to another stoppable pos is the weight in the graph. We use Dijkstra's to find path from source to destination. 这个题比普通的Dijkstra's就只是多了一步找下一个node的步骤. solution 2: just use a bfs, every time we reach the destination, we cannot return directly, because第二次到达的steps可能还更小，所以我们需要记录所有达到destination所用的步数. - 0499.The_Maze_III.py (!!H)
similar iwth 505 solution 2, use Dikstra's algorithm. hq needs to store the path: (curr_dist, curr_pos, curr_path). So when curr_pos == destination: instead of return curr_dist, we return curr_path.
- 1102.Path_With_Maximum_Minimum_Value (!!M)
Solution 1: 每次都把目前为止最小值最大的那个path的那个currNode pop出来，从那个currNode开始往后走. maintain a heapq to store (the minimum value in the path so far till the currPos, currPos); each time, we push (min(nextVal, currMinVal), nextPos); O(MNlogMN), O(MN)。 Solutoon 2: 让路径的最小值最大！！！策略：让每次走最大的node.最终就会路径的最小值的最大。max_minvals用来记录已经访问过的值。 - 0778.Swim_in_Rising_Water (!!H)
find a path with the minimum max-height in the path. 采用Dikstra, 每次pop出来的都是min height就可了 - O(N^2* log(N^2)), where N is the lens of grid. Google 面经：有一个nxn矩阵，信使从(0, 0)出发，想走到(n-1, n-1)去报信， 中途会有一些狮子/敌营，我们离狮子的距离越远越安全，问为了尽可能到达目的地，离狮子最大的最近距离是多少？ - 1631.Path_With_Minimum_Effort (!!M)
Obviously, it is a minimum of max_val problem, which is typical Dijkstra's. maintain a heapq to store (the max_diff in the path so far till the curr_pos, curr_pos). Each time, we push (max(next_diff, curr_max_diff), next_pos). 注意需要一个visited set to store the pos we visited. - Google.Maximum_Safty_for_the_Soldier.py (!!M)
similar with 1631. Google 面经：有一个nxn矩阵，信使从(0, 0)出发，想走到(n-1, n-1)去报信， 中途会有一些狮子/敌营，我们离狮子的距离越远越安全，问为了尽可能到达目的地，离狮子最大的最近距离是多少？ - Google.Student_Cheating_sheet.py (!!M)
similar with 1514. Dijkstra's. 问从a到b被捉概率最小的传递路线。本质上是weighted edge shortest path，因为不是DAG 所以用dijkstra
prim algorithm samilar to Dijkstra algorithm
Kruskal algorithm use union find
- 1135.Connecting_Cities_With_Minimum_Cost.py (!!H)
This problem is to find the minimum path to connect all nodes, so it is a minimum spanning tree (MST) problem. There are two defferent algorithms to solve MST problem, one is Prim's, the other is Kruskal's. The Kruskul's algorithm is easy to implement using Union-Find, with O(ElogE) time and O(V) space. Step 1: add all vertices to UnionFind obj; Step 2: sort the graph by edge weights; Step 3: add the smallest edge into the MST if adding the edge do not form a cycle; (if the two vertices of the edge was already connected, then adding the edge will form a cycle); Step 4: keep step 3 until all the edges are collected (E = V-1 or only one disjoint_cnt = 1) - 1168.Optimize_Water_Distribution_in_a_Village.py (!!H)
这个题目比较tricky的地方是需要想像有一个虚拟的house_0, house_0是出水的house, 这样house_1自己打井需要的cost就相当于从house_0连接到house_1所需的cost了. Other than hte tricky part, everything is exactly the same as 1135.