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

Commit361b8aa

Browse files
committed
827-making-a-large-island.md Simplified Python solution.
1 parent2e4a38e commit361b8aa

File tree

4 files changed

+112
-130
lines changed

4 files changed

+112
-130
lines changed

‎README.md‎

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -85,8 +85,6 @@ You can skip the more difficult problems and do them later.
8585
-[188. Best Time to Buy and Sell Stock IV](en/1-1000/188-best-time-to-buy-and-sell-stock-iv.md) was solved in_Python, JavaScript, Go_.
8686
-[309. Best Time to Buy and Sell Stock with Cooldown](en/1-1000/309-best-time-to-buy-and-sell-stock-with-cooldown.md) was solved in_Python, JavaScript, Go_.
8787

88-
to here now
89-
9088
##Subsequence Problems
9189
-[674. Longest Continuous Increasing Subsequence](en/1-1000/674-longest-continuous-increasing-subsequence.md) was solved in_Python, Java, JavaScript, C#_.
9290
-[300. Longest Increasing Subsequence](en/1-1000/300-longest-increasing-subsequence.md) was solved in_Python, Java, JavaScript, C#_.

‎en/1-1000/827-making-a-large-island.md‎

Lines changed: 54 additions & 64 deletions
Original file line numberDiff line numberDiff line change
@@ -60,9 +60,9 @@ And this graph may have multiple **connected components** (islands):
6060
##Approach
6161
1. Change one vertex from`0` to`1` to make the largest island means combining the adjacent islands of a`0` vertex.
6262
1. We can mark an island's lands with one same id (`island_id`), and mark another island's lands with another`island_id`. To mark a land, just change its value to the`island_id`.
63-
1. Use a`map` (or an`array`) to map each`island_id` to its area (`land_count`).
63+
1. Use a`map` (or an`array`) to map each`island_id` to its`area`.
6464
1. How to calculate the area of an island? Using`Depth-First Search` or`Breadth-First Search`. See[695. Max Area of Island](695-max-area-of-island.md).
65-
1. Iterate through each`0` (water), then sum the areas (`land_count`) of neighboring islands.
65+
1. Iterate through each`0` (water), then sum the`areas` of neighboring islands.
6666
1. Record the max area and return it.
6767

6868
##Complexity
@@ -71,88 +71,78 @@ And this graph may have multiple **connected components** (islands):
7171

