梅县区住房和城市建设局网站,全国十大网站建设公司哪家好,怎样做吧网站排名做上去,南宁网站建设哪家好#x1f4dd;前言说明#xff1a;
本专栏主要记录本人的基础算法学习以及LeetCode刷题记录#xff0c;按专题划分每题主要记录#xff1a;#xff08;1#xff09;本人解法 本人屎山代码#xff1b;#xff08;2#xff09;优质解法 优质代码#xff1b;#xff…前言说明
本专栏主要记录本人的基础算法学习以及LeetCode刷题记录按专题划分每题主要记录1本人解法 本人屎山代码2优质解法 优质代码3精益求精更好的解法和独特的思想如果有的话文章中的理解仅为个人理解。如有错误感谢纠错 个人简介努力学习ing 本专栏C刷题专栏 其他专栏C语言入门基础python入门基础C学习笔记Linux CSDN主页 愚润泽 你可以点击下方链接进行该专题内不同子专题的学习
点击链接开始学习双指针(1)双指针(2)双指针(3)双指针(4)滑动窗口(1)滑动窗口(2)滑动窗口(3)滑动窗口(4)二分查找(1)二分查找(2)前缀和(1)前缀和(2)前缀和(3)位运算(1)位运算(2)模拟算法快速排序归并排序链表哈希表字符串栈队列 宽搜优先级队列BFS 解决 FloodFillBFS 解决最短路径多源 BFSBFS 解决拓扑排序
题单汇总链接点击 → 题单汇总暂时未整理因为还没刷完 题目导论——多源 BFS542. 01 矩阵优质解1020. 飞地的数量个人解1765. 地图中的最高点个人解1162. 地图分析个人解导论——多源 BFS
多元最短路问题起始点有多个去同一个终点
前提BFS解决的最短路问题都是边权为 1 的解法一把多源最短路问题转换成若干个单源最短路问题——暴力枚举每个起点对每个起点进行单源最短路问题分析【但是时间复杂度高超时】解法二把所有的源点当成一个“超级源点”——从“超级源点”出发一次单源最短路问题 如何求“超级源点” 把所有的起始节点加入到队列中即第一层由单源的一个节点变成了多源的多个节点只不过这些节点都属于第一层罢了多个源点可能开辟出不同的路在不同的路中后到达的节点会被hash淘汰
542. 01 矩阵
题目链接https://leetcode.cn/problems/01-matrix/description/ 优质解
思路
解法一把 1 当成起点的话要遍历整个矩阵解法二把 0 当起点从所有 0 走到某一个 1 的最短距离 从 1 走到最近 0 的距离
代码
class Solution {
public:vectorvectorint updateMatrix(vectorvectorint mat) {int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};int m mat.size(), n mat[0].size();queuepairint, int q;vectorvectorint dis(m, vectorint(n, -1));// 先获得超级源点for(int i 0 ; i m; i){for(int j 0; j n; j){if(mat[i][j] 0){q.push({i, j});dis[i][j] 0;}}}// 从超级源点开始扩展while(q.size()){// int sz q.size(); 为什么可以不计算 sz // 因为之前的 sz 是和 step 配合使用的我们通过sz知道是在哪一层// 但是现在下一个dis中填写的内容可以根据上一个dis中的内容决定// 并且一定是上一层的节点pop出去以后才会处理上一层加入的后续节点auto [a, b] q.front();q.pop();for(int j 0; j 4; j){int x a dx[j], y b dy[j];if(x 0 x m y 0 y n dis[x][y] -1){dis[x][y] dis[a][b] 1;q.push({x, y}); }}}return dis;}
};时间复杂度O(m∗n)O(m*n)O(m∗n) 空间复杂度O(m∗n)O(m*n)O(m∗n) 1020. 飞地的数量
题目链接https://leetcode.cn/problems/number-of-enclaves/description/
个人解
屎山代码
class Solution {
public:int numEnclaves(vectorvectorint grid) {// 这就是 floodfill// 只不过从边缘 1 开始先标记连通块的时候可以使用 多源 bfs 标记int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};int m grid.size(), n grid[0].size();queuepairint, int q;for(int i 0; i m; i){for(int j 0; j n; j){if((i 0 || i m - 1 || j 0 || j n - 1) grid[i][j]){grid[i][j] 0;q.push({i, j});}}}while(q.size()){auto [a, b] q.front();q.pop();for(int i 0; i 4; i){int x a dx[i], y b dy[i];if(x 0 x m y 0 y n grid[x][y]){grid[x][y] 0;q.push({x, y});}}}int ans 0;for(int i 0; i m; i){for(int j 0; j n; j){if(grid[i][j])ans;}}return ans;}
};时间复杂度O(m∗n)O(m*n)O(m∗n) 空间复杂度O(m∗n)O(m*n)O(m∗n) 1765. 地图中的最高点
题目链接https://leetcode.cn/problems/map-of-highest-peak/description/
个人解
思路
和 01 矩阵一样
屎山代码
class Solution {
public:vectorvectorint highestPeak(vectorvectorint isWater) {// 自行安排出最高高度// 以水域为起点能到达的最远的陆地最高(走最短路径)int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};int m isWater.size(), n isWater[0].size();vectorvectorint high(m, vectorint(n, -1));queuepairint, int q;for(int i 0; i m; i){for(int j 0; j n; j){if(isWater[i][j]){q.push({i, j});high[i][j] 0;}}}while(q.size()){auto [a, b] q.front();q.pop();for(int i 0; i 4; i){int x a dx[i], y b dy[i];if(x 0 x m y 0 y n high[x][y] -1){high[x][y] high[a][b] 1;q.push({x, y});}}}return high;}
};时间复杂度O(m∗n)O(m*n)O(m∗n) 空间复杂度O(m∗n)O(m*n)O(m∗n) 1162. 地图分析
题目链接https://leetcode.cn/problems/as-far-from-land-as-possible/description/
个人解
思路
// 海洋到最近的陆地的距离 陆地到海洋的最短路径
// 以陆地为起始点做 bfs用时14:00 屎山代码
class Solution {
public:int maxDistance(vectorvectorint grid) {int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};int m grid.size(), n grid[0].size();queuepairint, int q;for(int i 0; i m; i){for(int j 0; j n; j){if(grid[i][j])q.push({i, j});}}int ans 0;while(q.size()){auto [a, b] q.front();q.pop();for(int i 0; i 4; i){int x a dx[i], y b dy[i];if(x 0 x m y 0 y n !grid[x][y]){grid[x][y] grid[a][b] 1;ans max(ans, grid[x][y]);q.push({x, y});}}}return ans - 1; // 因为第一次是 1 - 2但其实是 1}
};时间复杂度O(m∗n)O(m*n)O(m∗n) 空间复杂度O(m∗n)O(m*n)O(m∗n) 我的分享也就到此结束啦 要是我的分享也能对你的学习起到帮助那简直是太酷啦 若有不足还请大家多多指正我们一起学习交流 公主王子点赞→收藏⭐→关注 感谢大家的观看和支持祝大家都能得偿所愿天天开心
