LeetCode 1000000本ノック【200. Number of Islands】

19150 ワード
コーディング面接 leetcode 初学者向け Python Python テキストリンク

目次

No. 項目
1 概要
2 問題
3 解法
4 メイキング

概要

●発端
　・競プロ初心者、コーディング面接でズタボロにされ、
　・最低限のアルゴリズム学習とコーディング力強化を習慣化するため記事化
●環境
　・LeetCodeブラウザ上で実装（vscodeに拡張機能にするかもシレナイ）
　・言語はpython3
●その他ルール
　・google検索は自由に（直接的なLeetCodeの問題解説ページはNG）
　　（60分実装して実装出来なければ解説ページ参照）
　・コーディング面接対策のために解きたいLeetCode 60問から問題選出
　・「1000000」は任意の2進数とする

問題

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

⇨「0を海、1を陸に見立てたグリッド図で、島は何個あるのか？
　ちなみに島ってのは上下左右を海で囲われた陸の集まりだよ」
　と書いてあります。知らんけど

ex
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","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]

解法

実施時間：60分オーバー

class Solution:

    def numIslands(self, grid: List[List[str]]) -> int: 
        def adjoining_land_check(grid,i,j):
            #確認前陸(1)かそれ以外（確認後陸(2)か海(0)）か判別
            if grid[i][j] == "1":
                #確認済み(2)に変更
                grid[i][j] = "2"
                #座標の上下左右が１なら2にしてその上も確認を繰り返す
                #上が存在するエリア
                if i-1>=0:
                    adjoining_land_check(grid,i-1,j)
                #右が存在するエリア
                if j-1>=0:
                    adjoining_land_check(grid,i,j-1)
                #下が存在するエリア
                if i+1<=len(grid)-1:
                    adjoining_land_check(grid,i+1,j)
                #左が存在するエリア
                if j+1<=len(grid[0])-1:
                    adjoining_land_check(grid,i,j+1)
        island_count = 0  
        #gridを左上〜右下まで横順で確認ループ
        for i,inner_grid in enumerate(grid):
            for j,area in enumerate(inner_grid):
                if grid[i][j] == "1":
                    #引数 グリッド grid 座標 var,hor (ij)
                    adjoining_land_check(grid,i,j)
                    #大陸数に+1
                    island_count +=1
        return island_count

※色々と余裕がなかったので汚いままですがご容赦を

メイキング

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        #gridを左上〜右下まで横順で確認ループ
            #確認前陸(1)かそれ以外（確認後陸(2)か海(0)）か判別
                #確認前陸(1)なら大陸数に+1
                #確認前陸(1)なら確認済み(2)に変更
                #上下左右が確認前陸(1)があれば確認済み(2)に変更してその上下左右もループ確認
            #2or0なら次を確認しに行く

とりあえずはざっと設計してみる。
肝は　#上下左右の確認〜　のところだなと思ったけども、
とりあえず詳細は後回しにしてコーディングしていくことに。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        island_count = 0   
        for i,inner_grid in enumerate(grid):
            for j,area in enumerate(inner_grid):
                if area == "1":
                    island_count +=1
                    grid[i][j] = "2"
                    #上下左右が確認前陸(1)があれば確認済み(2)に変更してその上下左右もループ確認


                #2or0なら次を確認しに行く
        return island_count

25分程度で全体的には出来ました。
（この時点では　island_count　は単純に　"1"　の数を返します。）
それでは問題の箇所に入っていきます。まずは仮コーディングしてみる。

                    #上は1か？
                    　　#2にする
                    　　　　#さらに上は1か？
　　　　　　　　　　　　　　　　　#......
                    #右があるか？
                        #同じ感じ
                    #下があるか？
                        #同じ感じ
                    #左があるか？
                        #同じ感じ

際限なく確認せなあかんやろ。。。となるところです。1ヶ月前の自分では。
今は「再帰的」という言葉を知っているので余裕の予感がしましたが問題は時間。
（残り20分）

class Solution:

    def numIslands(self, grid: List[List[str]]) -> int:
        island_count = 0   
        #gridを左上〜右下まで横順で確認ループ
        for i,inner_grid in enumerate(grid):
            for j,area in enumerate(inner_grid):
                #確認前陸(1)かそれ以外（確認後陸(2)か海(0)）か判別
                if area == "1":
                    #大陸数に+1
                    island_count +=1

                    #確認済み(2)に変更
                    grid[i][j] = "2"
                    #上下左右が確認前陸(1)があれば確認済み(2)に変更してその上下左右もループ確認
                    #引数 グリッド grid 座標 var,hor (ij)
                    def adjoining_land_check(grid,i,j):
                        #座標の上下左右が１なら2にしてその上も確認を繰り返す
                        if grid[i-1][j] == "1":
                            grid[i-1][j] == "2"
                            adjoining_land_check(grid,i-1,j)
                        if grid[i][j+1] == "1":
                            grid[i][j+1] == "2"
                            adjoining_land_check(grid,i,j+1)
                        if grid[i+1][j] == "1":
                            grid[i+1][j] == "2"
                            adjoining_land_check(grid,i+1,j)
                        if grid[i][j-1] == "1":
                            grid[i][j-1] == "2"
                            adjoining_land_check(grid,i,j-1)
                    adjoining_land_check(grid,i,j)
                    print(grid)
                #2or0なら次を確認しに行く
        return island_count

慣れない再帰処理とインナークラス実装で手こずりながらも完成しましたが。。。

Runtime Error
RecursionError: maximum recursion depth exceeded in comparison

再帰エラー。。。だと。。。
と色々確認しているうちにタイムアップで、下記の記事を参考にさせて頂きました。

LeetCode「200. Number of Islands」解説

一番問題の箇所（エラー）は再帰の中の条件ですね。
早い話が確認範囲の際限がないため無限ループになっていたよう。

誤:

if grid[i-1][j] == "1":

正:

if i-1>=0:

後は、細々したところを直して完成。

今回は難易度Mediumってのもあったけど、再帰慣れないとだなぁ。。。

データベーステーブルの挿入情報
Linuxの下でQtCreatorは検索入力方式を使って中国語を入力することができません