当前位置: 首页 > news >正文

广州网站建设第一公司百度产品大全入口

广州网站建设第一公司,百度产品大全入口,杭州软件开发外包公司,华升建设集团有限公司网站给一个0 1矩阵,1代表是陆地,0代表海洋, 如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 岛屿问题: 相邻陆地可以组成一个岛屿(相邻:上下左右) 判断岛屿个数。 C 解决方案 #include &…

        给一个0 1矩阵,1代表是陆地,0代表海洋, 如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 岛屿问题: 相邻陆地可以组成一个岛屿(相邻:上下左右) 判断岛屿个数。

 C++ 解决方案

#include <iostream>
#include <vector>using namespace std;void dfs(vector<vector<int>>& grid, int i, int j) {if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0) {return;}grid[i][j] = 0; // Mark the current cell as visited// Visit all four adjacent cellsdfs(grid, i - 1, j); // Updfs(grid, i + 1, j); // Downdfs(grid, i, j - 1); // Leftdfs(grid, i, j + 1); // Right
}int numIslands(vector<vector<int>>& grid) {int count = 0;for (int i = 0; i < grid.size(); ++i) {for (int j = 0; j < grid[0].size(); ++j) {if (grid[i][j] == 1) {++count;dfs(grid, i, j); // Start DFS from the current cell to mark all connected 1s as visited}}}return count;
}int main() {vector<vector<int>> grid = {{1, 1, 0, 0, 0},{1, 1, 0, 0, 1},{0, 0, 1, 0, 1},{0, 0, 0, 1, 1}};cout << "Number of islands: " << numIslands(grid) << endl;return 0;
}

Python 解决方案 

def dfs(grid, i, j):if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:returngrid[i][j] = 0  # Mark the current cell as visited# Visit all four adjacent cellsdfs(grid, i - 1, j)  # Updfs(grid, i + 1, j)  # Downdfs(grid, i, j - 1)  # Leftdfs(grid, i, j + 1)  # Rightdef num_islands(grid):count = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == 1:count += 1dfs(grid, i, j)  # Start DFS from the current cell to mark all connected 1s as visitedreturn count# Example usage
grid = [[1, 1, 0, 0, 0],[1, 1, 0, 0, 1],[0, 0, 1, 0, 1],[0, 0, 0, 1, 1]
]print("Number of islands:", num_islands(grid))

解释

  1. 深度优先搜索(DFS)
    • dfs函数用于遍历所有与当前陆地相连的陆地,并将它们标记为已访问(即0)。
    • 每当遇到一个未访问的陆地(即值为1的单元格),我们增加岛屿计数,并调用dfs来标记所有相连的陆地。
  2. 遍历矩阵
    • numIslands函数遍历整个矩阵,每当遇到一个新的陆地时,调用dfs函数,并增加岛屿计数。

复杂度

  • 时间复杂度:O(M * N),其中M是矩阵的行数,N是矩阵的列数,因为我们需要遍历整个矩阵一次。
  • 空间复杂度:O(M * N)(在极端情况下,递归调用栈的深度可能达到这个级别),但由于DFS的深度通常较小,实际空间占用可能会更小。

http://www.ritt.cn/news/18594.html

相关文章:

  • 做网站最好软件网络搜索优化
  • 做网站外包哪家好游戏推广一个月能拿多少钱
  • 网站建设费用要多少郑州seo顾问外包公司
  • 做网站工资多少钱网站关键词优化软件
  • 网站推广引流软件青岛seo排名公司
  • 类似于pinterest的设计网站张家界网站seo
  • DW做的网页用网站打不开进入百度搜索首页
  • python可以做网站后台吗推广关键词排名查询
  • 哪个网站有做视频转场的素材免费b站推广网站短视频
  • 做图网站有哪些内容东莞seo培训
  • 网站建设的优势备案查询站长之家
  • 石家庄做家教网站上海seo网站优化软件
  • dedecms做门户网站今日热点新闻事件摘抄50字
  • wordpress 用户中心厦门百度seo
  • 做艺术品拍卖的网站seo研究中心晴天
  • 微软asp.net mvc4 web企业网站开发实战课程自己如何建立网站
  • 最好的网站建设组织站长推荐
  • 国家工商网站查询网站服务器是什么意思
  • 做柱状图好看的网站百度反馈中心
  • 2021年中国十大电商平台排名优化设计的答案
  • 上海网站备案流程百度竞价排名背后的伦理问题
  • 织梦网站做关键词江北seo综合优化外包
  • 镇江公司做网站企业seo服务
  • 成人高考条件软件排名优化
  • 导航网站怎么做西安seo优化顾问
  • 做soho要不要注册网站网络推广赚钱项目
  • 网络推广培训如何商品seo优化是什么意思
  • 邯郸建移动网站费用百度注册公司地址
  • 武汉seo网站排名网站定制的公司
  • 石家庄铁路网上海搜索优化推广