知识点

LeetCode算法题

1. LeetCode算法题

   1. 学习

      1. 787.【K 站中转内最便宜的航班】

         解题思路：

         思路1：图的最短路径，可以用BFS来做。BFS中必然要用到一个队列来存储边，一般的无权图（或者多叉树）使用普通的Queue即可，因为无权图相当于每个边权重都为1，所以不存在排序问题；但是有权图，我们要考虑每个边的权重，因此需要使用PriorityQueue来存储边，让PriorityQueue帮我们自动排序。

         思路2：求最值的问题，很多都可能使用动态规划来求解。加权最短路径问题，再加个K的限制，也是个求最值的问题。首先，不考虑k的限制，单就「加权最短路径」这个问题如何分析它是否为动态规划问题：目的地是dst节点，到dst节点的加权最短路径=min(相邻节点1的加权最短路径+相邻节点1到dst路径，相邻节点2的加权最短路径+相邻节点2到dst路径，...)，拓展到其他节点一样，是动态规划。

   2. 复习

      1. 887.【鸡蛋掉落】

         解题思路：

         肯定需要穷举，而该题目又是求最值得，因此先考虑动态规划。

         状态肯定有两个：楼层数、鸡蛋个数。

         选择，肯定是从第几层楼上扔鸡蛋

         base case。当只有一个鸡蛋了，肯定是线性遍历剩下的所有楼层，找到目标楼层；如果楼层为0，不用尝试了，尝试次数为0。

         状态转移：假设在第i层扔鸡蛋，鸡蛋有两个情况，碎了，则鸡蛋的个数K应该减一，搜索的楼层区间应该从[1..N]变为[1..i-1]共i-1层楼；没碎，说明目标楼层在上面，鸡蛋的个数K不变，搜索的楼层区间应该从 [1..N]变为[i+1..N]共N-i层楼。注意，我们要求的是最坏情况下扔鸡蛋的次数，所以鸡蛋在第i层楼碎没碎，取决于那种情况的结果更大。

      2. 312.【戳气球】