【LeetCode】数据结构与算法 最短路径

Happy coding! Enjoy Algorithms.

【LeetCode】数据结构与算法 第一期 图的最短路径问题

如何刷题：表达+熟练+重复5遍

1. 刷题不需要刷那么多！！不需要那么多！！不需要辣么多！！刷熟常用300题，刷5遍，效果 >>>>>(远好于） 我这样刷到900+题。
2. 个人感觉：熟练度 >>>>> （远重要于）抖小聪明。流畅的表达，简介明了的思路远好于在白板上磨磨蹭蹭的推导。这也回到第一点，反复刷同样的题非常重要。

其实，8-10遍高频效果是最好的，这基本就是到另一个境界了。当然，大家没有那么多时间，3-5遍也可以去面试了。

1. Talk out loud，这个不仅仅是说在面试的时候你要说出你的思路。

刷题的时候也是！你第一遍可以不开口，但后面几遍，一定要开口说话！！

刷题是为了面试，面试第一看的是communication skill! 不在刷题的时候开口，到面试的时候才意识到沟通不畅就太晚了。

1. 关于具体刷题，我只说第一遍，我是怎么刷的。

前500题：抄。就是直接看答案抄！完美解决没基础看不懂，不会做，做题枯燥等种种问题。其实，我觉得，在刚开始的时候完全没必要思考，做题。因为初学者啥也不会。自己拼命想，写两题就被劝退不想再做了。

1. https://afteracademy.com/tech-interview/ds-algo-concepts 题目总结和这个对比起来。

优先级队列使用场景和 课后作业

• CPU Scheduling
• Event-driven Simulation.
• A* search algorithm in AI.
• Data compression using Huffman coding.【tree】
• Statistics (maintain the largest M values in a sequence).

Suggested Problems to Solve in Heaps

• K Pairs with Smallest Sums
• Sliding window maximum
• Merge K sorted list
• Convert a min heap to max heap

题目

【LeetCode】Daily Coding Challenge 124. 二叉树中的最大路径和

分析：

• 假如给我一个二叉树root， 利用已有掌握知识，（数学几何都是利用已知识信息 推到更复杂信息） 我能计算出roo为根节点高度/深度/路径。最大路径。9 -10 20 15组成的链表（类比hegiht）

不一定经过root节点。因为每个节点值不一定，可能需要计算每个node， 每个node就是一个tree

• 难点1 如何：二叉树的每个节点都计算执行一遍（从上到下看） 变成遍历一边（从下到上）

【万变不离其宗还是利用 遍历，但是返回值 不是最大路径，二是最深路径，需要2个返回值】

• 难点2 :负数一定舍去吧？如果叶子节点肯定删除，如果中间的，看sum结果。

###【LeetCode】Daily Coding Challenge 54. 螺旋矩阵

分析

• 从一个位置到另外一个位置，只有一个路径。该怎么遍历？
• 【100%确定事情】 按照行列遍历线型方式肯定不行。
• 【100%确定事情】 这里不需要回溯。

如何判断一个图是否有环？207. 课程表

• 【你知道，大家都知道知识】 无论怎么遍历，最终收回输出一个顺序。
• 定义：遍历顺序 开始位置 = 结束位置。
• 一个节点被访问2次 一定是环吗？

• 0为一次dfs遍历 入口节点，这个节点被访问2次，说明存在环。
• 说明 如果 3也被访问2次，这个不是环