Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit093670d

Browse files
committed
695-max-area-of-island.md Perfected code.
1 parentd30ebe1 commit093670d

File tree

2 files changed

+126
-192
lines changed

2 files changed

+126
-192
lines changed

‎en/1-1000/695-max-area-of-island.md

Lines changed: 61 additions & 94 deletions
Original file line numberDiff line numberDiff line change
@@ -54,11 +54,11 @@ Return _the maximum area of an island_ is to return the vertex count of the larg
5454
* There are two major ways to explore a`connected component` (island):**Breadth-First Search** and**Depth-First Search**.
5555
* For**Depth-First Search**, there are two ways to make it:`Recursive` and`Iterative`. So I will provide 3 solutions in total.
5656
* When we traverse each`connected components` (island), we can:
57-
* Mark each found land as`8` which represents`visited`. Visited lands don't need to be visited again.
57+
* Mark each found land as`8` which represents`visited` (or`included` in`area`). Visited lands don't need to be visited again.
5858
***count** the lands of the island.
5959
3. After all lands on an island have been visited, look for the next non-visited land.
6060
4. Repeat the above two steps until all the lands have been`visited`.
61-
5. At last, return themax land count.
61+
5. At last, return the`max_area`.
6262

6363
##Solution 1: 'Depth-First Search' by Recursion
6464
![](../../images/binary_tree_DFS_1.png)
@@ -85,70 +85,65 @@ Similar problem is `200. Number of Islands`, please click [Breadth-First Search
8585
```python
8686
classSolution:
8787
def__init__(self):
88-
self.max_land_count=0
89-
self.land_count=0
88+
self.max_area=0
89+
self.area=0
9090
self.grid=None
9191

9292
defmaxAreaOfIsland(self,grid: List[List[int]]) ->int:
9393
self.grid= grid
9494

9595
for iinrange(len(grid)):
9696
for jinrange(len(grid[0])):
97-
ifself.grid[i][j]==1:
98-
self.land_count=0
99-
97+
if grid[i][j]==1:
98+
self.area=0
10099
self.depth_first_search(i, j)
100+
self.max_area=max(self.max_area,self.area)
101101

102-
returnself.max_land_count
103-
102+
returnself.max_area
103+
104104
defdepth_first_search(self,i,j):
105-
if i<0or i>=len(self.grid):
106-
return
107-
108-
if j<0or j>=len(self.grid[0]):
105+
if i<0or j<0or i>=len(self.grid)or j>=len(self.grid[0]):
109106
return
110107

111108
ifself.grid[i][j]!=1:
112109
return
113110

114111
self.grid[i][j]=8
115-
116-
self.land_count+=1
117-
118-
ifself.land_count>self.max_land_count:
119-
self.max_land_count=self.land_count
120-
121-
self.depth_first_search(i-1, j)
122-
self.depth_first_search(i, j+1)
123-
self.depth_first_search(i+1, j)
124-
self.depth_first_search(i, j-1)
112+
self.area+=1
113+
114+
for m, nin [
115+
(-1,0),
116+
(0,-1), (0,1),
117+
(1,0),
118+
]:
119+
self.depth_first_search(i+ m, j+ n)
125120
```
126121

127122
#Java
128123
```java
129124
classSolution {
130125
int[][] grid;
131-
intmaxLandCount=0;
132-
intlandCount=0;
126+
intmaxArea=0;
127+
intarea=0;
133128

134129
publicintmaxAreaOfIsland(int[][]grid) {
135130
this.grid= grid;
136131

137132
for (var i=0; i< grid.length; i++) {
138133
for (var j=0; j< grid[0].length; j++) {
139134
if (grid[i][j]==1) {
140-
landCount=0;
141-
135+
area=0;
142136
depthFirstSearch(i, j);
137+
maxArea=Math.max(maxArea, area);
143138
}
144139
}
145140
}
146141

147-
returnmaxLandCount;
142+
returnmaxArea;
148143
}
149144

150145
voiddepthFirstSearch(inti,intj) {
151-
if (i<0|| i>= grid.length) {
146+
if (i<0|| i>= grid.length) {
152147
return;
153148
}
154149

@@ -161,12 +156,7 @@ class Solution {
161156
}
162157

163158
grid[i][j]=8;
164-
165-
landCount++;
166-
167-
if (landCount> maxLandCount) {
168-
maxLandCount= landCount;
169-
}
159+
area++;
170160

171161
depthFirstSearch(i-1, j);
172162
depthFirstSearch(i, j+1);
@@ -186,20 +176,20 @@ public:
186176
for (auto i = 0; i < grid_.size(); i++) {
187177
for (auto j = 0; j < grid_[0].size(); j++) {
188178
if (grid_[i][j] == 1) {
189-
land_count_ = 0;
190-
179+
area_ = 0;
191180
depth_first_search(i, j);
181+
max_area_ = max(max_area_, area_);
192182
}
193183
}
194184
}
195185

196-
returnmax_land_count_;
186+
returnmax_area_;
197187
}
198188

199189
private:
200190
vector<vector<int>> grid_;
201-
intmax_land_count_ =0;
202-
intland_count_ =0;
191+
intmax_area_ =0;
192+
intarea_ =0;
203193

204194
voiddepth_first_search(int i, int j) {
205195
if (
@@ -211,12 +201,7 @@ private:
211201
}
212202

213203
grid_[i][j] = 8;
214-
215-
land_count_++;
216-
217-
if (land_count_ > max_land_count_) {
218-
max_land_count_ = land_count_;
219-
}
204+
area_++;
220205

221206
depth_first_search(i - 1, j);
222207
depth_first_search(i, j + 1);
@@ -229,24 +214,24 @@ private:
229214
# JavaScript
230215
```JavaScript
231216
let grid
232-
letmaxLandCount = 0
233-
letlandCount
217+
letmaxArea = 0
218+
letarea
234219
235220
var maxAreaOfIsland = function (grid_) {
236221
grid = grid_
237-
maxLandCount = 0
222+
maxArea = 0
238223
239224
grid.forEach((row, i) => {
240225
row.forEach((value, j) => {
241226
if (value === 1) {
242-
landCount = 0
243-
227+
area = 0
244228
depthFirstSearch(i, j)
229+
maxArea = Math.max(maxArea, area)
245230
}
246231
})
247232
})
248233
249-
returnmaxLandCount
234+
returnmaxArea
250235
};
251236
252237
@@ -264,12 +249,7 @@ function depthFirstSearch(i, j) {
264249
}
265250
266251
grid[i][j] = 8
267-
268-
landCount++
269-
270-
if (landCount > maxLandCount) {
271-
maxLandCount = landCount
272-
}
252+
area++
273253
274254
depthFirstSearch(i - 1, j)
275255
depthFirstSearch(i, j + 1)
@@ -280,12 +260,14 @@ function depthFirstSearch(i, j) {
280260

281261
#C#
282262
```c#
283-
publicclassSolution {
263+
publicclassSolution
264+
{
284265
int[][]grid;
285-
intmaxLandCount=0;
286-
intlandCount=0;
266+
intmaxArea=0;
267+
intarea=0;
287268

288-
publicintMaxAreaOfIsland(int[][]grid) {
269+
publicintMaxAreaOfIsland(int[][]grid)
270+
{
289271
this.grid=grid;
290272

291273
for (vari=0;i<grid.Length;i++)
@@ -294,14 +276,14 @@ public class Solution {
294276
{
295277
if (grid[i][j]==1)
296278
{
297-
landCount=0;
298-
279+
area=0;
299280
depthFirstSearch(i,j);
281+
maxArea=Math.Max(maxArea,area);
300282
}
301283
}
302284
}
303285

304-
returnmaxLandCount;
286+
returnmaxArea;
305287
}
306288

307289
voiddepthFirstSearch(inti,intj)
@@ -316,12 +298,7 @@ public class Solution {
316298
return;
317299

318300
grid[i][j]=8;
319-
320-
landCount++;
321-
322-
if (landCount>maxLandCount) {
323-
maxLandCount=landCount;
324-
}
301+
area++;
325302

326303
depthFirstSearch(i-1,j);
327304
depthFirstSearch(i,j+1);
@@ -335,25 +312,25 @@ public class Solution {
335312
```go
336313
var (
337314
grid [][]int
338-
maxLandCountint
339-
landCountint
315+
maxAreaint
316+
areaint
340317
)
341318

342319
funcmaxAreaOfIsland(grid_ [][]int)int {
343320
grid = grid_
344-
maxLandCount =0
321+
maxArea =0
345322

346323
fori,row:=range grid {
347324
forj,value:=range row {
348325
if value ==1 {
349-
landCount =0
350-
326+
area =0
351327
depthFirstSearch(i, j)
328+
maxArea =max(maxArea, area)
352329
}
353330
}
354331
}
355332

356-
returnmaxLandCount
333+
returnmaxArea
357334
}
358335

359336
funcdepthFirstSearch(iint,jint) {
@@ -370,12 +347,7 @@ func depthFirstSearch(i int, j int) {
370347
}
371348

372349
grid[i][j] =8
373-
374-
landCount++
375-
376-
if landCount > maxLandCount {
377-
maxLandCount = landCount
378-
}
350+
area++
379351

380352
depthFirstSearch(i -1, j)
381353
depthFirstSearch(i, j +1)
@@ -388,20 +360,20 @@ func depthFirstSearch(i int, j int) {
388360
```Ruby
389361
defmax_area_of_island(grid)
390362
@grid= grid
391-
@max_land_count=0
392-
@land_count=0
363+
@max_area=0
364+
@area=0
393365

394366
@grid.each_with_indexdo |row,i|
395367
row.each_with_indexdo |value,j|
396368
if value==1
397-
@land_count=0
398-
369+
@area=0
399370
depth_first_search(i, j)
371+
@max_area= [@max_area,@area].max
400372
end
401373
end
402374
end
403375

404-
@max_land_count
376+
@max_area
405377
end
406378

407379
defdepth_first_search(i,j)
@@ -412,12 +384,7 @@ def depth_first_search(i, j)
412384
returnif@grid[i][j]!=1
413385

414386
@grid[i][j]=8
415-
416-
@land_count+=1
417-
418-
if@land_count>@max_land_count
419-
@max_land_count=@land_count
420-
end
387+
@area+=1
421388

422389
depth_first_search(i-1, j)
423390
depth_first_search(i, j+1)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp