风啊雨-CSDN博客

原创刷题Day64|Floyd 算法精讲：97. 小明逛公园、A * 算法精讲：127. 骑士的攻击

分两种情况：（1）节点i 到节点j 的最短路径经过节点k：grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]。（2）节点i 到节点j 的最短路径不经过节点k：grid[i][j][k] = grid[i][j][k - 1]A * 可以有方向性的去搜索，关键在于启发式函数，启发式函数要影响的就是队列里元素的排序。使用优先级队列排好序，每次出队列，就是目前遍历的节点到达终点的距离最小的节点。思路：采用A * 算法，采用欧拉距离计算点与点之间的距离。

2024-07-26 10:35:41 403 1

原创刷题Day63|Bellman_ford算法优化版、判断负权回路、单源有限最短路径

有负权回路，如果松弛 n 次，结果就会有变化了，因为有负权回路就是可以无限最短路径（一直绕圈，就可以一直得到无限小的最短距离）。最多经过 k 个节点的条件下，而不是一定经过k个节点，也可以经过的节点数量比k小，但要最短的路径。（2）在队列优化版的bellman_ford（SPFA）基础上，判断如果节点加入队列的次数超过了 n-1次，那么该图就一定有负权回路。：SPFA是用队列来记录上次松弛的时候更新过的节点，只需要对上一次松弛的时候更新过的节点作为出发节点所连接的边进行松弛就够了。

2024-07-25 20:45:03 374

原创刷题Day62|Dijkstra(堆优化版): 47. 参加科学大会、Bellman-Ford算法：94. 城市间货物运输 I

参考：代码随想录（

2024-07-24 22:49:00 333

原创刷题Day61|拓扑排序：117. 软件构建、Dijkstra算法：47. 参加科学大会

（3）开始从队列里遍历入度为0 的节点：将其放入结果集；将该节点作为出发点所连接的节点的入度减一。如果连接节点的入度为0，放入队列（循环步骤23）。当然拓扑排序也要检测这个有向图是否有环，即存在循环依赖的情况，因为这种情况是不能做线性排序的。（1）我们要在初始化的时候，就把每个节点的入度和每个节点的依赖关系做统计。结果集的顺序，就是我们想要的拓扑排序顺序（结果集里顺序可能不唯一）（2）找入度为0 的节点，用队列放存放，依次去处理。（1）找到入度为0 的节点，加入结果集。

2024-07-23 11:29:31 407

原创刷题Day59|prim算法与kruskal算法：53. 寻宝

2. 遍历排序后的边（用到并查集方法）：如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环；如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合。总路径长度对不在同一个集合的边的长度不断累加。最后，minDist数组也就是记录的是最小生成树所有边的权值，最小生成树里边的权值总和就是把最后的 minDist 数组累加一起。1. 边的权值排序，要优先选最小的边加入到生成树里。

2024-07-21 00:33:34 288

原创刷题Day58|108. 冗余连接、109. 冗余连接II

分情况讨论：找到入度为2的点，需要判断删除哪一条边后本图能成为有向树。如果是删哪个都可以，优先删顺序靠后的边（从后向前遍历）；如果没有入度为2的点，说明图中有环了（注意是有向环），删掉构成环的边就可以了。从前向后遍历每一条边，边的两个节点如果不在同一个集合就相连加入集合，如果在同一个集合就不要相连直接返回。

2024-07-20 22:42:59 286

原创刷题Day57|107. 寻找存在的路径

思路：学习了并查集理论，使用并查集思路解决。并查集初始化，寻根，加入集合，判断是否是同根（即在同个集合）。

2024-07-19 22:45:44 167

原创刷题Day56|110. 字符串接龙、105. 有向图的完全可达性、106. 岛屿的周长

思路：dfs遍历有向图。访问过的节点都标记为true。本题在递归中不用回溯，我们只需要判断能否遍历所有点，而不是找到所有的路径。思路：bfs找最短路径长度。map存字符串和路径长度，queue存节点，for循环给字符串替换字母。思路：简单的数学题。遍历每个节点，遇到是岛屿的节点就根据条件计算这块岛屿贡献的一部分周长。

