今天总结这四道题目

无重复字符的最长子串

这题已经做了多次，但是今天做的时候发现了一个我之前有点没有重视的地方。我们通过HashMap来记录重复的字符出现的下标，然后为了加快算法执行，如果发生重复，我们会将子字符串开始的下标记作从Hashmap中取出的下标+1.但是这里一定要注意，判断重复的字符和当前的字符串开始的下标的大小，不然有可能出现【往回拉】的情况，导致最后出错。

概率最大的路径

这实际上是地杰斯特拉算法的变体。

求一个单源最短路径问题。算法主要分成这样几个方面：

1. 构建带权图的数据结构：我们通过List<List<Pair>>来存储节点以及边上的权值信息。

2. 迪杰斯特拉算法其实就是一个BFS+贪心的过程，所以下一个需要遍历到的节点，应该使得当前的概率最大。我们可以使用优先队列。

3. 开辟一个数组记录从起始点到当前的点的概率值，只有大于这个概率才可以被加入队列（不然肯定有更好的路径，不走重复的道路）

代码如下：

课程表I

我们首先需要对问题有一个了解：

1. 这是一个图问题，这个图可能有很多子图

2. 只要每一个子图中不存在环就行

可以使用拓扑排序，也可以使用dfs。我这里使用的dfs，思路主要是这样：

visited表示当前的节点访问的情况，0 表示没有访问过，1表示已经访问了。同时我们还需要使用另外一个值：-1.因为我们在考察课程是否会形成环路的时候，我们开始的节点可能是一个大图中的一部分，所以visited数组需要传递，但是我们直接记录为1的话无法区分是在本次的dfs中出现了重复，还是咋地，所以我们使用-1表示在其他的dfs中已经访问过，而且没有环路（不然直接返回false了）

代码如下：

课程表II

这个问题虽然题目中没有指出，但是其实还是需要判断是否存在环。其实这个问题很明显就是拓扑排序问题。我们首先记录每一个点的出度，出度为0的点，一定是最先需要上的课。在构建表的时候也注意需要反向构建路径。首先将出度为0的点加入队列，然后从队列中弹出，并且将它指向的节点的出度都--，然后将出度为0的节点加入队列。如果最后所有的点都能被弹出，说明不存在环。而且我们也可以形成一个结果：

最长的回文子串

这道题我才用的方式是中心扩散法：