当前位置:网站首页>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 skimming: binary tree 16 (path sum)
- Leetcode brush question: binary tree 13 (the same tree)
- selenium 元素信息
- E. Singhal and Numbers(质因数分解)
- [C language] merge sort
- sort和投影
- 股票开户哪里好?网上客户经理开户安全吗
- Scala basics [HelloWorld code parsing, variables and identifiers]
- - Oui. Net Distributed Transaction and Landing Solution
- mongodb文档间关系
猜你喜欢
【数字IC验证快速入门】3、数字IC设计全流程介绍
Guidelines for application of Shenzhen green and low carbon industry support plan in 2023
【数字IC验证快速入门】8、数字IC中的典型电路及其对应的Verilog描述方法
. Net distributed transaction and landing solution
leetcode刷题:二叉树16(路径总和)
leetcode刷题:二叉树15(找树左下角的值)
leetcode刷题:二叉树12(二叉树的所有路径)
leetcode刷题:二叉树17(从中序与后序遍历序列构造二叉树)
[quick start of Digital IC Verification] 6. Quick start of questasim (taking the design and verification of full adder as an example)
leetcode刷题:二叉树18(最大二叉树)
随机推荐
E. Singhal and Numbers(质因数分解)
Bzoj 3747 poi2015 kinoman segment tree
【数字IC验证快速入门】1、浅谈数字IC验证,了解专栏内容,明确学习目标
《乔布斯传》英文原著重点词汇笔记(十二)【 chapter ten & eleven】
nprogress插件 进度条
Model method
How to select the Block Editor? Impression notes verse, notation, flowus
Oracle-表空间管理
【数字IC验证快速入门】7、验证岗位中必备的数字电路基础知识(含常见面试题)
Minimum commission for stock trading account opening, where to open an account with low commission? Is it safe to open an account on your mobile phone
中金财富在网上开户安全吗?
Unity editor extended UI control
Scala basics [HelloWorld code parsing, variables and identifiers]
mongodb/文档操作
1: Citation;
PyTorch 1.12发布,正式支持苹果M1芯片GPU加速,修复众多Bug
Scala基础【HelloWorld代码解析,变量和标识符】
CTF逆向基础
js实现禁止网页缩放(Ctrl+鼠标、+、-缩放有效亲测)
sun. misc. Base64encoder error reporting solution [easy to understand]