2024-07-18 23:20:07 228

原创刷题Day55|101.孤岛的总面积、102. 沉没孤岛、103. 水流问题、104. 建造最大岛屿

优化思路：第一次遍历地图，得出各个岛屿的面积，并做编号记录。第二次遍历地图，遍历0的方格（因为要将0变成1），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有0之后，就可以得出选一个0变成1 之后的最大面积。优化思路：反过来想，从第一组边界上的节点逆流而上，将遍历过的节点都标记上。从第二组边界的边上节点逆流而上，将遍历过的节点也标记上。从边上找节点开始遍历，遍历到的点不沉，标记为2。因为孤岛不能接触边缘，所以从边上开始找结点开始遍历，使用沉岛思想。遍历一遍全表的时候，统计岛的数量。

2024-07-17 23:11:11 332

原创刷题Day54|99. 岛屿数量、100. 岛屿的最大面积

深搜思路：从一个unvisited的结点开始dfs遍历它所有能到的节点并标为visited，然后res+=1。广搜思路：使用bfs来遍历一个unvisited的节点所能到的节点，进queue标记为visited。思路：在【99. 岛屿数量】的基础上，要记录每个岛屿的面积，最后取最大值。注意：也可以利用沉岛思路，访问过的岛屿都置为0。

2024-07-16 22:57:01 238

原创刷题Day52|98. 所有可达路径

思路：图可以用邻接矩阵或者邻接表存储。采用dfs来递归遍历图的节点。

2024-07-14 22:30:55 300

原创刷题Day51|42. 接雨水、84、柱状图中最大的矩形

遍历当前元素小于栈顶元素，进栈；等于栈顶元素，remove再add；大于栈顶元素，计算宽和高，由此计算当前槽的面积。整体面积是横向往上累加的。思路：单调递减栈，要找到左右第一个小于当前的元素，再讨论三种大于，等于，小于的情况。注意：栈还是加index。

2024-07-13 23:19:41 204

原创刷题Day50|739. 每日温度、496.下一个更大元素 I、503.下一个更大元素II

思路：依旧使用递增单调栈，分析三种情况：当前的元素大于、小于、等于栈顶元素。因为没有重复元素，用map做映射。思路：使用一个递增单调栈，可以从头到尾或者从尾到头遍历。栈中只存在大于前者的数组中的数。思路：和【739. 每日温度】差不多，但记住是循环数组，所以可以走两遍数组。注意：栈中只要存下标，通过下标可以找到对应的温度。

2024-07-12 23:07:42 177

原创刷题Day49|647. 回文子串、516.最长回文子序列

