Skip to content

Commit 4a29be2

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0695. Max Area of Island
1 parent b4ddd69 commit 4a29be2

File tree

5 files changed

+208
-56
lines changed

5 files changed

+208
-56
lines changed

‎solution/0600-0699/0695.Max Area of Island/README.md

Lines changed: 78 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -50,15 +50,58 @@
5050
<!-- 这里可写当前语言的特殊实现逻辑 -->
5151

5252
```python
53-
53+
class Solution:
54+
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
55+
def dfs(grid, i, j, m, n):
56+
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:
57+
return 0
58+
grid[i][j] = 0
59+
res = 1
60+
for x, y in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
61+
res += dfs(grid, i + x, j + y, m, n)
62+
return res
63+
64+
m, n = len(grid), len(grid[0])
65+
res = 0
66+
for i in range(m):
67+
for j in range(n):
68+
t = dfs(grid, i, j, m, n)
69+
res = max(res, t)
70+
return res
5471
```
5572

5673
### **Java**
5774

5875
<!-- 这里可写当前语言的特殊实现逻辑 -->
5976

6077
```java
78+
class Solution {
79+
private int[][] directions = {{0, 1}, {0, - 1}, {1, 0}, {-1, 0}};
80+
81+
public int maxAreaOfIsland(int[][] grid) {
82+
int m = grid.length, n = grid[0].length;
83+
int res = 0;
84+
for (int i = 0; i < m; ++i) {
85+
for (int j = 0; j < n; ++j) {
86+
int t = dfs(grid, i, j, m, n);
87+
res = Math.max(res, t);
88+
}
89+
}
90+
return res;
91+
}
6192

93+
private int dfs(int[][] grid, int i, int j, int m, int n) {
94+
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
95+
return 0;
96+
}
97+
grid[i][j] = 0;
98+
int res = 1;
99+
for (int[] direction : directions) {
100+
res += dfs(grid, i + direction[0], j + direction[1], m, n);
101+
}
102+
return res;
103+
}
104+
}
62105
```
63106

64107
### **TypeScript**
@@ -95,6 +138,40 @@ function dfs(grid: number[][], i: number, j: number, visited: boolean[][]): numb
95138
}
96139
```
97140

141+
### **C++**
142+
143+
```cpp
144+
class Solution {
145+
public:
146+
int maxAreaOfIsland(vector<vector<int>>& grid) {
147+
int m = grid.size(), n = grid[0].size();
148+
int res = 0;
149+
for (int i = 0; i < m; ++i) {
150+
for (int j = 0; j < n; ++j) {
151+
int t = dfs(grid, i, j, m, n);
152+
res = max(res, t);
153+
}
154+
}
155+
return res;
156+
}
157+
private:
158+
vector<vector<int>> directions = {{0, 1}, {0, - 1}, {1, 0}, {-1, 0}};
159+
160+
int dfs(vector<vector<int>>& grid, int i, int j, int m, int n) {
161+
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
162+
return 0;
163+
}
164+
grid[i][j] = 0;
165+
int res = 1;
166+
for (auto direction : directions) {
167+
res += dfs(grid, i + direction[0], j + direction[1], m, n);
168+
}
169+
return res;
170+
}
171+
172+
};
173+
```
174+
98175
### **...**
99176

100177
```

‎solution/0600-0699/0695.Max Area of Island/README_EN.md

Lines changed: 78 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -63,13 +63,56 @@ Given the above grid, return <code>0</code>.
6363
### **Python3**
6464

6565
```python
66-
66+
class Solution:
67+
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
68+
def dfs(grid, i, j, m, n):
69+
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:
70+
return 0
71+
grid[i][j] = 0
72+
res = 1
73+
for x, y in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
74+
res += dfs(grid, i + x, j + y, m, n)
75+
return res
76+
77+
m, n = len(grid), len(grid[0])
78+
res = 0
79+
for i in range(m):
80+
for j in range(n):
81+
t = dfs(grid, i, j, m, n)
82+
res = max(res, t)
83+
return res
6784
```
6885

6986
### **Java**
7087

7188
```java
89+
class Solution {
90+
private int[][] directions = {{0, 1}, {0, - 1}, {1, 0}, {-1, 0}};
91+
92+
public int maxAreaOfIsland(int[][] grid) {
93+
int m = grid.length, n = grid[0].length;
94+
int res = 0;
95+
for (int i = 0; i < m; ++i) {
96+
for (int j = 0; j < n; ++j) {
97+
int t = dfs(grid, i, j, m, n);
98+
res = Math.max(res, t);
99+
}
100+
}
101+
return res;
102+
}
72103

104+
private int dfs(int[][] grid, int i, int j, int m, int n) {
105+
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
106+
return 0;
107+
}
108+
grid[i][j] = 0;
109+
int res = 1;
110+
for (int[] direction : directions) {
111+
res += dfs(grid, i + direction[0], j + direction[1], m, n);
112+
}
113+
return res;
114+
}
115+
}
73116
```
74117

