还有几天就打蓝桥杯了, 这里就记录一下个人备赛训练中学到的算法小寄巧~ 这里只是基于个人的总结, 看完之后不一定能拿奖。。。当然结果啥的并不重要, 重要的是学到的算法思路和优化的技巧, 帮助你在日后写出更优美高效的代码。
目录:
* 图论
(相关资料图)
* 二分搜索
* 前缀和与差分
* 并查集
图论
图论里面最经典的问题就是最短路径了, 求最短路径的两种算法思想, 一种是基于贪心算法的dijkstra, 另外一种是基于动态规划的 Floyd 和 Bellman-ford。
dijkstra 的算法过程:
dijkstra一般用来解决单源最短路径问题(边权一定要为正数), 首先我们定义一个数组 dist, 然后我们再定义一个集合 S, 我们首先把源点的距离(dist数组)设置为 0 然后放入集合 S 中.
之后我们在 集合 S 中 找到一个没有访问过且 dist最小的一个节点, 对这个节点进行松弛操作并更新 dist 数组, 最后标记为已访问过。
重复以上过程 n - 1 次。
经典模板题:
https://www.lanqiao.cn/problems/1460/learning/?page=1&first_category_id=1&sort=students_count&name=%E8%B7%AF%E5%BE%84
Bell-ford实际上是动态规划, 我们定义 dp 方程:
dp[i][j]： 在第 i 步内到达 节点 j 的最短路径.
其中 j 是 v 的某一条邻边, 定义 cost(v, j) 为v 到 j 的路径:
dp[i][j] = min(dp[i][j], dp[i - 1][v] + cost(v, j))
我们可以对其进行状态压缩:
dp[j] = min(dp[j], dp[v] + cost(v, j)
于是我们发现这不就是松弛操作吗?
那么就相当于对每条边进行松弛操作, 所以说 Bellman-ford 更像是暴力法, 时间复杂度会比 Djikstra高:
二分搜索
对于二分查找如果我们要找某个元素是否在一个数组中, 这很容易实现。但一般问题需要在数组查找满足条件的某个区间的左端点或者右端点, 这时候就要注意好循环时更新区间的细节，不然很容易出现死循环。
当我们要获取满足条件的左端点时:
列如：在升序数组中找到第一个不小于target的索引：
nums = [5,7,7,8,8,10], target = 8; ans = 3;
对于这个问题我们不要死记硬背, 我们来直观地理解一下:
当 arr[mid] < val 时, 我们才会更新 left， 我们已上面为例子, 那么会出现两种情况:
1. 当 mid 取到索引 2 时, 此时元素是 7, 那么l = mid + 1 = 3， 之后我们只会更新 r, 当出现 l = r - 1时, 我们更新 mid = (l + r) >> 1 (向下取整), 那么最后的 l 是 3。 (证明了此时答案为左端点)
索引: 0 1 2 3 4 5
元素: 5 7 7 8 8 10
2. 当 mid 没有取到索引 2 时, 此时我们的 l 最终一定会落在索引 2, r 会落在索引3, 此时我们更新 mid = (l + r) >> 1 (向下取整), 此时 mid = 2, l = mid + 1 = 3, 那么最后的 l 是 3。 (证明了此时答案也为左端点)
索引: 0 1 2 3 4 5
元素: 5 7 7 8 8 10
当我们要获取满足条件的右端点时:
列如：在升序数组中找到最后一个不大于target的索引。
nums = [5,7,7,8,8,10], target = 8; ans = 4;
证明和上面的一样。。。此时 mid = (l + r + 1) >> 1 为向上取整了, 所以取得了右端点.
当然，也可以这样理解：
当我们要取左端点时(对应上面的第一种), 我们满足条件了那么 r = mid 说明我们不再往>r的方向找了, 没满足条件我们就使得 l = mid + 1继续搜索。
当我们要取右端点时(对应上面的第二种), 我们满足条件那么 l = mid 继续搜索直到获取到满足条件的最大下标, 没满足条件我们就使得 r = mid - 1 继续搜索.
例题:
1.分巧克力：
前缀和与差分
一维前缀和
预处理出s[]，s[i]存储前i个数的和:
计算[l,r]区间和:
二维前缀和
左上角坐标为(1,1)，右下角坐标为(i,j)的前缀和（区域内所有数的和）
求左上角坐标为(x1,y1)，右下角坐标为(x2,y2)的前缀和
例题: 统计子矩阵
给定一个 N×M 的矩阵 A, 请你统计有多少个子矩阵 (最小 1×1, 最大N×M) 满足子矩阵中所有数的和不超过给定的整数 K ?
一维差分
二维差分
并查集
并查集是一种优美的数据结构, 在之前的 leetcode 题解中介绍过:
leetcode赛后补题: 322周赛题解 - 哔哩哔哩 (bilibili.com)
例题: 七段码:
https://www.lanqiao.cn/problems/595/learning/
我们首先建图, 然后只需要dfs枚举出所有的亮灯情况, 判断亮灯的部分是否是一个连通块即可:
