LeetCodeのEasy問題を解いて勉強するSwift Climbing Stairs編

新しくSwiftを触ることになりそうなので

ひとまずコードを書いてみることにする。
LeetCodeのEasy問題は比較的解き方を知っている(はず)なので、Python3で書いていた部分をどのような書き方に直すのかを色々思い出しつつ試行錯誤していく。

書いている人のレベル感

Swiftビギナー。基本的な文法すらあやふやなので始めて数日レベルと言っても過言ではない。

LeetCode

お題が与えられ、その内容に合わせてコードを書き、提出して合ってるかどうかを確認できる。
問題はソフトウェアエンジニアのコーディング面接で出されたお題をそのまま引用していることがほとんど。

前回
LeetCodeのEasy問題を解いて勉強するSwift Last Stone Weight編

Climbing Stairs

Climbing Stairs
階段を登るとき、頂上までn段の階段があり、仮に毎回、1段か2段のどちらかを登ることができる時、何通りの登り方が存在するかを返り値として書く。

典型的な問題でけんちょん本にも記載されていた・・・はず
単純な再帰でもテストケースは通るが、それだとnの値のよっては計算量が爆発する可能性があるため、今回はメモ化再帰で解く。

関数の引数として配列を渡すときの記述を知らず、調べた。
Swiftではそのような場合に参照渡しをするときにinoutを使うようで、そして実際に呼び出す時に該当する引数の前に&を付ける。
なんか気持ち悪いと思いつつもそうしないとエラーを吐くんだからしょうがない。

あと、dpの時とかに使う配列の長さを設定して中身を何の値で埋めるか、みたいな所も勉強できた。単純な問題だけど意外と学びがあったように思える。

class Solution {
   func climbStairs(_ n: Int) -> Int {
       var memo: [Int] = Array(repeating: -1, count: n + 1)
       return climb_Stairs(0,n,&memo)
   }

   func climb_Stairs(_ i:Int,_ n:Int,_ memo: inout[Int]) -> Int {
       if i > n{
           return 0
       }

       if i == n{
           return 1
       }

       if memo[i] > 0 {
           return memo[i]
       }

       memo[i] = climb_Stairs(i+1,n,&memo) + climb_Stairs(i+2,n,&memo)
       return memo[i]
   }
}

学べたこと

配列の宣言
関数の引数の設定、引数の渡し方

このブログを検索

Kuehar's Blog