75118
### **TypeScript**
@@ -106,6 +149,40 @@ function dfs(grid: number[][], i: number, j: number, visited: boolean[][]): numb
106149
}
107150
```
108151

152+
### **C++**
153+
154+
```cpp
155+
class Solution {
156+
public:
157+
int maxAreaOfIsland(vector<vector<int>>& grid) {
158+
int m = grid.size(), n = grid[0].size();
159+
int res = 0;
160+
for (int i = 0; i < m; ++i) {
161+
for (int j = 0; j < n; ++j) {
162+
int t = dfs(grid, i, j, m, n);
163+
res = max(res, t);
164+
}
165+
}
166+
return res;
167+
}
168+
private:
169+
vector<vector<int>> directions = {{0, 1}, {0, - 1}, {1, 0}, {-1, 0}};
170+
171+
int dfs(vector<vector<int>>& grid, int i, int j, int m, int n) {
172+
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
173+
return 0;
174+
}
175+
grid[i][j] = 0;
176+
int res = 1;
177+
for (auto direction : directions) {
178+
res += dfs(grid, i + direction[0], j + direction[1], m, n);
179+
}
180+
return res;
181+
}
182+
183+
};
184+
```
185+
109186
### **...**
110187

111188
```

‎solution/0600-0699/0695.Max Area of Island/Solution.cpp

Lines changed: 22 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -1,51 +1,29 @@
11
class Solution {
22
public:
3-
bool v[55][55] = {0, } ; // ·ÃÎʱê¼Ç
4-
int maxAreaOfIsland(vector<vector<int>>& grid)
5-
{
6-
int maxAera = 0 ;
7-
for (int i = 0; i < grid.size(); ++i)
8-
{
9-
if (0 == grid.size())
10-
{
11-
return 0 ;
12-
}
13-
14-
for (int j = 0; j < grid[0].size(); ++j)
15-
{
16-
if (1 == grid[i][j] && !v[i][j])
17-
{
18-
int cnt = calcAera(grid, i, j) ;
19-
if (cnt > maxAera)
20-
maxAera = cnt ;
21-
}
3+
int maxAreaOfIsland(vector<vector<int>>& grid) {
4+
int m = grid.size(), n = grid[0].size();
5+
int res = 0;
6+
for (int i = 0; i < m; ++i) {
7+
for (int j = 0; j < n; ++j) {
8+
int t = dfs(grid, i, j, m, n);
9+
res = max(res, t);
2210
}
2311
}
24-
return maxAera ;
12+
return res;
2513
}
26-
27-
int calcAera(vector<vector<int>>& grid, int i, int j)
28-
{
29-
if (i < 0 || i >= grid.size())
30-
return 0 ;
31-
if (j < 0 || j >= grid[0].size())
32-
return 0 ;
33-
34-
if (v[i][j])
35-
return 0 ;
36-
37-
v[i][j] = true ;
38-
39-
40-
if (grid[i][j])
41-
{
42-
return 1
43-
+ calcAera(grid, i-1, j)
44-
+ calcAera(grid, i+1, j)
45-
+ calcAera(grid, i, j-1)
46-
+ calcAera(grid, i, j+1) ;
14+
private:
15+
vector<vector<int>> directions = {{0, 1}, {0, - 1}, {1, 0}, {-1, 0}};
16+
17+
int dfs(vector<vector<int>>& grid, int i, int j, int m, int n) {
18+
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
19+
return 0;
20+
}
21+
grid[i][j] = 0;
22+
int res = 1;
23+
for (auto direction : directions) {
24+
res += dfs(grid, i + direction[0], j + direction[1], m, n);
4725
}
48-
else
49-
return 0 ;
26+
return res;
5027
}
51-
} ;
28+
29+
};

‎solution/0600-0699/0695.Max Area of Island/Solution.java

Lines changed: 12 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,25 +1,27 @@
11
class Solution {
2+
private int[][] directions = {{0, 1}, {0, - 1}, {1, 0}, {-1, 0}};
3+
24
public int maxAreaOfIsland(int[][] grid) {
5+
int m = grid.length, n = grid[0].length;
36
int res = 0;
4-
int m = grid.length;
5-
int n = grid[0].length;
67
for (int i = 0; i < m; ++i) {
78
for (int j = 0; j < n; ++j) {
8-
res = Math.max(res, dfs(grid, i, j, m, n));
9+
int t = dfs(grid, i, j, m, n);
10+
res = Math.max(res, t);
911
}
1012
}
1113
return res;
1214
}
13-
15+
1416
private int dfs(int[][] grid, int i, int j, int m, int n) {
15-
if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0) {
17+
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
1618
return 0;
1719
}
1820
grid[i][j] = 0;
19-
return 1
20-
+ dfs(grid, i - 1, j, m, n)
21-
+ dfs(grid, i + 1, j, m, n)
22-
+ dfs(grid, i, j - 1, m, n)
23-
+ dfs(grid, i, j + 1, m, n);
21+
int res = 1;
22+
for (int[] direction : directions) {
23+
res += dfs(grid, i + direction[0], j + direction[1], m, n);
24+
}
25+
return res;
2426
}
2527
}

‎solution/0600-0699/0695.Max Area of Island/Solution.py

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
class Solution:
2+
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
3+
def dfs(grid, i, j, m, n):
4+
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:
5+
return 0
6+
grid[i][j] = 0
7+
res = 1
8+
for x, y in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
9+
res += dfs(grid, i + x, j + y, m, n)
10+
return res
11+
12+
m, n = len(grid), len(grid[0])
13+
res = 0
14+
for i in range(m):
15+
for j in range(n):
16+
t = dfs(grid, i, j, m, n)
17+
res = max(res, t)
18+
return res

0 commit comments

Comments
 (0)