首页 / 更多教程 / LeetCode 200, 694
LeetCode 200, 694
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode 200, 694，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3096字，纯文字阅读大概需要5分钟。
内容图文
典型的搜索问题。694是200的拓展，多了怎么保存岛屿的特征的问题。两道题既可以用DFS做，也可以用BFS做。
解题中用到了 pair<int, int> 和 make_pair(i, j) 来记录坐标，相较于自己创建一个结构体，更加方便。auto关键字，用于申明类型，类型会自动推断，如果类型比较复杂，用auto申明会方便不少。
DFS和BFS结构都比较固定，DFS的写法与之前总结的框架结构保持一致，熟能生巧。
200. Number of Islands
DFS:
class
Solution {
public
:
int di[4]={0,0,1,-1};
int dj[4]={1,-1,0,0};
int numIslands(vector<vector<char>>& 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);
}
}
}
return count;
}
void dfs(vector<vector<char>> &grid, int i, int j){
if (i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || grid[i][j]!=‘1‘) return;
grid[i][j] = ‘0‘;
for (int k=0;k<4;++k){
dfs(grid,i+di[k],j+dj[k]);
}
}
};
BFS:
class
Solution {
public
:
int di[4]={0,0,1,-1};
int dj[4]={1,-1,0,0};
int numIslands(vector<vector<char>>& 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;
queue<pair<int,int>> q;
q.push({i,j});
grid[i][j] = ‘0‘;
while (!q.empty()){
auto tmp=q.front(); q.pop();
for (int k=0;k<4;++k){
int ii=tmp.first+di[k], jj=tmp.second+dj[k];
if (ii>=0 && ii<grid.size() && jj>=0 && jj<grid[0].size() && grid[ii][jj]==‘1‘){
q.push({ii,jj});
grid[ii][jj] = ‘0‘;
}
}
}
}
}
}
return count;
}
};
694. Number of Distinct Islands
可以通过记录相对于搜索起点的相对坐标来判断岛屿是否相同（搜索的顺序都是固定的）。
DFS:
class
Solution {
public
:
set<vector<vector<int>>> islands;
int di[4]={0,0,1,-1};
int dj[4]={1,-1,0,0};
int numDistinctIslands(vector<vector<int>>& grid) {
for (int i=0;i<grid.size();++i){
for (int j=0;j<grid[0].size();++j){
if (grid[i][j]==1){
vector<vector<int>> island;
dfs(grid,i,j,i,j,island);
islands.insert(island);
}
}
}
return islands.size();
}
void dfs(vector<vector<int>>& grid, int i0, int j0, int i, int j, vector<vector<int>> &island){
if (i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || grid[i][j]!=1) return;
island.push_back({i-i0,j-j0});
grid[i][j] = 0;
for (int k=0;k<4;++k){
dfs(grid,i0,j0,i+di[k],j+dj[k],island);
}
}
};
BFS:
class
Solution {
public
:
set<vector<pair<int,int>>> islands;
int di[4]={0,0,1,-1};
int dj[4]={1,-1,0,0};
int numDistinctIslands(vector<vector<int>>& grid) {
for (int i=0;i<grid.size();++i){
for (int j=0;j<grid[0].size();++j){
if (grid[i][j]==1){
vector<pair<int,int>> island;
queue<pair<int,int>> q;
q.push({i,j});
grid[i][j] = 0;
island.push_back({0,0});
while (!q.empty()){
auto tmp=q.front(); q.pop();
for (int k=0;k<4;++k){
int ii=tmp.first+di[k], jj=tmp.second+dj[k];
if (ii>=0 && ii<grid.size() && jj>=0 && jj<grid[0].size() && grid[ii][jj]==1){
q.push({ii,jj});
grid[ii][jj] = 0;
island.push_back({ii-i,jj-j});
}
}
}
islands.insert(island);
}
}
}
return islands.size();
}
};
原文：https://www.cnblogs.com/hankunyan/p/8977250.html
内容总结
以上是互联网集市为您收集整理的LeetCode 200, 694全部内容，希望文章能够帮你解决LeetCode 200, 694所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。