当前位置:网站首页>Leetcode (695) - the largest area of an island
Leetcode (695) - the largest area of an island
2022-07-05 20:19:00 【SmileGuy17】
Leetcode(695)—— The largest area of the island
subject
Give you a size of m × n m \times n m×n The binary matrix of grid .
Islands It's made up of some neighboring 1 ( Representing land ) A combination of components , there 「 adjacent 」 Ask for two 1 Must be in In four horizontal or vertical directions adjacent . You can assume grid The four edges of are all 0( Representative water ) Surrounded by a .
The area of the island is the value of 1 Number of cells .
Calculate and return grid The largest island area in . If there were no Islands , Then the return area is 0 .
Example 1:
Input :grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output :6
explain : The answer should not be 11 , Because the island can only contain horizontal or vertical 1 .
Example 2:
Input :grid = [[0,0,0,0,0,0,0,0]]
Output :0
Tips :
- m == grid.length
- n == grid[i].length
- 1 1 1 <= m, n <= 50 50 50
- grid[i][j] by 0 0 0 or 1 1 1
Answer key
Method 1 :DFS( Recursive writing )
Ideas
- We want to know the area of each connected shape in the grid , And then take the maximum .
- If we are on a land , With 4 4 4 Explore every land connected with it in two directions ( And the land connected to these lands ), Then the total amount of land explored will be the area of the connected shape .
- To ensure that no more than one visit is made to each land , Every time we pass a piece of land , Set the value of this land to 0 0 0. So we won't visit the same land many times .
Here we use a trick , For traversal in four directions , You can create an array [-1, 0, 1, 0, -1], Every two adjacent digits is one of the four directions up, down, left and right .
In the auxiliary function , One important thing to note is that recursive search in auxiliary functions , Determination of boundary conditions . There are generally two ways to write boundary determination , One is to determine whether it crosses the boundary first , Only if it is legal, can we carry out the next search ( That is, the judgment is placed before calling the recursive function ); The other is to search for the next step regardless of three, seven and twenty-one , Judge whether it is legal when the next search starts ( That is, the judgment is placed on the first line of the auxiliary function ). Here we show these two ways .
Code implementation
Leetcode Official explanation :
class Solution {
int dfs(vector<vector<int>>& grid, int cur_i, int cur_j) {
if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
return 0;
}
grid[cur_i][cur_j] = 0;
int di[4] = {
0, 0, 1, -1};
int dj[4] = {
1, -1, 0, 0};
int ans = 1;
for (int index = 0; index != 4; ++index) {
int next_i = cur_i + di[index], next_j = cur_j + dj[index];
ans += dfs(grid, next_i, next_j);
}
return ans;
}
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans = 0;
for (int i = 0; i != grid.size(); ++i) {
for (int j = 0; j != grid[0].size(); ++j) {
ans = max(ans, dfs(grid, i, j));
}
}
return ans;
}
};
My own :
class Solution {
void DFS(vector<vector<int>>& grid, int x, int y, int& area){
if(0 > x || x >= grid[0].size() || y >= grid.size() || 0 > y) return;
if(grid[y][x] == 1){
// The up and down or so
area += 1;
grid[y][x] = 0; // Set as 0 Prevent revisiting this point
DFS(grid, x-1, y, area);
DFS(grid, x+1, y, area);
DFS(grid, x, y-1, area);
DFS(grid, x, y+1, area);
}
}
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans = 0, area, yn = grid.size(), xn = grid[0].size();
for(int y = 0; y < yn; y++){
for(int x = 0; x < xn; x++){
if(grid[y][x] == 1){
area = 0;
DFS(grid, x, y, area);
ans = ans < area? area: ans;
}
}
}
return ans;
}
};
Complexity analysis
Time complexity : O ( m × n ) O(m×n) O(m×n). among m m m Is the number of rows in a given grid , n n n It's the number of columns . We visited each originally 1 At most once .
Spatial complexity : O ( m × n ) O(m \times n) O(m×n), The depth of recursion is most likely the size of the entire grid , Therefore, it is possible to use O ( m × n ) O(m \times n) O(m×n) Stack space of .
Method 2 :DFS + Auxiliary stack ( Iterative writing )
Ideas
The principle is the same as method 1 , Only the implementation adopts iteration rather than recursion , And use the stack to help realize .
- Method 1 indicates which land you want to traverse next by calling a function , Let the next function access these lands . And method 2 puts the land you want to traverse next in the stack , Then visit these lands when taking them out .
- When visiting every piece of land , We will explore four directions around it , Find land that has not been visited , Add to stack stack \textit{stack} stack in ;
- in addition , Just stack stack \textit{stack} stack Not empty , It means we still have land to visit , Then take an element from the stack and access .
Code implementation
Leetcode Official explanation :
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans = 0;
for (int i = 0; i != grid.size(); ++i) {
for (int j = 0; j != grid[0].size(); ++j) {
int cur = 0;
stack<int> stacki;
stack<int> stackj;
stacki.push(i);
stackj.push(j);
while (!stacki.empty()) {
int cur_i = stacki.top(), cur_j = stackj.top();
stacki.pop();
stackj.pop();
if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
continue;
}
++cur;
grid[cur_i][cur_j] = 0;
int di[4] = {
0, 0, 1, -1};
int dj[4] = {
1, -1, 0, 0};
for (int index = 0; index != 4; ++index) {
int next_i = cur_i + di[index], next_j = cur_j + dj[index];
stacki.push(next_i);
stackj.push(next_j);
}
}
ans = max(ans, cur);
}
}
return ans;
}
};
My own :
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans = 0, area, yn = grid.size(), xn = grid[0].size();
stack<pair<int, int>> island;
pair<int, int> tmp;
for(int y = 0; y < yn; y++){
for(int x = 0; x < xn; x++){
if(grid[y][x] == 1){
area = 0;
island.push(make_pair(y, x));
while(!island.empty()){
tmp.first = island.top().first;
tmp.second = island.top().second;
island.pop();
if(grid[tmp.first][tmp.second] != 1) continue;
grid[tmp.first][tmp.second] = 0;
area++;
if(tmp.second-1 >= 0) island.push(make_pair(tmp.first, tmp.second-1));
if(tmp.second+1 < xn) island.push(make_pair(tmp.first, tmp.second+1));
if(tmp.first-1 >= 0) island.push(make_pair(tmp.first-1, tmp.second));
if(tmp.first+1 < yn) island.push(make_pair(tmp.first+1, tmp.second));
}
ans = max(area, ans);
}
}
}
return ans;
}
};
Complexity analysis
Time complexity : O ( m × n ) O(m \times n) O(m×n). among m m m Is the number of rows in a given grid , n n n It's the number of columns . We visited each originally 1 At most once .
Spatial complexity : O ( m × n ) O(m \times n) O(m×n), The stack can store up to all the land , The maximum amount of land is m × n m \times n m×n block , Therefore, the space used is O ( m × n ) O(m \times n) O(m×n).
Method 3 :BFS + queue
Ideas
Change the stack in method 2 to queue , Take out the land from the head of the team every time , And put the land you want to traverse next at the end of the team , To achieve the breadth first search algorithm .
Code implementation
Leetcode Official explanation :
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans = 0;
for (int i = 0; i != grid.size(); ++i) {
for (int j = 0; j != grid[0].size(); ++j) {
int cur = 0;
queue<int> queuei;
queue<int> queuej;
queuei.push(i);
queuej.push(j);
while (!queuei.empty()) {
int cur_i = queuei.front(), cur_j = queuej.front();
queuei.pop();
queuej.pop();
if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1)
continue;
++cur;
grid[cur_i][cur_j] = 0;
int di[4] = {
0, 0, 1, -1};
int dj[4] = {
1, -1, 0, 0};
for (int index = 0; index != 4; ++index) {
int next_i = cur_i + di[index], next_j = cur_j + dj[index];
queuei.push(next_i);
queuej.push(next_j);
}
}
ans = max(ans, cur);
}
}
return ans;
}
};
My own :
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans = 0, area, yn = grid.size(), xn = grid[0].size();
queue<pair<int, int>> island;
pair<int, int> tmp;
for(int y = 0; y < yn; y++){
for(int x = 0; x < xn; x++){
if(grid[y][x] == 1){
area = 0;
island.push(make_pair(y, x));
while(!island.empty()){
tmp.first = island.front().first;
tmp.second = island.front().second;
island.pop();
if(grid[tmp.first][tmp.second] != 1) continue;
grid[tmp.first][tmp.second] = 0;
area++;
if(tmp.second-1 >= 0) island.push(make_pair(tmp.first, tmp.second-1));
if(tmp.second+1 < xn) island.push(make_pair(tmp.first, tmp.second+1));
if(tmp.first-1 >= 0) island.push(make_pair(tmp.first-1, tmp.second));
if(tmp.first+1 < yn) island.push(make_pair(tmp.first+1, tmp.second));
}
ans = max(area, ans);
}
}
}
return ans;
}
};
Complexity analysis
Time complexity : O ( m × n ) O(m×n) O(m×n). among m m m Is the number of rows in a given grid , n n n It's the number of columns . We visited each originally 1 At most once .
Spatial complexity : O ( m × n ) O(m \times n) O(m×n), At most all the land will be stored in the queue , The maximum amount of land is m × n m \times n m×n block , Therefore, the space used is O ( m × n ) O(m \times n) O(m×n).
边栏推荐
- leetcode刷题:二叉树17(从中序与后序遍历序列构造二叉树)
- Informatics Olympiad 1337: [example 3-2] word search tree | Luogu p5755 [noi2000] word search tree
- 图嵌入Graph embedding学习笔记
- C language OJ gets PE, OJ of ACM introduction~
- 【数字IC验证快速入门】2、通过一个SoC项目实例,了解SoC的架构,初探数字系统设计流程
- Station B up builds the world's first pure red stone neural network, pornographic detection based on deep learning action recognition, Chen Tianqi's course progress of machine science compilation MLC,
- MySql的root密码忘记该怎么找回
- leetcode刷题:二叉树13(相同的树)
- Oracle tablespace management
- 点云文件的.dat文件读取保存
猜你喜欢
js实现禁止网页缩放(Ctrl+鼠标、+、-缩放有效亲测)
leetcode刷题:二叉树15(找树左下角的值)
[Yugong series] go teaching course in July 2022 004 go code Notes
Autumn byte interviewer asked you any questions? In fact, you have stepped on thunder
物联网智能家居基本方法实现之经典
[quick start of Digital IC Verification] 9. Finite state machine (FSM) necessary for Verilog RTL design
B站UP搭建世界首个纯红石神经网络、基于深度学习动作识别的色情检测、陈天奇《机器学编译MLC》课程进展、AI前沿论文 | ShowMeAI资讯日报 #07.05
【数字IC验证快速入门】9、Verilog RTL设计必会的有限状态机(FSM)
Oracle tablespace management
Guidelines for application of Shenzhen green and low carbon industry support plan in 2023
随机推荐
信息学奥赛一本通 1340:【例3-5】扩展二叉树
2022北京眼睛健康用品展,护眼产品展,中国眼博会11月举办
Y57. Chapter III kubernetes from entry to proficiency -- business image version upgrade and rollback (30)
USACO3.4 “破锣摇滚”乐队 Raucous Rockers - DP
【数字IC验证快速入门】3、数字IC设计全流程介绍
Scala基础【HelloWorld代码解析,变量和标识符】
model方法
[Yugong series] go teaching course in July 2022 004 go code Notes
【数字IC验证快速入门】8、数字IC中的典型电路及其对应的Verilog描述方法
Oracle-表空间管理
leetcode刷题:二叉树17(从中序与后序遍历序列构造二叉树)
Go language learning tutorial (XV)
Go language | 01 wsl+vscode environment construction pit avoidance Guide
[quick start of Digital IC Verification] 6. Quick start of questasim (taking the design and verification of full adder as an example)
- Oui. Net Distributed Transaction and Landing Solution
Model method
c語言oj得pe,ACM入門之OJ~
计算lnx的一种方式
走入并行的世界
Wechat applet regular expression extraction link