没想到 63 天了。 其实之前半差不差的刷过一遍。 这次算是养成一个习惯，每天还是要有一定的 code 量。希望之后能保持这样的习惯

没想到还有一天，然后描述一下 floyd 的算法, 核心就是遍历点作为中间的节点来获取最短的路径。节点i 到 节点j 的最短路径允许经过节点 k 的最短路径分两种情况：节点i 到 节点j 的最短路径经过节点k节点i 到 节点j 的最短路径不经过节点k dp[i][j][k] = min(dp[i][j][k-1],dp[i][k][k-1]+dp[k][j][k-1])我们把 节点 0 的情况设置为初始值遍历顺序就是每次选一个节点作为中间节点，然后遍历所有节点。先 k 再 ij

优化一 用队列每次的松弛过程中，我们不用对所有的边进行遍历，只需要对上一次松弛过后的能达到的点的集合进行遍历维护一个点集合， 每次松弛过后便把 to 节点加入到这个集合中。 每次松弛找的边都需要在这个点集合里面的点为开始既然是一个集合要避免重复加入变形二 判断负环判断 n-1 次必定能达到end，那么再判断一次，如果出现负环则路径会继续更行。变形二 判断 k 次至多经过 k 次城市可以达到的最短距离。 显然只需要松弛k+1次即可一个问题是松弛的过程中我们会对所有的边进行松弛，他们的先后顺序导致了我们松弛次数和实际经过节点个数的区别举个例子就是当边的先后顺序很好的时候一次遍历即可得到最短路径，但...

在 dijk 求最小路径的过程中我们每次会选择离集合最近的一个点加入进去，并且更新和这个点相连的所有距离。一个优化方法是在我们维持一个小根堆表示离集合最近的点，取出最近的点，然后将更新后的距离重新加入的小根堆里面一个问题就是一个点对应的不同距离会重复加入到小根堆中，我们通过 visited 数组进行判断过滤。bellman 算法维护的是一个边集合我们从 1 号点出发，遍历边集合内的所有边，更新点的所有距离mindist由于边给的顺序不同，理论上来说最完美的顺序可以一次得到最短距离，而最差我们可以得到所有和 1 号点相连一条边的最短距离我们距离 n 号点共有n-1条边，也就是无论如何我们只要遍历...

拓扑排序bfs 初始化，找到所有入度为 0 的节点加入 que遍历 que， 每取出一个节点，就把他对应 start 边的 end 节点的入度度数-1如果有对应度数为 0 的相邻点则加入 quedijkstra 排序维持一个点集合往集合加入 1 节点，并且更新 mindist 数组（表示的是该节点到 1 的最短距离）遍历所有节点，得到离当前结合最近的点 cur更新和 cur 相邻的，且不在集合内的 mindist 距离mindist[i]=min(mindist[cur] + g[cur][i],mindist[i])然后是关于是否可以有负数的问题Prime 维护的是一个 到集合的最短距离，所...

prim维护一个最小生成树的点集合minWeight 数组表示点到这个集合的距离默认所有节点离这个数的距离是无穷大随机选取一个节点，然后更新相连节点的 minWeight 数组持续遍历所有不在树里面节点，找到离这个树最近的节点cur把 cur 加入到树里面，并且更新和 cur 关联节点的minWeightKruskal算法维护一个最小生成树的边集合遍历所有边，如果两个节点不在同一个集合里，则加入边，并且加到一个集合中不在一个集合则跳过

108 是无向图，所以相当于构造一个并查集，如果发现有 root 相同去掉就可以109 是有向图。然后主要是关于有向树的定义，就是除树根外的结点入度为1；有向树除树根外的结点入度为1；输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边针对第一个条件我们找到入度为 2 的点，此时必须删除一条，如果不删除的话不合条件针对第二个情况找到入度 2 的两条边，从后往前删除，查看是否可以成树，可以就打印。如果没有入度2 的节点，则就是相当于无向图的并查集，照之前的写即可。

几个操作find（u） 查找一个元素 u 的 root。 其中向上的过程可能会有多个层级，由于我们找到了最后的 root，通过root[u]=find(root[u])这个方法可以避免后续遍历过多的层级。join(start,end) 把两个节点关联在一起。 首先查询两个点的 root 点，如果相同则不用关联不关联则将查询到的 2 个 root 点关联起来。 注意的是不能直接讲 start 和 end 关联在一起（因为我们构造的都是一个全部指向 root 的有向图，此时 start 会有两个指向，原有 start 节点和 end 节点（用数组存储的话只有一个指向，相当于修改了start 的 r...

110. 字符串接龙 先构建出图bfs 查询最短距离105. 有向图的完全可达性 dfs 遍历所有节点，如果到达则可以106. 岛屿的周长 直接遍历所有节点和相连接的边的数量

101. 孤岛的总面积 先标记周围的岛屿为 2记录剩余的岛屿数量 102. 沉没孤岛 先标记周围的岛屿为 2标记剩余的岛屿为 0把 2 标记回 1103. 水流问题 反向考虑，从左上角逆向 dfs和右下角 dfs 能同时到达的地方104.建造最大岛屿1. 先遍历一次 dfs，每次有新的岛屿就标记不同的记号2. 遍历每个海水的节点，考虑四周标记的记号，记录最大的面积

简单来说就是 BFS 和 DFS 两种方法。然后关于 python 一些基本语法。 input.split() split 的默认值是对空白字符的，所以输入的时候不用给任何参数。然后是在加入队列就就需要标记，还是从队列拿出来的时候再去标记走过。如果没有做标记的话，后续可能会重复加入同一个节点。 所以可以用一个 set 来进行一下判断，或者就在加入队列的时候进行标记。但是如果要计算岛屿数量的话就需要在进行标记的时候对题目的一些条件进行判断，否则可能会是不有效的数据。既然要标记了，实际上我们就要进行状态的判断。 因此是判断位置放的地方不一样。 是在加入前还是在遍历的时候。

今天这个主要是了解一下 acm 的输入和输出处理python 里面的 input 主要都是字符串，所以输入的时候手动转成 int 类型。 这里用 split 的语法，split 的语法和 js 的类似然后是输出的时候，用 join加上空格。join 语法和 js 的有点区别就是连接的词是放在前面的，调用的是连接词的 join 方法然后输出的时候要重新把 int 类型转换为 str 类型，这样才能直接进行数字上的加减。

接雨水和*********两道题接雨水维持一个单调递减的list，如果有一个高出的元素且当前 list 有至少两个元素，那么我们就可以找到一部分是可以装水的。装完之后则可以pop 出去维持单调性 if len(stack)>=2: h = min(stack[-2][1],height[i])-stack[-1][1] w=i-stack[-2][0]-1 count+=w*h 柱状图最大矩形题目可以翻译为在一维数组中对每一个数找到一个比自己小的元素，这样构成的矩形面积可以看做这个数构成的最大矩形 while stack and heights[i]<stack[-1][1]: i...

739. 每日温度  求的是下一个更高温度的天数还有几天出现。 首先我们维持一个单调递减的stack，因为显然这个栈里面不会出现更高温度的天。 如果出现了一个更高温度的天，我们可以利用二分法重新构造这个队列。 当然因为我们要求每天的天数，所以从后往前遍历这个 list，依次 pop，求出对应的天数。 因为要求索引的差值，所以我们不能存入值，而是应当存入索引。 为了方便我这里用一个元祖直接表示了。 stack = [(0,temperatures[0])] if temperatures[i]<stack[-1][1]: stack.append((i,temperatures[i])) ...