一共两种情况：s[i] = s[j]，i和j相差1以外就得判断中间包含的的字符串是否为回文了，所以if (j - i <=1) dp[i][j] = true;思路：dp[i][j]表示[i, j]内的回文字符串长度。两种情况讨论，如果s[i] =s[j]，dp[i][j] = dp[i+1][j-1] +2;否则就是i为头或者j为尾取最大值，dp[i][j] = max(dp[i+1][j], dp[i][j-1]）。注意：初始化的时候根据dp[i][j]的含义，i=j时dp[i][j]=1。

2024-07-11 21:06:18 373

原创刷题Day48|115.不同的子序列、583. 两个字符串的删除操作、72. 编辑距离

否则就是三种操作（增删改），”增删“都是任选一个word操作数+1，”改“是改一次就是能让word1/2相同，即三种情况取最小值：dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;否则因为两个word都可以删，只删一个或者两个都删：dp[i][j] = min(dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1);

2024-07-10 23:05:49 431

原创刷题Day47|1143.最长公共子序列、1035.不相交的线、53. 最大子序和、

当text1[i - 1] = text2[i - 1], dp[i][j] = dp[i - 1][j - 1] +1;因为两种情况都有可能出现较大值。思路：和【1143.最长公共子序列】类似（情况更简单），当s[i - 1] == t[j - 1]那么dp[i][j] = dp[i - 1][j - 1] + 1;否则dp[i][j] = dp[i][j - 1];思路：dp[i]的状态是加入或不加入nums[i]：dp[i] = max(dp[i - 1] + nums[i], nums[i]。

2024-07-09 23:29:12 390

原创刷题day45|300.最长递增子序列、674. 最长连续递增序列、 718. 最长重复子数组

思路：dp[i]的含义是以nums[i]为结尾的最长递增子序列的长度。dp[i]是统计0到i-1的最长子序列长度的最大值，它会一直更新，记得要dp[j]加1。思路：二维dp数组，记录i-1结尾和j-1结尾时的最长重复子数组的长度。两个for循环，dp[i][j] = dp[i - 1][j - 1] + 1。注意：i-1和j-1结尾省去了i和j结尾初始化要先遍历一遍获取值的过程，这样直接for循环时边进行边赋值。思路：因为是连续，所以dp[i]只和dp[i - 1]比较最长子序列的长度。

2024-07-07 23:20:57 250

原创刷题Day44|188.买卖股票的最佳时机IV、309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费

122.买卖股票的最佳时机II】基本一样，但是在不持有股票dp[i][1]的推导时需要再减去一笔手续费。思路：最多买卖k次，每次都有持有和不持有，所以下标最大到dp[i][2k]。思路：因为有冷冻期，所以卖出的状态要有保持卖出股票和刚卖出股票两个状态。

2024-07-06 23:04:32 294

原创刷题Day43|121. 买卖股票的最佳时机、122.买卖股票的最佳时机II、123.买卖股票的最佳时机III

也可以用动态规划，状态：当天持有股票和不持有股票。和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);思路：可以多次买卖，但是至多两次买卖，所以在【122、买卖股票的最佳时机II】题的基础上，多了几个状态，一共有五个状态。所以递推公式dp[i][0]中不仅仅是-prices[i]，而是dp[i - 1][1] - prices[i]。

2024-07-05 23:14:41 526

原创刷题Day42|198.打家劫舍、213.打家劫舍II、337.打家劫舍III

思路：最简单的动态规划思路。递推公式是dp[j] = Math.max(dp[j - 1], dp[j - 2] + nums[j])，要么打劫第j个房子（下一个打劫的房子不能和j相邻），要么不打劫第j个房子。思路：递推加动态规划。递归到左和右节点，取得该节点偷还是不偷的最大值。思路：让数组没有成环的情况：掐头包括尾，掐尾包括头。动态规划计算结果取最大值。注意：背包问题只是动态规划的一种题型，请记得动态规划的思路初衷。

2024-07-04 23:31:38 283

原创刷题Day41|322. 零钱兑换、279. 完全平方数、139.单词拆分

但是其中不存在要判断dp[j - i]]！思路：dp[i]表示长度为i的字符串是否可以被当前单词组成。被更新的j说明是当前硬币种类情况下，有硬币能凑成amount = j，我们找凑成的个数最小值。注意：只有当dp[j - coins[i]]！= max的时候，再更新dp[j]，这样才能不断更新”有意义“的dp[j]。注意：dp[j - i]中的i是完全平方数，不是完全平方数的i会自动跳过。放物品i：dp[j - coins[i]] + 1。dp[j]：装满容量为j，最少物品为dp[j]

2024-07-03 21:33:43 444

原创刷题Day40|518. 零钱兑换 II、377. 组合总和 Ⅳ、70. 爬楼梯（进阶）

递推公式和494、目标和一样：dp[j] += dp[j - nums[i]]。注意遍历顺序是先物品后背包才是组合。思路：每次爬的台阶数有多种，是完全背包问题。

2024-07-02 22:40:52 352

原创刷题Day38|1049. 最后一块石头的重量 II、494. 目标和、474.一和零

思路：和昨天的题目（分割等和子集）相似。明确三个条件：容量是target，重量为stones[i]，价值为stones[i]。递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])。

2024-06-29 06:24:26 276

原创刷题Day37|416. 分割等和子集

