LeetCode「200. Number of Islands」解説
概要
外資系では、エンジニアの面接でコーディングテストを行う企業が多いらしいです
そのコーディングテストの過去問のサイトがLeetCodeです
受ける予定はありませんが、勉強のために毎日1問解いています
問題
200. Number of Islands
難易度はMediumです
以下のような入力が与えられます
地図みたいなイメージで、1が陸、0が海を表します
隣接した陸で1つの島が作られます
求められる出力は、島の数です
以下の例では、左上、真ん中、右下に3つの島があるので、3が出力です
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
解法
端から順に見ていって、以下を繰り返します
1. 島を見つけたら、その島の陸を、全て訪問済みにする
2. 島カウンターを1足す
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
#島の陸を全て訪問済みにする
def check(i,j):
if grid[i][j]=="1":
#訪問済みにする
grid[i][j]="2"
#上下左右の隣接した陸を、再帰的に訪問済みにする
if i-1>=0:
check(i-1,j)
if j-1>=0:
check(i,j-1)
if i+1<=len(grid)-1:
check(i+1,j)
if j+1<=len(grid[0])-1:
check(i,j+1)
#島カウンター
count=0
#grid[0][0]から順に見ていく
for i in range(len(grid)):
for j in range(len(grid[0])):
#陸だったら
if grid[i][j]=="1":
#島の陸を全て訪問済みにする
check(i,j)
#島カウンター1足す
count+=1
return count
Author And Source
この問題について(LeetCode「200. Number of Islands」解説), 我々は、より多くの情報をここで見つけました https://qiita.com/wadayamada/items/c0ac42d1c323a975941d著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .