概要
ゼロから始めるLeetCodeの時に解いた問題とかをSwiftで書いてみることにした。
シリーズ化するかは不明。
問題
1（陸）と0（水）の地図を表すm×nの2次元2進格子が与えられたとき、一番大きい島の面積を返しなさいという問題。
前回に引き続きMediumの問題です。
[
["0","1","0"],
["1","1","1"],
["0","1","0"]
]
であれば島の面積は5となり、
[
["0","1","0"],
["1","0","1"],
["0","1","0"]
]
となれば島の面積は1となる。
Pythonで実装
グラフなんだからDFSとBFSで書いてみる。
まずDFS。
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid:
return 0
rows,cols = len(grid),len(grid[0])
maxArea = 0
def dfs(row,col):
if 0 <= col < cols and 0 <= row < rows and grid[row][col] == 1:
grid[row][col] = 0
return 1 + dfs(row+1,col) + dfs(row-1,col) + dfs(row,col+1) + dfs(row,col-1)
return 0
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
tempCount = dfs(i,j)
maxArea = max(maxArea,tempCount)
return maxArea
# Runtime Details 119ms Beats 82.74%of users with Python3
# Memory Details 18.92MB Beats 63.58%of users with Python3
前回同様、再帰処理が分かっていれば想像しやすい。
ただ、通った後に思ったけど、これだと上から下に読んだ時の視認性が悪いと感じたので書き直した。
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid:
return 0
self.grid = grid
self.rows, self.cols = len(grid), len(grid[0])
self.maxArea = 0
for i in range(self.rows):
for j in range(self.cols):
if self.grid[i][j] == 1:
tempCount = self.dfs(i, j)
self.maxArea = max(self.maxArea, tempCount)
return self.maxArea
def dfs(self, row, col):
if 0 <= col < self.cols and 0 <= row < self.rows and self.grid[row][col] == 1:
self.grid[row][col] = 0
return 1 + self.dfs(row+1, col) + self.dfs(row-1, col) + self.dfs(row, col+1) + self.dfs(row, col-1)
return 0
# Runtime Details 119ms Beats 82.74%of users with Python3
# Memory Details 18.92MB Beats 63.58%of users with Python3
両方の解法をいきなり見せられた場合、こちらの方が読みやすいと思ったのでこちらで通すことにする。
計算量と空間計算量ともにO(N*M)で二次元配列の長さに依存する。
今度はBFS。今度は関数直下に書くパターンのみ。
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid:
return 0
rows,cols = len(grid),len(grid[0])
maxArea = 0
def bfs(row,col):
queue = collections.deque()
queue.append((row,col))
areaCounter = 0
while queue:
qr,qc = queue.popleft()
if 0 <= qr < rows and 0 <= qc < cols and grid[qr][qc] == 1:
grid[qr][qc] = 0
areaCounter += 1
queue.append((qr+1,qc))
queue.append((qr-1,qc))
queue.append((qr,qc+1))
queue.append((qr,qc-1))
return areaCounter
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
tempCount = bfs(i,j)
maxArea = max(maxArea,tempCount)
return maxArea
# Runtime Details 113ms Beats 93.33%of users with Python3
# Memory Details 16.26MB Beats 99.49%of users with Python3
最初の回答と計算量も空間計算量も変わらないのになんかいい数値が出た。
こちらも計算量と空間計算量ともにO(N*M)で二次元配列の長さに依存する。
Swiftで実装
上記と同様の内容をSwiftで書き直してみる。
視認性が悪くて修正する前。
class Solution {
func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
if grid.isEmpty{
return 0
}
var rows:Int = grid.count
var cols:Int = grid[0].count
var grid = grid
var maxArea:Int = 0
func dfs(row:Int,col:Int) -> Int{
if 0 ..< rows ~= row && 0 ..< cols ~= col && grid[row][col] == 1 {
grid[row][col] = 0
return 1 + dfs(row:row+1,col:col) + dfs(row:row-1,col:col) + dfs(row:row,col:col+1) + dfs(row:row,col:col-1)
}
return 0
}
for i in 0..<rows{
for j in 0..<cols{
if grid[i][j] == 1{
let tempCount = dfs(row:i,col:j)
maxArea = max(maxArea,tempCount)
}
}
}
return maxArea
}
}
// Runtime Details 57ms Beats 70.43%of users with Swift
// Memory Details 14.32MB Beats 40.32%of users with Swift
修正後
class Solution {
var rows = 0
var cols = 0
var grid = [[Int]]()
func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
if grid.isEmpty {
return 0
}
self.rows = grid.count
self.cols = grid[0].count
self.grid = grid
var maxArea = 0
for i in 0..<self.rows {
for j in 0..<self.cols {
if self.grid[i][j] == 1 {
let tempCount = dfs(row: i, col: j)
maxArea = max(maxArea, tempCount)
}
}
}
return maxArea
}
func dfs(row: Int, col: Int) -> Int {
if 0 ..< self.rows ~= row && 0 ..< self.cols ~= col && self.grid[row][col] == 1 {
self.grid[row][col] = 0
return 1 + dfs(row: row + 1, col: col) + dfs(row: row - 1, col: col) + dfs(row: row, col: col + 1) + dfs(row: row, col: col - 1)
}
return 0
}
}
// Runtime Details 57ms Beats 70.43%of users with Swift
// Memory Details 14.32MB Beats 40.32%of users with Swift
いずれもそこまで気をつけることはなく、単純に書き直してみました！って感じの流れだった。
強いて書くなら前回の記事でコメント頂いたif分岐の条件をSwiftっぽく書くことを意識したくらい。
BFSはというと、
class Solution {
func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
if grid.isEmpty{
return 0
}
var rows:Int = grid.count
var cols:Int = grid[0].count
var grid = grid
var maxArea:Int = 0
func bfs(row:Int,col:Int) -> Int{
var queue = [(row,col)]
var areaCount = 0
while !queue.isEmpty{
let (qr,qc) = queue.removeFirst()
if 0 ..< rows ~= qr && 0 ..< cols ~= qc && grid[qr][qc] == 1 {
grid[qr][qc] = 0
areaCount += 1
queue.append((qr+1,qc))
queue.append((qr-1,qc))
queue.append((qr,qc+1))
queue.append((qr,qc-1))
}
}
return areaCount
}
for i in 0..<rows{
for j in 0..<cols{
if grid[i][j] == 1{
let tempCount = bfs(row:i,col:j)
maxArea = max(maxArea,tempCount)
}
}
}
return maxArea
}
}
// Runtime Details 61ms Beats 40.32%of users with Swift
// Memory Details 13.94MB Beats 90.86%of users with Swift
こちらも前回コメントでもらった条件で分岐を書くくらいに気をつけたことは他になかった。
グラフだって分かったらある程度型にはめる方法が大事で、その場でのひらめきとかよりも定石を知っているかのような気がしてきたので、もしかしたら基礎の部分が徐々に固まってきたのかもしれない。
Swiftの知識がまだまだ足りないので色んな問題(主に難易度Medium以上)を解いて練習していく予定。