7272
##Python
7373
```python
74+
from collectionsimport defaultdict
75+
7476
classSolution:
7577
def__init__(self):
76-
self.result=0
77-
self.grid=None
78-
self.land_count=0
79-
self.land_counts= [0,0]# Since `island_id` starts from 2, the first two records will not be used
8078
self.island_id=2
79+
self.island_id_to_area= defaultdict(int)
8180

8281
deflargestIsland(self,grid: List[List[int]]) ->int:
8382
self.grid= grid
83+
max_area=0
8484

85-
for i, rowinenumerate(self.grid):
86-
for j, valueinenumerate(row):
87-
if value==1:
88-
self.land_count=0
89-
85+
for iinrange(len(grid)):
86+
for jinrange(len(grid[0])):
87+
ifself.grid[i][j]==1:
9088
self.depth_first_search(i, j)
89+
self.island_id+=1
9190

92-
self.land_counts.append(self.land_count)
93-
94-
self.result=max(self.land_count,self.result)
91+
has_water=False
9592

96-
self.island_id+=1
97-
98-
for i, rowinenumerate(grid):
99-
for j, valueinenumerate(row):
100-
if value==0:
101-
self.result=max(
102-
self.combined_islands_land_count(i, j),
103-
self.result
104-
)
105-
106-
returnself.result
93+
for iinrange(len(grid)):
94+
for jinrange(len(grid[0])):
95+
ifself.grid[i][j]==0:
96+
has_water=True
97+
max_area=max(max_area,self.combined_islands_area(i, j))
98+
99+
ifnot has_water:
100+
returnlen(grid)*len(grid[0])
101+
102+
return max_area
107103

108104
defdepth_first_search(self,i,j):
109-
if i<0or i>=len(self.grid):
110-
return
111-
112-
if j<0or j>=len(self.grid[0]):
105+
if i<0or j<0or i>=len(self.grid)or j>=len(self.grid[0]):
113106
return
114-
107+
115108
ifself.grid[i][j]!=1:
116109
return
117-
118-
self.grid[i][j]=self.island_id
119-
120-
self.land_count+=1
121-
122-
self.depth_first_search(i-1, j)
123-
self.depth_first_search(i, j+1)
124-
self.depth_first_search(i+1, j)
125-
self.depth_first_search(i, j-1)
126-
127-
defcombined_islands_land_count(self,i,j):
128-
used_island_ids=set()
129-
count=1
130110

131-
count+=self.island_land_count(i-1, j, used_island_ids)
132-
count+=self.island_land_count(i, j+1, used_island_ids)
133-
count+=self.island_land_count(i+1, j, used_island_ids)
134-
count+=self.island_land_count(i, j-1, used_island_ids)
135-
136-
return count
111+
self.grid[i][j]=self.island_id
112+
self.island_id_to_area[self.island_id]+=1
113+
114+
for a, bin [
115+
(-1,0),
116+
(0,-1), (0,1),
117+
(1,0)
118+
]:
119+
m= i+ a
120+
n= j+ b
121+
self.depth_first_search(m, n)
137122

138-
defisland_land_count(self,i,j,used_island_ids):
139-
if i<0or i>=len(self.grid):
140-
return0
141-
142-
if j<0or j>=len(self.grid[0]):
143-
return0
123+
defcombined_islands_area(self,i,j):
124+
island_ids=set()
125+
126+
for a, bin [
127+
(-1,0),
128+
(0,-1), (0,1),
129+
(1,0)
130+
]:
131+
m= i+ a
132+
n= j+ b
133+
134+
if m<0or n<0or m>=len(self.grid)or n>=len(self.grid[0]):
135+
continue
136+
137+
ifself.grid[m][n]!=0:
138+
island_ids.add(self.grid[m][n])
144139

145-
ifself.grid[i][j]==0:
146-
return0
140+
area=1
147141

148-
island_id=self.grid[i][j]
142+
for island_idin island_ids:
143+
area+=self.island_id_to_area[island_id]
149144

150-
if island_idin used_island_ids:
151-
return0
152-
153-
used_island_ids.add(island_id)
154-
155-
returnself.land_counts[island_id]
145+
return area
156146
```
157147

158148
##Java

‎en/3001-4000/unorganized.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -164,6 +164,9 @@ The improved way with a queue is commonly more efficient. Relaxing **All Edges**
164164
- 647https://leetcode.cn/problems/palindromic-substrings/ very hard
165165
- 516https://leetcode.cn/problems/longest-palindromic-subsequence/
166166

167+
###Graph
168+
- 417https://leetcode.com/problems/pacific-atlantic-water-flow/
169+
167170
###Failed in 2 rounds
168171
- 222https://leetcode.cn/problems/count-complete-tree-nodes/
169172
- 236https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
@@ -176,5 +179,6 @@ The improved way with a queue is commonly more efficient. Relaxing **All Edges**
176179
- 115https://leetcode.cn/problems/distinct-subsequences/
177180
- 647https://leetcode.cn/problems/palindromic-substrings/https://leetcode.cn/problems/palindromic-substrings/submissions/597748845/
178181
- 516https://leetcode.cn/problems/longest-palindromic-subsequence/
182+
- 417https://leetcode.com/problems/pacific-atlantic-water-flow/
179183

180184
2005-02-09 day 2

‎zh/1-1000/827-making-a-large-island.md‎

Lines changed: 54 additions & 64 deletions
Original file line numberDiff line numberDiff line change
@@ -60,9 +60,9 @@ And this graph may have multiple **connected components** (islands):
6060
##Approach
6161
1. Change one vertex from`0` to`1` to make the largest island means combining the adjacent islands of a`0` vertex.
6262
1. We can mark an island's lands with one same id (`island_id`), and mark another island's lands with another`island_id`. To mark a land, just change its value to the`island_id`.
63-
1. Use a`map` (or an`array`) to map each`island_id` to its area (`land_count`).
63+
1. Use a`map` (or an`array`) to map each`island_id` to its`area`.
6464
1. How to calculate the area of an island? Using`Depth-First Search` or`Breadth-First Search`. See[695. Max Area of Island](695-max-area-of-island.md).
65-
1. Iterate through each`0` (water), then sum the areas (`land_count`) of neighboring islands.
65+
1. Iterate through each`0` (water), then sum the`areas` of neighboring islands.
6666
1. Record the max area and return it.
6767

