目录 Bellman_ford算法 模拟过程 题目：94.城市间货物运输I Bellman_ford队列优化算法（又名SPFA） 模拟过程 题目：94.城市间货物运输I Bellman_ford算法之判断负权回路 题目：95.城市间货物运输II Bellman_ford算法之单源有限最短路 题目：96.城市间货物运输III Bellman_ford算法 Bellman_ford算法解决的问题和dijkstra朴素版要解决的问题类似，唯一不同的是dijkstra解决的问题中边的权值不能为负数，而Bellman_ford算法要解决的问题是带负权值的单源最短路问题。 ...

目录 Floyd算法 题目：97.小明逛公园 A算法 题目：126.骑士的攻击 最短路算法总结 Floyd算法 Floyd算法用于求解多源最短路问题（求多个起点到多个终点的多条最短路径）。在前面学习的dijkstra算法、Bellman算法都是求解单源最短路的问题（即只能有一个起点）。 注意：Floyd算法对边的权值正负没有要求，都可以处理。 Floyd的核心思想是动态规划。 动态规划的五部曲： 确定dp数组（dptable）以及下标的含义。 确定递推公式。 dp数组如何初始化。 确定遍历顺序。 举例推导dp数组。 根据动态规划的五部曲来解释Floyd算法的遍历...

目录 拓扑排序 题目：117.软件构建 dijkstra（朴素版） 题目：47.参加科学大会 dijkstra算法和prim算法的区别 dijkstra（堆优化版） 题目：47.参加科学大会 拓扑排序 拓扑排序概括来说就是给出一个有向无环图，把这个有向无环图转成线性的排序，就叫拓扑排序。 使用广度优先搜索（BFS）即可。 如上图，当我们做拓扑排序的时候，优先找入度为0的节点，只有入度为0，它才是出发节点。 拓扑排序的过程： 找到入度为0的节点，加入结果集。 将该节点从图中移除。 循环以上两步，直到所有节点都在图中被移除了。 结果集的顺序，就是我们想要的拓扑排序...

目录 最小生成树的解题 prim算法 举例说明（来自代码随想录） 题目：53.寻宝 Kruskal算法 举例说明（来自代码随想录） 题目：53.寻宝 最小生成树的解题 最小生成树类型的题目主要用于解决所有节点的最小连通子图的问题，即：以最小的成本（边的权值）将图中所有节点链接到一起。 最小生成树可以使用prim算法，也可以使用kruskal算法计算出来。 prim算法 prim算法的核心有三步： 第一步，选距离生成树最近节点。 第二步，最近节点加入生成树。 第三步，更新非生成树节点到生成树的距离（即更新minDist数组） 其中，minDist数组最为重要，用来...

目录 110.字符串接龙 105.有向图的完全可达性 DFS BFS 106.岛屿的周长 解法一 解法二 110.字符串接龙 题目链接：https://kamacoder.com/problempage.php?pid=1183文章讲解：https://programmercarl.com/kamacoder/0110.字符串接龙.html题目状态：看题解 思路： 输入部分: 读取单词数量(n)。 读取起始单词beginStr和目标单词endStr。 读取并存储单词集合strSet。 辅助数据结构: visitMap:记录每个单词是否被访问过，以及路径长度。...

目录 并查集模板 107.寻找存在的路径 并查集模板 原理： 并查集主要有两个功能： 将两个元素添加到一个集合中。 判断两个元素在不在同一个集合。 模板代码： intn=1005;//n根据题目中节点数量而定，一般比节点数量大一点就好 vector<int>father=vector<int>(n,0);//C里的一种数组结构 //并查集初始化 voidinit(){ for(inti=0;i<n;i){ father[i]=i; } } //并查集里寻根的过程 intfind(intu){ returnufather[u]?u:father...

目录 108.冗余连接 109.冗余连接II 108.冗余连接 题目链接：https://kamacoder.com/problempage.php?pid=1181文章讲解：https://www.programmercarl.com/kamacoder/0108.冗余连接.html题目状态：看题解 思路： 构建并查集，然后通过并查集来判断节点，若当前这对节点(s,t)在同一个集合中，那么输出这对节点即可达到题目要求，否则，就将s和t合并到同一个集合中。 代码： include<iostream> include<vector> usingname...

目录 101.孤岛的总面积 DFS思路 BFS思路 102.沉没孤岛 103.水流问题 104.建造最大岛屿 101.孤岛的总面积 题目链接：https://kamacoder.com/problempage.php?pid=1173文章讲解：https://programmercarl.com/kamacoder/0101.孤岛的总面积.html题目状态：看题解 DFS思路 思路： 代码结构 变量和方向数组: dir[4][2]：定义了四个方向的移动（上、左、下、右）。 count：用于统计符合条件的陆地块数量。 深度优先搜索函数dfs: 输入参数为二维数组g...

200.岛屿数量 题目链接：https://leetcode.cn/problems/number-of-islands/description/文章讲解：https://programmercarl.com/kamacoder/0099.岛屿的数量深搜.html题目难度：中等题目状态：看题解 思路一：深搜版 方法dfs： 参数:接受一个字符网格grid和当前坐标(r,c)。 功能:将当前岛屿的所有相连部分标记为已访问。 实现: 改变当前坐标的值为'0'，表示已访问。 检查上下左右四个方向，如果相邻位置是'1'，递归调用dfs。 方法numIslands： 参数:接受一个字符网格...

797.所有可能的路径 题目链接：https://leetcode.cn/problems/all-paths-from-source-to-target/description/文章讲解：https://programmercarl.com/kamacoder/0098.所有可达路径.html题目难度：中等题目状态：看题解 思路一：DFS voiddfs(vector<vector<int>>&graph,intx,intn)：使用深度优先搜索（DFS）方法，用于探索从节点x到节点n的所有路径。逻辑： 如果当前节点x是目标节点n，将当前路径stk添加到a...

647.回文子串 题目链接：https://leetcode.cn/problems/palindromic-substrings/文章讲解：https://programmercarl.com/0647.回文子串.html题目难度：中等视频讲解：https://www.bilibili.com/video/BV17G4y1y7z9/题目状态：看题解 思路一：动态规划 使用一个二维动规数组dp[i][j]来保存从s[i]到s[j]（或从s[j]到s[i]，一样的，本题代码是从j到i）是否属于回文子串。两层遍历该字符串，来记录回文子串的个数。 当s[i]s[j]时，要判断一下i和j的距离，...

739.每日温度 题目链接：https://leetcode.cn/problems/daily-temperatures/文章讲解：https://programmercarl.com/0739.每日温度.html题目难度：中等视频讲解：https://www.bilibili.com/video/BV1my4y1Z7jj/题目状态：看题解 思路： 定义一个单调栈，该栈存放下标，规则是要保持其下标对应的温度值从栈底到栈头是单调递减的。再定义一个和题目数组大小相等的数组ans存放结果，初始化为0。具体步骤如下： 先将第一个元素的下标存入栈中。 循环遍历温度数组： 若当前温度小于等于栈头...

42.接雨水 题目链接：https://leetcode.cn/problems/trapping-rain-water/文章讲解：https://programmercarl.com/0042.接雨水.html题目难度：困难视频讲解：https://www.bilibili.com/video/BV1uD4y1u75P/题目状态：这道题目在LeetCodeTop100中做过，使用两种方法，再回顾一下 思路一：单调栈 栈的作用： 栈用于存储柱子的索引，确保栈中的高度是递减的。 遍历数组： 对于每个柱子，如果当前柱子高度大于栈顶柱子高度，说明可以形成一个凹槽来积水。 计算积水： ...

115.不同的子序列 题目链接：https://leetcode.cn/problems/distinct-subsequences/文章讲解：https://programmercarl.com/0115.不同的子序列.html题目难度：困难视频讲解：https://www.bilibili.com/video/BV1fG4y1m75Q/题目状态：看题解 思路： 动态规划数组初始化 创建一个二维动态规划数组dp，大小为((s.size()+1),(t.size()+1))。dp[i][j]表示s的前i个字符中包含t的前j个字符的不同子序列的数量。 边界条件设置 dp[i][0]=...

1143.最长公共子序列 题目链接：https://leetcode.cn/problems/longest-common-subsequence/文章讲解：https://programmercarl.com/1143.最长公共子序列.html题目难度：中等视频讲解：https://www.bilibili.com/video/BV1ye4y1L7CQ题目状态：有点思路，但细节有点混乱 思路： 维护一个二维动规数组dp[i][j]，用来记录长度为i-1的字符串text1与长度为j-1的字符串text2的最长公共子序列，它的更新条件如下： 若text1[i1]text2[j1]，则dp[...

300.最长递增子序列 题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/文章讲解：https://programmercarl.com/0300.最长上升子序列.html题目难度：中等视频讲解：https://www.bilibili.com/video/BV1ng411J7xP题目状态：有思路，但是自己能写出来还是太勉强，有些细节想不到 思路： 维护一个动规数组dp[i]，表示在遍历到数组中的第i个元素的时候，此时能找到的最长递增子序列的长度。 其更新的代码如下：if(num[i]>num[j])dp...

188.买卖股票的最佳时机IV 题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/文章讲解：https://programmercarl.com/0188.买卖股票的最佳时机IV.html题目难度：困难视频讲解：https://www.bilibili.com/video/BV16M411U7XJ题目状态：太难了，勉强理解，自己做肯定做不出来 思路： 这是买卖股票的最佳时机III的进阶版本，股票III题目中我们将每天分为五个状态： 无操作 第一次买入 第一次卖出 第二次买入 第二次卖出 在这道题中我...

121.买卖股票的最佳时机 题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/文章讲解：https://programmercarl.com/0121.买卖股票的最佳时机.html题目难度：简单视频讲解：https://www.bilibili.com/video/BV1Xe4y1u77q题目状态：有一半的思路 思路一：贪心 对数组进行遍历，分别保存两个变量：最小的买入时间left，最大的获利金额ans，遍历完就得到答案了。 代码： classSolution{ public: intmaxProfit(ve...

283.移动零 题目链接：https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked题目难度：简单标签：数组、双指针题目状态：AC 思路： 两个指针，i用来找0，j用来找非0。当nums[i]0&&nums[j]!=0时，将两者交换。 代码： classSolution{ public: voidmoveZeroes(vector<int>&nums){ inti=0; for(intj=1;j<nums.si...

3.无重复字符的最长子串 题目链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked题目难度：中等标签：哈希表、字符串、滑动窗口题目状态：学习题解 思路： 滑动窗口的思路，也就是维持一个无序队列unordered_set<char>用来当作这个窗口。 遍历字符串，若当前字符不在窗口中，就将该字符insert进窗口中，然后将长度加1。 若当前字符在窗口中，就将窗...