547.省份数量 深度优先遍历 找到未访问过的城市，深度优先遍历其所有能联通的城市，并标记为已访问。 最后统计有几个联通量。 时间复杂度：O(N^2)空间复杂度：O(N) 2021-09-20 算法 > leetcode
560. 和为 K 的子数组 前缀和+哈希 滚动计算前缀和，同时查找哈希值中有符合前缀和之差等于k的前缀和的出现次数。 最后累加哈希中前缀和的出现次数。 时间复杂度：O(N)空间复杂度：O(N) 2021-09-20 算法 > leetcode
673.最长递增子序列的个数 动态规划 要注意统计个数的时候，dp相等时要把之前的数量累加上，dp大的时候则是直接继承之前的数量。 时间复杂度： O(N^2)空间复杂度：O(N) 2021-09-20 算法 > leetcode
684.冗余链接 leetcode 使用并查集方法，维护联通分量数组，检验每条边的两个节点，如果已经联通了，则当前边导致成环，为冗余链接。 时间复杂度：空间复杂度：O(n) 2021-09-20 算法 > leetcode
685.冗余链接2 leetcode 建立出边邻接表，节点入度数组。 因为需要返回最后的一个可以去除的边，故倒序删除边，删除后满足树的条件则表明该边为要找的冗余边。 为树的条件： 有且只有一个入度大于0的点（防止成环） 且最长路径的步数和节点数相等（防止有独立的多块不联通的图） 2021-09-20 算法 > leetcode
699. 掉落的方块 12345678910111213141516171819202122232425262728293031323334353637type Box struct { Left int Right int Height int}func fallingSquares(positions [][]int) []int { boxes := []B 2021-09-20 算法 > leetcode
72.编辑距离 动态规划 f[i][j] 记录 word1[1..i] 到 word2[1..j] 的最短编辑距离。则考虑三种情况： word1插入一个字符和word2相等：f[i][j-1] + 1 word1删除一个字符和word2相等： f[i-1][j] + 1 word1替换一个字符和word2相等：f[i-1]f[j-1] + eq 。其中eq考虑两种状态，如果word1要替换的这个字符和word2 2021-09-20 算法 > leetcode