CodingNotes(01)

岛屿系列题目

695.岛屿的最大面积

我的思路

最简单的想法

  1. 有一个函数输入是某个为1的点,然后去找这个点所在岛屿的面积。
  2. 函数计算的方式是DFS,向四周遍历直到碰到0。
  3. 遍历所有为1的点取最大值。

Code

第一版code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ret = -1;
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j]==1)
{
int tmp = islandSize(grid, i, j);
ret = (tmp>ret) ? tmp : ret;
}

}
}

return ret;
}

int islandSize(vector<vector<int>>& grid, int x, int y)
{
if(x < 0 || x >=grid.size() || y<0 || y>=grid[0].size()) return 0;
if(grid[x][y] == 1)
return 1 + islandSize(grid, x+1, y) + islandSize(grid, x-1, y)
+ islandSize(grid, x, y+1) + islandSize(grid, x, y-1);
else
return 0;
}
};

但是这里没有考虑到重复访问的问题,没有将已经计数过的陆地置为0,陷入无限递归而导致栈溢出。
修改后的code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ret = 0; // 从0开始,因为面积不能是负数
for(int i = 0; i < grid.size(); i++) {
for(int j = 0; j < grid[0].size(); j++) {
if(grid[i][j] == 1) {
int tmp = islandSize(grid, i, j);
ret = std::max(tmp, ret);
}
}
}
return ret;
}

int islandSize(vector<vector<int>>& grid, int x, int y) {
// 检查边界
if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == 0) {
return 0;
}

// 标记单元格为已访问
grid[x][y] = 0;

// 对相邻单元格进行递归调用
return 1 + islandSize(grid, x + 1, y) + islandSize(grid, x - 1, y)
+ islandSize(grid, x, y + 1) + islandSize(grid, x, y - 1);
}
};

1905. 统计子岛屿

我的思路

  1. 同上题 不过dfs函数的返回值改为bool类型,基本思想是边遍历边判断。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
int ret = 0;
for(int i=0;i<grid2.size();i++)
for(int j=0;j<grid2[0].size();j++)
{
if(grid2[i][j] == 1)
{
auto tmp = isVaildIsland(grid1, grid2, i, j);
if(tmp) ret++;
}
}
return ret;
}

bool isVaildIsland(vector<vector<int>>& grid1, vector<vector<int>>& grid2, int x, int y) {
// 检查边界
if(x < 0 || x >= grid2.size() || y < 0 || y >= grid2[0].size()) {
return true;
}
// if(grid1[x][y] ^ grid2[x][y]) return false;

if(grid2[x][y]==0) return true;
// 标记单元格为已访问
grid2[x][y] = 0;
bool flag = true;
if(grid1[x][y] == 0)
{
flag = false;
//return false;
}

auto tmp1 = isVaildIsland(grid1, grid2, x + 1, y);
auto tmp2 = isVaildIsland(grid1, grid2, x - 1, y);
auto tmp3 = isVaildIsland(grid1, grid2, x, y + 1) ;
auto tmp4 = isVaildIsland(grid1, grid2, x, y - 1);

return flag&&tmp1&&tmp2&&tmp3&&tmp4;
// return tmp1&&tmp2&&tmp3&&tmp4;
}
};

一开始踩了几个坑

  1. 首先是觉得grid1和grid2的不同时就返回false,显然当grid1==1 && grid2 == 0 时是不成立的
  2. 其次是grid1 == 0 && grid2 == 1时不能直接返回false,否则递归会直接中止。

1020. 飞地的数量

我的思路

先把所有和边界联通的陆地都沉了,然后再去统计剩余的陆地数量。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution{
public:
int numEnclaves(vector<vector<int>>& grid) {
int ret = 0;
int row = grid.size();
int col = grid[0].size();


for(int i=0;i<col;i++)
{
if(grid[0][i]==1)
{
turn2sea(grid, 0, i);
}
if(grid[row-1][i]==1)
{
turn2sea(grid, row-1, i);
}
}
for(int i=0;i<row;i++)
{
if(grid[i][0]==1)
{
turn2sea(grid, i, 0);
}
if(grid[i][col-1]==1)
{
turn2sea(grid, i, col-1);
}
}


for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
{
if(grid[i][j]==1)
{
ret++;
}
}
return ret;
}

void turn2sea(vector<vector<int>>& grid, int x, int y)
{
if(x<0|| y<0|| x>=grid.size() || y>=grid[0].size() ||grid[x][y]==0 ) return;
else
{
grid[x][y]=0;
turn2sea(grid, x+1,y);
turn2sea(grid, x-1,y);
turn2sea(grid, x,y+1);
turn2sea(grid, x,y-1);
return ;
}
}


};

CodingNotes(01)
https://arcanus.red/2024/11/17/CodingNotes-01/
作者
Helix
发布于
2024年11月17日
许可协议