【二分查找】LeetCode1970:你能穿过矩阵的最后一天

简介: 【二分查找】LeetCode1970:你能穿过矩阵的最后一天

题目

给你一个下标从 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, vector& 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;
vector 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 vector& 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(n+1, (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;
vector 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;
  }
  vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
  {
    const int iNodeSize = m_vNodeToRegion.size();
    vector<int> vRet(iNodeSize);
    for (int i = 0; i < iNodeSize; i++)
    {
      vRet[GetConnectRegionIndex(i)]++;
    }
    return vRet;
  }
  std::unordered_map<int, vector<int>> GetNodeOfRegion()
  {
    std::unordered_map<int, vector<int>> 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;
  }
  vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引,为了增加可理解性,用最小索引
  int m_iConnetRegionCount;
};
class Solution {
public:
  int latestDayToCross(int row, int col, vector<vector<int>>& 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);
    }
    vector<vector<int>> mat(row, vector<int>(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, vector& cells) {
m_r = row;
m_c = col;
int left = 0,r = cells.size()+1 ;
while (r > left + 1)
{
int iMid = left + (r - left) / 2;
vector 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 vector& mat)
{
std::queue> queCanViste;
std::unordered_map 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, r+1, c, mat);
Add(queCanViste, setDo, r-1, c, mat);
Add(queCanViste, setDo, r , c+1, mat);
Add(queCanViste, setDo, r, c-1, mat);
}
return false;
}
void Add(std::queue>& queCanViste, std::unordered_map& setDo, int r, int c,const vector& mat)
{
if ((r < 0) || (r >= m_r))
{
return;
}
if ((c<0) || (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, vector& cells) {
m_c = col;
int iMaskNum = row * col;
vector grid(row, vector(col));
for (auto& v : cells)
{
v[0]–;
v[1]–;
grid[v[0]][v[1]] = 1;
}
CUnionFind uf(iMaskNum+2);//增加两个特殊端点; iMaskNum 连接所有第0行 iMaskNum+1 连接多有最后一行
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(iMaskNum+1, Mask(row-1, c));
}
for (int i = cells.size() - 1; i >= 0; i–)
{
if (uf.IsConnect(iMaskNum, iMaskNum+1))
{
return i+1;
}
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 C++17

或者 操作系统:win10 开发环境:

VS2022 C++17



相关文章
|
2月前
|
存储 算法 NoSQL
LeetCode第73题矩阵置零
文章介绍了LeetCode第73题"矩阵置零"的解法,通过使用矩阵的第一行和第一列作为标记来记录哪些行或列需要置零,从而在不增加额外空间的情况下解决问题。
LeetCode第73题矩阵置零
|
2月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
39 6
|
2月前
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
25 4
|
2月前
|
算法 Python
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
19 0
【Leetcode刷题Python】73. 矩阵置零
|
2月前
|
Python
【Leetcode刷题Python】704. 二分查找
解决LeetCode "二分查找" 问题的Python实现代码。
13 0
|
2月前
|
算法 索引 Python
【Leetcode刷题Python】34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)
解决LeetCode "在排序数组中查找元素的第一个和最后一个位置" 问题的方法。第一种方法是使用两次二分查找,首先找到目标值的最左边界,然后找到最右边界。第二种方法是利用Python的list.index()方法,先正序找到起始位置,再逆序找到结束位置,并给出了两种方法的Python实现代码。
48 0
|
4月前
|
算法
力扣经典150题第三十七题:矩阵置零
力扣经典150题第三十七题:矩阵置零
27 2
|
4月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
4月前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
|
4月前
力扣随机一题 6/28 数组/矩阵
力扣随机一题 6/28 数组/矩阵
36 0