思路：0-1背包问题，重量和价值一样，每个元素只能使用一次，装满背包且最大价值为sum/2就是true。dp[target] = target返回true。注意：明确背包容量、重量和价值数组。

2024-06-28 23:20:26 277

原创刷题Day36|62.不同路径、 63. 不同路径 II

思路：初始化要明确。关于递推公式：走多少步 dp[i - 1][j] + 1；有几条路径dp[i - 1][j]。思路：基本和62一样。初始化数组要注意：一旦出现一个障碍物，后面的格子就再也无法达到了，路径数=0。注意：从左往右，从上往下：因为根据题意，每一个状态都从左边和上边的状态转移来的。63. 不同路径 II。

2024-06-27 17:57:33 162

原创刷题Day35|509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

注意：因为可以从0或1台阶往上走，所以dp[0] = 0;dp[1] = 0;而不是dp[1] = cost[0]！注意：初始化给i赋值可以从i有意义的值开始考虑，这道题目中i=1开始。注意：边界条件直接return。n<=1的时候return n。思路：明确每次走需要加上对应的cost，并取两种方法的最小值。思路：递归公式题目已经给出，用for循环遍历写逻辑就行。思路：递推公式自己推出（实际和509一样）。

2024-06-26 15:24:00 247

原创刷题Day34|56. 合并区间、738.单调递增的数字

思路：从后往前遍历，不满足递增：前一位减1，后一位取9。flag标记哪一位往后全都赋值9，否则半路碰到赋值9，后面的所有位数都要变成9，又得重新修改。思路：左边界排序。区间重叠之后做相应的处理。可以用list找到结果再add，也可以边add再remove更新完之后再add。2.char类型变量可以实现加减运算，通过查找对应变量值的ACSII值进行加减运算。1.用char[ ]取值比较再返回int，取/修改每一位的值比较方便。

2024-06-25 16:19:16 217

原创刷题Day33|452. 用最少数量的箭引爆气球、435. 无重叠区间、763.划分字母区间

思路：根据左边界升序排序。当当前左边界>上个元素右边界即res++不重合；当重合的时候更新右边界（直接对元素的右边界进行重新赋值）。思路：遍历s，统计字符最远出现的下标。再遍历判断字符最远出现的下标是否等于当前下标，等于的时候下标就是分割点。思路：和452一个思路，按照左边界排序，找重叠区间的个数。也可以按照右边界排序，找非交叉区间的个数。注意：排序的时候使用Integer.compare，不然会因为溢出有一个testcase不通过。

2024-06-24 23:23:54 279

原创刷题Day31|134. 加油站、135. 分发糖果、860.柠檬水找零、406.根据身高重建队列

思路：先按照身高属性从高到低排序，身高相同k小靠前。再根据k的属性看是否往前插（往前插不会破坏原来的顺序，因为后面的身高一定比前面的矮，k是统计比自己高的）思路：贪心：优先消耗10（比起消耗2个5）。注意：只要总和totalSum大于0，我们只要找到起始位置就可以。局部最优：当前的油量和要>0。遍历统计curSum，要是小于0就清零。从左到右：统计右边比左边大；从右到左：统计左边比右边大。注意：插入操作直接查到对应index = k处的位置就行。注意：第二次循环统计最大值，不仅仅是否+1。

2024-06-23 23:09:40 275

原创刷题Day30|122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II、1005.K次取反后最大化的数组和

思路：贪心，用最小的步数覆盖最大的范围。每走一步更新最大的覆盖范围and记录步数，判断是否覆盖到最后一个数？break：更新当前数的覆盖范围。局部最优：每个元素能覆盖的最大范围；全局最优：整个序列能覆盖的最大范围。如果最大覆盖范围包括最后一个数，return true。注意：for循环中i<cover，cover是变量。只有在cover的范围内探索能覆盖的最大区域。思路：首先尽可能把所有负数变为正数，其次把绝对值最小的正数再变为负数。局部最优：每天的利润（利润>0）；全局最优：几天下来的最大利润。

2024-06-22 19:49:05 281

空空如也

空空如也