铜陵网站制作,中国城乡建设部证件查询网站,营销型网站的缺点,wordpress设置网站关键字本文涉及的基础知识点
二分查找算法合集
作者推荐
动态规划LeetCode2552#xff1a;优化了6版的1324模式
题目
给你一个下标从 1 开始的二进制矩阵#xff0c;其中 0 表示陆地#xff0c;1 表示水域。同时给你 row 和 col 分别表示矩阵中行和列的数目。
一开始在第 0 …本文涉及的基础知识点
二分查找算法合集
作者推荐
动态规划LeetCode2552优化了6版的1324模式
题目
给你一个下标从 1 开始的二进制矩阵其中 0 表示陆地1 表示水域。同时给你 row 和 col 分别表示矩阵中行和列的数目。
一开始在第 0 天整个 矩阵都是 陆地 。但每一天都会有一块新陆地被 水 淹没变成水域。给你一个下标从 1 开始的二维数组 cells 其中 cells[i] [ri, ci] 表示在第 i 天第 ri 行 ci 列下标都是从 1 开始的陆地会变成 水域 也就是 0 变成 1 。
你想知道从矩阵最 上面 一行走到最 下面 一行且只经过陆地格子的 最后一天 是哪一天。你可以从最上面一行的 任意 格子出发到达最下面一行的 任意 格子。你只能沿着 四个 基本方向移动也就是上下左右。 请返回只经过陆地格子能从最 上面 一行走到最 下面 一行的 最后一天 。 示例 1 输入row 2, col 2, cells [[1,1],[2,1],[1,2],[2,2]] 输出2 解释上图描述了矩阵从第 0 天开始是如何变化的。 可以从最上面一行到最下面一行的最后一天是第 2 天。 示例 2 输入row 2, col 2, cells [[1,1],[1,2],[2,1],[2,2]] 输出1 解释上图描述了矩阵从第 0 天开始是如何变化的。 可以从最上面一行到最下面一行的最后一天是第 1 天。 示例 3 输入row 3, col 3, cells [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]] 输出3 解释上图描述了矩阵从第 0 天开始是如何变化的。 可以从最上面一行到最下面一行的最后一天是第 3 天。 参数范围 2 row, col 2 * 104 4 row * col 2 * 104 cells.length row * col 1 ri row 1 ci col cells 中的所有格子坐标都是 唯一 的。
二分查找分析
时间复杂度
O(nlogn) 二分查找O(logn)并集查找O(n)。
分析
随着天数的增大逐步从能过变成不能过。左闭右开空间。 并集查找的时候只需要连接左边和上边。第一行下移就是第二行上移。
代码
核心代码
class Solution { public: int latestDayToCross(int row, int col, vectorvector cells) { m_r row; m_c col; int left 0, right m_r * m_c ; while (right - left 1) { const auto mid left (right - left) / 2; vectorvector mat(row, vector(col)); for (int i 0; i mid; i) { mat[cells[i][0]-1][cells[i][1]-1] 1; } if (Can(mat)) { left mid; } else { right mid; } } return left; } bool Can(const vectorvector mat) { const int n m_r*m_c; CUnionFind uf(n 2); for (int r 0; r m_r; r) { for (int c 0; c m_c; c) { if (1 mat[r][c]) { continue; } if ((0 ! r) (0 mat[r - 1][c])) { uf.Union(r * m_c c, (r - 1) * m_c c); } if ((0 ! c) (0 mat[r][c - 1])) { uf.Union(r * m_c c, r * m_c c - 1); } } } for (int c 0; c m_c; c) { if (0 mat[0][c]) { uf.Union(n, c); } if (0 mat[m_r - 1][c]) { uf.Union(n1, (m_r - 1) * m_c c); } } return uf.IsConnect(n, n 1); } int m_r,m_c; };
测试用例
template void Assert(const vector v1, const vector v2) { if (v1.size() ! v2.size()) { assert(false); return; } for (int i 0; i v1.size(); i) { assert(v1[i] v2[i]); } }
template void Assert(const T t1, const T t2) { assert(t1 t2); }
int main() { int row, col, res; vectorvector cells; { row 2, col 2, cells { {1,1},{2,1},{1,2},{2,2} }; Solution slu; auto res slu.latestDayToCross(row, col, cells); Assert(2, res); } { row 2, col 2, cells { {1,1},{1,2},{2,1},{2,2} }; Solution slu; auto res slu.latestDayToCross(row, col, cells); Assert(1, res); } { row 6, col 2, cells { {4, 2}, { 6,2 }, { 2,1 }, { 4,1 }, { 6,1 }, { 3,1 }, { 2,2 }, { 3,2 }, { 1,1 }, { 5,1 }, { 5,2 }, { 1,2 } }; Solution slu; auto res slu.latestDayToCross(row, col, cells); Assert(3, res); } //CConsole::Out(res);}
逆序思考
反向思考水慢慢变成陆地最晚什么时候连通陆地。 时间复杂度(n)
代码
class CUnionFind
{
public:CUnionFind(int iSize) :m_vNodeToRegion(iSize){for (int i 0; i iSize; i){m_vNodeToRegion[i] i;}m_iConnetRegionCount iSize;}int GetConnectRegionIndex(int iNode){int iConnectNO m_vNodeToRegion[iNode];if (iNode iConnectNO){return iNode;}return iConnectNO GetConnectRegionIndex(iConnectNO);}void Union(int iNode1, int iNode2){const int iConnectNO1 GetConnectRegionIndex(iNode1);const int iConnectNO2 GetConnectRegionIndex(iNode2);if (iConnectNO1 iConnectNO2){return;}m_iConnetRegionCount--;if (iConnectNO1 iConnectNO2){UnionConnect(iConnectNO1, iConnectNO2);}else{UnionConnect(iConnectNO2, iConnectNO1);}}bool IsConnect(int iNode1, int iNode2){return GetConnectRegionIndex(iNode1) GetConnectRegionIndex(iNode2);}int GetConnetRegionCount()const{return m_iConnetRegionCount;}vectorint GetNodeCountOfRegion()//各联通区域的节点数量{const int iNodeSize m_vNodeToRegion.size();vectorint vRet(iNodeSize);for (int i 0; i iNodeSize; i){vRet[GetConnectRegionIndex(i)];}return vRet;}std::unordered_mapint, vectorint GetNodeOfRegion(){std::unordered_mapint, vectorint ret;const int iNodeSize m_vNodeToRegion.size();for (int i 0; i iNodeSize; i){ret[GetConnectRegionIndex(i)].emplace_back(i);}return ret;}
private:void UnionConnect(int iFrom, int iTo){m_vNodeToRegion[iFrom] iTo;}vectorint m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引为了增加可理解性用最小索引int m_iConnetRegionCount;
};class Solution {
public:int latestDayToCross(int row, int col, vectorvectorint cells) {m_r row;m_c col;const int n m_r * m_c;CUnionFind uf(n 2);for (int c 0; c m_c; c){uf.Union(n, c);uf.Union(n 1, (m_r - 1) * m_c c);}vectorvectorint mat(row, vectorint(col,1));for (int i cells.size() - 1; i 0; i--){const int r cells[i][0] - 1;const int c cells[i][1] - 1;mat[r][c] 0;auto Add [](const int rNew, const int cNew){if ((rNew 0) || (rNew m_r)){return;}if ((cNew 0) || (cNew m_c)){return;}if (0 mat[rNew][cNew]){uf.Union(r * m_c c, rNew * m_c cNew);}};Add(r 1, c);Add(r - 1, c);Add(r, c - 1);Add(r, c 1);if (uf.IsConnect(n, n 1)){return i ;}} return 0;}int m_r,m_c;
};2023年3月旧代码
class Solution { public: int latestDayToCross(int row, int col, vectorvector cells) { m_r row; m_c col; int left 0,r cells.size()1 ; while (r left 1) { int iMid left (r - left) / 2; vectorvector mat(m_r, vector(m_c)); for (int i 0; i iMid; i) { mat[cells[i][0]-1][cells[i][1]-1] 1; } if (bfs(mat)) { left iMid; } else { r iMid; } } return left; } bool bfs(const vectorvector mat) { std::queuestd::pairint, int queCanViste; std::unordered_mapint, std::unordered_set setDo; for (int c 0; c m_c; c) { Add(queCanViste, setDo, 0, c, mat); } while (queCanViste.size()) { const int r queCanViste.front().first; const int c queCanViste.front().second; if (r m_r - 1) { return true; } queCanViste.pop(); Add(queCanViste, setDo, r1, c, mat); Add(queCanViste, setDo, r-1, c, mat); Add(queCanViste, setDo, r , c1, mat); Add(queCanViste, setDo, r, c-1, mat); } return false; } void Add(std::queuestd::pairint, int queCanViste, std::unordered_mapint, std::unordered_set setDo, int r, int c,const vectorvector mat) { if ((r 0) || (r m_r)) { return; } if ((c0) || (c m_c)) { return; } if (1 mat[r][c]) { return; } if (setDo[r].count©) { return; } queCanViste.emplace(r, c); setDo[r].emplace©; } int m_r, m_c; };
2023年9月旧代码
class Solution { public: int latestDayToCross(int row, int col, vectorvector cells) { m_c col; int iMaskNum row * col; vectorvector grid(row, vector(col)); for (auto v : cells) { v[0]–; v[1]–; grid[v[0]][v[1]] 1; } CUnionFind uf(iMaskNum2);//增加两个特殊端点; iMaskNum 连接所有第0行 iMaskNum1 连接多有最后一行 auto Add [row,this,grid,uf](int iMask, int r, int c) { if ((r 0) || (r row)) { return; } if ((c 0) || (c m_c)) { return; } if (1 grid[r][c]) { return; } uf.Union(iMask, Mask(r, c)); }; for (int r 0; r row; r) { for (int c 0; c m_c; c) { if (1 grid[r][c]) { continue; } const int mask Mask(r, c); Add(mask, r 1, c); Add(mask, r, c 1); } } for (int c 0; c m_c; c) { uf.Union(iMaskNum, Mask(0, c)); uf.Union(iMaskNum1, Mask(row-1, c)); } for (int i cells.size() - 1; i 0; i–) { if (uf.IsConnect(iMaskNum, iMaskNum1)) { return i1; } const auto v cells[i]; grid[v[0]][v[1]] 0; const int mask Mask(v[0], v[1]); Add(mask, v[0] 1, v[1]); Add(mask, v[0], v[1] 1); Add(mask, v[0] - 1, v[1]); Add(mask, v[0], v[1] - 1); } return 0; } inline int Mask(int r, int c) { return r * m_c c; } int m_c; };
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境
VS2022 C17