6868
##Complexity
@@ -71,88 +71,78 @@ And this graph may have multiple **connected components** (islands):
7171

7272
##Python
7373
```python
74+
from collectionsimport defaultdict
75+
7476
classSolution:
7577
def__init__(self):
76-
self.result=0
77-
self.grid=None
78-
self.land_count=0
79-
self.land_counts= [0,0]# Since `island_id` starts from 2, the first two records will not be used
8078
self.island_id=2
79+
self.island_id_to_area= defaultdict(int)
8180

8281
deflargestIsland(self,grid: List[List[int]]) ->int:
8382
self.grid= grid
83+
max_area=0
8484

85-
for i, rowinenumerate(self.grid):
86-
for j, valueinenumerate(row):
87-
if value==1:
88-
self.land_count=0
89-
85+
for iinrange(len(grid)):
86+
for jinrange(len(grid[0])):
87+
ifself.grid[i][j]==1:
9088
self.depth_first_search(i, j)
89+
self.island_id+=1
9190

92-
self.land_counts.append(self.land_count)
93-
94-
self.result=max(self.land_count,self.result)
91+
has_water=False
9592

96-
self.island_id+=1
97-
98-
for i, rowinenumerate(grid):
99-
for j, valueinenumerate(row):
100-
if value==0:
101-
self.result=max(
102-
self.combined_islands_land_count(i, j),
103-
self.result
104-
)
105-
106-
returnself.result
93+
for iinrange(len(grid)):
94+
for jinrange(len(grid[0])):
95+
ifself.grid[i][j]==0:
96+
has_water=True
97+
max_area=max(max_area,self.combined_islands_area(i, j))
98+
99+
ifnot has_water:
100+
returnlen(grid)*len(grid[0])
101+
102+
return max_area
107103

108104
defdepth_first_search(self,i,j):
109-
if i<0or i>=len(self.grid):
110-
return
111-
112-
if j<0or j>=len(self.grid[0]):
105+
if i<0or j<0or i>=len(self.grid)or j>=len(self.grid[0]):
113106
return
114-
107+
115108
ifself.grid[i][j]!=1:
116109
return
117-
118-
self.grid[i][j]=self.island_id
119-
120-
self.land_count+=1
121-
122-
self.depth_first_search(i-1, j)
123-
self.depth_first_search(i, j+1)
124-
self.depth_first_search(i+1, j)
125-
self.depth_first_search(i, j-1)
126-
127-
defcombined_islands_land_count(self,i,j):
128-
used_island_ids=set()
129-
count=1
130110

131-
count+=self.island_land_count(i-1, j, used_island_ids)
132-
count+=self.island_land_count(i, j+1, used_island_ids)
133-
count+=self.island_land_count(i+1, j, used_island_ids)
134-
count+=self.island_land_count(i, j-1, used_island_ids)
135-
136-
return count
111+
self.grid[i][j]=self.island_id
112+
self.island_id_to_area[self.island_id]+=1
113+
114+
for a, bin [
115+
(-1,0),
116+
(0,-1), (0,1),
117+
(1,0)
118+
]:
119+
m= i+ a
120+
n= j+ b
121+
self.depth_first_search(m, n)
137122

138-
defisland_land_count(self,i,j,used_island_ids):
139-
if i<0or i>=len(self.grid):
140-
return0
141-
142-
if j<0or j>=len(self.grid[0]):
143-
return0
123+
defcombined_islands_area(self,i,j):
124+
island_ids=set()
125+
126+
for a, bin [
127+
(-1,0),
128+
(0,-1), (0,1),
129+
(1,0)
130+
]:
131+
m= i+ a
132+
n= j+ b
133+
134+
if m<0or n<0or m>=len(self.grid)or n>=len(self.grid[0]):
135+
continue
136+
137+
ifself.grid[m][n]!=0:
138+
island_ids.add(self.grid[m][n])
144139

145-
ifself.grid[i][j]==0:
146-
return0
140+
area=1
147141

148-
island_id=self.grid[i][j]
142+
for island_idin island_ids:
143+
area+=self.island_id_to_area[island_id]
149144

150-
if island_idin used_island_ids:
151-
return0
152-
153-
used_island_ids.add(island_id)
154-
155-
returnself.land_counts[island_id]
145+
return area
156146
```
157147

158148
##Java

0 commit comments

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