Kuehar's Blog

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 , &

LeetCodeのEasy問題を解いて勉強するSwift Last Stone Weight編 新しくSwiftを触ることになりそうなので ひとまずコードを書いてみることにする。 LeetCodeのEasy問題は比較的解き方を知っている(はず)なので、Python3で書いていた部分をどのような書き方に直すのかを色々思い出しつつ試行錯誤していく。 書いている人のレベル感 Swiftビギナー。基本的な文法すらあやふやなので始めて数日レベルと言っても過言ではない。 LeetCode お題が与えられ、その内容に合わせてコードを書き、提出して合ってるかどうかを確認できる。 問題はソフトウェアエンジニアのコーディング面接で出されたお題をそのまま引用していることがほとんど。 前回 LeetCodeのEasy問題を解いて勉強するSwift Invert Binary Tree編 Last Stone Weight Last Stone Weight 与えられた数値が入っている配列の中に入っている最も大きい値と2番目に大きい値をぶつける。 ぶつける時に値がイコールなら両方消える。値が異なる場合には両方とも削除し、最も大きい値から2番目に大きい値を引いた値を配列に追加する。 これを繰り返し、配列内に値が1個、または0個になるまで繰り返す。1個 残った場合はその値を戻り値として返却し、0個の場合は0を返す。 class Solution { func lastStoneWeight ( _ stones : [ Int ] ) - > Int { var stones = stones . sorted ( by : > ) while stones . count > 1 { let smaller_stone = stones . remove ( at : 1 ) stones [ 0 ] - = smaller_stone stones = stones . sorted ( by : > ) } return stones [ 0 ]

LeetCodeのEasy問題を解いて勉強するSwift Invert Binary Tree編 新しくSwiftを触ることになりそうなので ひとまずコードを書いてみることにする。 LeetCodeのEasy問題は比較的解き方を知っている(はず)なので、Python3で書いていた部分をどのような書き方に直すのかを色々思い出しつつ試行錯誤していく。 書いている人のレベル感 Swiftビギナー。基本的な文法すらあやふやなので始めて数日レベルと言っても過言ではない。 LeetCode お題が与えられ、その内容に合わせてコードを書き、提出して合ってるかどうかを確認できる。 問題はソフトウェアエンジニアのコーディング面接で出されたお題をそのまま引用していることがほとんど。 前回 LeetCodeのEasy問題を解いて勉強するSwift Binary Search編 Invert Binary Tree Invert Binary Tree 与えられたバイナリツリーをInvert(反転)させて root を返す関数を書く。 /** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val = 0; self.left = nil; self.right = nil; } * public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val = val * self.left = left * self.right = right * } * } */ class Solution { func invertTr

LeetCodeのEasy問題を解いて勉強するSwift Binary Search編 新しくSwiftを触ることになりそうなので ひとまずコードを書いてみることにする。 LeetCodeのEasy問題は比較的解き方を知っている(はず)なので、Python3で書いていた部分をどのような書き方に直すのかを色々思い出しつつ試行錯誤していく。 書いている人のレベル感 Swiftビギナー。基本的な文法すらあやふやなので始めて数日レベルと言っても過言ではない。 LeetCode お題が与えられ、その内容に合わせてコードを書き、提出して合ってるかどうかを確認できる。 問題はソフトウェアエンジニアのコーディング面接で出されたお題をそのまま引用していることがほとんど。 前回 LeetCodeのEasy問題を解いて勉強するSwift Valid Parentheses編 Binary Search Binary Search 与えられた配列(数値が入っている)にtargetが存在する場合はその数値が存在するインデックスを、存在しない場合には -1 を返す関数を書く。 class Solution { func search ( _ nums : [ Int ] , _ target : Int ) - > Int { var left = 0 var right = nums . count - 1 while left <= right { let mid = left + ( right - left ) / 2 if nums [ mid ] == target { return mid } else if nums [ mid ] < target { left = mid + 1 } else { right = mid - 1 } } return - 1

LeetCodeのEasy問題を解いて勉強するSwift Valid Parentheses編 新しくSwiftを触ることになりそうなので ひとまずコードを書いてみることにする。 LeetCodeのEasy問題は比較的解き方を知っている(はず)なので、Python3で書いていた部分をどのような書き方に直すのかを色々思い出しつつ試行錯誤していく。 書いている人のレベル感 Swiftビギナー。基本的な文法すらあやふやなので始めて数日レベルと言っても過言ではない。 LeetCode お題が与えられ、その内容に合わせてコードを書き、提出して合ってるかどうかを確認できる。 問題はソフトウェアエンジニアのコーディング面接で出されたお題をそのまま引用していることがほとんど。 前回 LeetCodeのEasy問題を解いて勉強するSwift Valid Palindrome編 次回 LeetCodeのEasy問題を解いて勉強するSwift Binary Search編 Valid Palindrome Valid Parentheses 与えられた文字列の括弧の種類と数がイコールであるかを判定する関数を書く。 class Solution { func isValid ( _ s : String ) - > Bool { var stack : [ Character ] = [ ] for c in s { switch c { case "(" : stack . append ( ")" ) case "{" : stack . append ( "}" ) case "[" : stack . append ( "]" ) default : guard c == stack . popLast ( ) else { return false } }

LeetCodeのEasy問題を解いて勉強するSwift　Valid Palindrome編 新しくSwiftを触ることになりそうなので ひとまずコードを書いてみることにする。 LeetCodeのEasy問題は比較的解き方を知っている(はず)なので、Python3で書いていた部分をどのような書き方に直すのかを色々思い出しつつ試行錯誤していく。 書いている人のレベル感 Swiftビギナー。基本的な文法すらあやふやなので始めて数日レベルと言っても過言ではない。 LeetCode お題が与えられ、その内容に合わせてコードを書き、提出して合ってるかどうかを確認できる。 問題はソフトウェアエンジニアのコーディング面接で出されたお題をそのまま引用していることがほとんど。 前回 LeetCodeのEasy問題を解いて勉強するSwift Two Sum編 次回 LeetCodeのEasy問題を解いて勉強するSwift Valid Parentheses編 Valid Palindrome Valid Palindrome 与えられた文字列が回文であるかを確認する関数を書く。 いわゆるTwo Pointerで解く。 最初ループ処理をrepeat while文で書いていたけどwhile文でも書けるんだっけ？となって書き直した。 そもそもrepeat while文とwhile文の違いってなんぞや？となったので調査。 repeat while →ループ条件に関わらずループ処理を一回だけ 必ず 実行する『while文』」 while →ループ条件を確認し、 条件に合致した場合にのみ ループ処理が行われる。 class Solution { func isPalindrome ( _ s : String ) - > Bool { if s . isEmpty { return true } let StringArray = Array ( s ) var pointer_1 = 0 var pointer_2 = s . count - 1 // 前からのポインターと後ろからのポイン

二分探索の書き方 なぜこのような書き方をしなければならないのか？ 二分探索の書き方 を実装するときにPythonでは中間値の宣言を mid = ( left + right ) // 2 で済みますが、Javaでは以下のような書き方をする必要があります。 mid = left + ( right - left ) / 2 ; ちなみにこれはC++にも当てはまります。 mid = left + ( right - left ) / 2 ; なぜこのような書き方をしなければならないのか？ 何故このような書き方をしなければならないかというと、仮に left + right の値が 2^31-1 よりも大きければ、オーバーフローして負の値になるからです。 例えば、Javaでそのような長さの配列が与えられ、読み込んでしまった場合には例外として ArrayIndexOutOfBoundsException が発生します。 C++の場合には不正な書き込みが発生し、メモリ破壊などに繋がることもあります。 Pythonでは整数値にはオーバーフローがなく、オーバーフローを意識するような処理を書かなくても処理を行うため、とてつもなく大きな値でも計算時の精度は落ちません。 二分探索を書くときには気をつけようってことで一応メモを残しておきます。

この記事を書いた理由 この記事を書いた理由 最近買った Elements of Programming Interviews in Java: The Insiders’ Guide にて以下のようなコードがあったため。 これ自体は書いてあるコメントの通り配列 A と pivotIndex を引数に貰い、最初に pivotIndex より小さな値、その後に pivotIndex と同じ値、その後に pivotIndex よりも大きな値の順に配列を並び替えるというアルゴリズム。 Enum に馴染みが余りなかったため気になって調べた。 列挙型といい、使うと定数を宣言するのに読みやすいコードになるらしい。 そしてその後にちょくちょく登場する ordinal 。これは enum 型から列挙した内容の順番を取り出し、比較に使えるというもの。 定数を列挙できるのは便利なように見えるので使えたら使いたい。 でも使わないんだろうなぁ・・・ そういえばこの本はKindle版で売っていたので買いました。やっぱり電子書籍だと自炊しなくて良いから楽ですね。

出典 Elements of Programming Interviews in Python: The Insiders’ Guide (English Edition) 問題 数値の入った配列が渡されます。 偶数の値が最初に現れるように配列の値を並べ替えなければしてください。 なお、追加で配列を用意してはなりません。 解法 # List[int] -> None def even_odd ( A ) : next_even , next_odd = 0 , len ( A ) - 1 while next_even < next_odd : if A [ next_even ] % 2 == 0 : next_even += 1 else : A [ next_even ] , A [ next_odd ] = A [ next_odd ] , A [ next_even ] next_odd -= 1 # Time Complexity O(N) # The additional space complexity O(1) 値が2で割り切れる時はイテレーションのインデックスを後ろにずらし、そうでない場合には入れ替え（スワップ）と後ろのインデックスを前にずらすことで比較的容易に実装が出来ます。

最長部分共通問題を解いているときに 最長部分共通問題を解いているときに 気になったので調べてみた。 最長共通部分列(Common Longest Subsequence) の問題を解いている最中にこの記事を読んでいて、あれ？これだと最長の共通部分が何文字分あるのか返せてないな、でも二次元配列ってどう返すんだっけ？ となったので調査。 ちなみに max(dp) や max(max(dp)) では返せませんでした。 結論としては ここ が参考になった。 大人しく従ったら上手く返せたのでメモがてら記事を書いておく。 max ( list ( map ( lambda x : max ( x ) , dp ) ) ) これで返すか、 from itertools import chain list ( chain ( * a ) ) max ( chain ( * a ) ) こう返すかの二択っぽい。 ちなみにつまづいていた最長部分共通問題は これ で、ソースコード(メモ化とDPを試した)は ここ 。 時間がある人はぜひ解いてみてください。

けんちょん本を読むと・・・ けんちょん本 ってAmazonで検索すると出るんですね。知らなかった。 本題に戻りますが、この本には二分探索法の章があります。 C++の話 その中でC++のライブラリである std::lower_bound() を使う際に得られる情報について記述があります。 std::lower_bound() の使用自体はソート済みの配列 a と key が存在するかという内容のライブラリです。 もう少し具体的に記述すると、 a[i] >= key という条件を満たす最小の添字 i を返す(この時の計算量は配列Nに対してO(logN))、というものなのですが、これは単に配列の中に存在するか否か、だけのライブラリではないという事みたいです。 例えば、 配列のなかに key が存在しない場合、与えた key 以上の値の範囲での最小値を取得 配列のなかに値 key が複数あった時、その内の最小の添字を取得 といったような使い方があるようで、これについて学んだ時、Pythonで似たようなライブラリは無いのかパッと思い浮かばなかったので、調べてみました。 Pythonの話 Pythonでは bisect が該当するようで、何度か使ったことはあったが詳しい仕様を思い出せなかったので、実際にドキュメントを読みながら使い方を見てみました。 import bisect a = [ 3 , 8 , 11 , 18 , 27 , 31 ] bisect . bisect_right ( a , 20 ) # 4 print ( bisect . bisect_right ( a , 11 ) ) # 3 print ( bisect . bisect_left ( a , 11 ) ) # 2 この配列に 18 を足してみましょう。すると bisect は以下のような振る舞いをします。 import bisect a = [ 3 , 8 , 11 , 18 , 18 , 27 , 31 ] bisect . bisect_right ( a , 18 ) # 5 bisect . bisect_left ( a , 18 ) # 3 lower_boundはbisect_left

計算量の改善 って意外と取り組む事がないなぁと最近思い始めて、一回解いた問題の回答をより良くできる方法を考えたりしている今日この頃です。 昔に比べてメモリの性能が改善しているためよっぽど致命的なアルゴリズムを設計しない限りはなんとかなる ソートなどのアルゴリズムはライブラリのものを呼び出せばなんとかなる etc… 色々な理由はあると思いますが、だからと言ってサボっていい理由にはならないと思うのでいい例を探していたらこんな問題を見つけました。 Majority Element 整数を格納したリストが与えられるのでそのリストの中で最も多い値を返してください、という問題です。 例えば、 Example 1: Input: nums = [3,2,3] Output: 3 Example 2: Input: nums = [2,2,1,1,1,2,2] Output: 2 といったような形式です。 今回はSolutionにもある通り、それぞれの問題に対する取り組み方を書きます。 例えばBruteforce。これはとにかく全パターンをしらみつぶしに実行して答えを導く、というものです。 class Solution : def majorityElement ( self , nums ) : majority_count = len ( nums ) // 2 for num in nums : count = sum ( 1 for elem in nums if elem == num ) if count > majority_count : return num 解けるものの、for文で2回走査しているため、計算量がO(N^2)とお世辞にもいいとは言えません。 では次にハッシュマップに格納して解く例です。 class Solution : def majorityElement ( self , nums ) : counts = collections . Counter ( nums ) return

冪乗のお話。 解答 冪乗のお話。 3の冪乗かどうかを判定するプログラムを求められました。 326. Power of Three 整数型の値、 n が引数として与えられた場合、それが3の冪乗かを判定し、冪乗ならば True 、冪乗でなければ False を返してください、っていう問題です。 なお、 n の値には以下の制約が存在します。 -2^31 <= n <= 2^31 - 1 さて、どうしましょう？ってことでメモ。 解答 とりあえず解ける解答。 class Solution : def isPowerOfThree ( self , n : int ) - > bool : if n == 0 : return False if n == 1 : return True for i in range ( 31 ) : if pow ( 3 , i ) == n : return True return False # Runtime: 240 ms, faster than 5.15% of Python3 online submissions for Power of Three. # Memory Usage: 14.4 MB, less than 13.91% of Python3 online submissions for Power of Three. pow関数 を使っています。 pow 関数は引数に (基数、冪乗) を取っています。ここでの使い方は、31乗までを範囲としているため、for文で1~31までの値を回します。 pow(3,1) == n pow(3,2) == n ............. といったように3の1乗から31乗までを調べます。 ただし、31という値を意識しすぎる余り、かなり遅くなっています。 遅い理由としては、正しくない場合、31回も回すことになっているからです。 しかし、解けるだけでいいのであればこれ

この記事を書く理由 問題 解答 この記事を書く理由 LeetCodeでTop Interview Questions(面接のコーディング試験で聞かれやすい問題を集めたやつ)のEasy問題を解いている時にビット操作を求められたので念のため書いておきます。 問題 Number of 1 Bits 解答は ここ 。 符号なしの整数を引数として受け取り、その整数が持つ「1」ビットの数（ ハミングウェイト とも呼ばれる）を返す関数を書いてください、という問題です。 Example 1: Input: n = 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits. Example 2: Input: n = 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit. Example 3: Input: n = 11111111111111111111111111111101 Output: 31 Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits. Constraints: - The input must be a binary string of length `32`. 解答 # O(N) Solution class Solution : def hammingWeight ( self , n : int ) - > int : bits = 0 for i in range ( 32 ) :

再帰とメモ化 問題 再帰とメモ化 問題解決力を鍛える!アルゴリズムとデータ構造 というアルゴリズムとデータ構造を学ぶのに良い本があります。 LeetCodeの問題を解いていた時に、この本の中で解説されていた例とすごく被っている内容があったので、記事にしてみようと思いました。 問題 1137. N-th Tribonacci Number 難易度はEasy。 再帰の入門にうってつけです。 問題解決力を鍛える!アルゴリズムとデータ構造 の4章の解説にもある通り、再帰関数のテンプレートは (戻り値の型) func(引数){ if(ベースケース){ return ベースケースに対する値; } func(次の引数) return 答え } 問題解決力を鍛える!アルゴリズムとデータ構造 第4章 設計技法(2):再帰と分割統治法より引用 といったものです。 今回解く問題は、 トリボナッチ数列Tnは次のように定義される。 T0 = 0, T1 = 1, T2 = 1, そして n >= 0 で Tn+3 = Tn + Tn+1 + Tn+2 となる。 nが与えられたとき、Tnの値を返す。 という内容です。 では、こちらをPythonでかつ再帰で解いてみましょう。 class Solution: def tribonacci(self, n: int) -> int: if n == 0: return 0 elif n == 1 or n == 2: return 1 return self.tribonacci(n-1) + self.tribonacci(n-2) + self.tribonacci(n-3) # Time Limit Exceeded しかし、これだとnが 30の時に時間切れとなり、正解とは認められません。 これは再帰で同じ処理が重複し、関数の呼び出し回数がとてつもない回数になっているためです。 ではこれを解決してみましょう。 class Solution: def tribonacci(self, n: int) -> int: memo =

特定の値まで素数を生み出すアルゴリズムとか 以下のようにリストで真偽値を管理するやり方で書くといいらしい。 Elements of Programming Interviews in Python  より。 # Given n, return all primes up to and including n. def generate_primes(n): primes = [] is_prime = [False,False] + [True] * (n-1) for p in range(2,n+1): if is_prime[p]: primes.append(p) for i in range(p*2,n+1,p): is_prime[i] = False return primes n = 100 print(generate_primes(n)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

リストの中から被っている値を見つけよう！！ 基本 問題 解法 改良前 改良後 リストの中から被っている値を見つけよう！！ という話。 見つけてその値を削除するなり、被っている値の数を数えるなり、被っている値は何なのかを返すなりは別にいいとして、個人的な方法をメモ代わりに取っておく。 基本 今回は考えやすいようにLeetCodeの問題を例に考えてみます。 問題 例えばこちら。 287. Find the Duplicate Number 難易度はMediumです。 問題としては与えられた数字のみのリストの中に1つだけ2つ存在する値があるのでそちらを探して欲しいという問題です。 例としては以下のような感じ。 Example 1: Input: nums = [1,3,4,2,2] Output: 2 Example 2: Input: nums = [3,1,3,4,2] Output: 3 Example 3: Input: nums = [1,1] Output: 1 Example 4: Input: nums = [1,1,2] Output: 1 解法 改良前 これの解放としてパッと思い浮かぶものとしては、二つのfor文で二つの値を比較しながら被っている値があれば行いたい処理を行う、というもの。 ただ、与えられたリストがソートされていないのでまずソートしないとその比較はできなくなります。 試しにPython3で書いてみました。 class Solution : def findDuplicate ( self , nums : List [ int ] ) - > int : ans = 0 nums = sorted ( nums ) for i in range ( len ( nums ) ) : for j in range ( i + 1 , len ( nums ) ) : if nums [ i ] == nums [ j ] : ans =

Arrayでのインクリメント スパッと思いつかなかったのでメモメモ。 ちなみに具体例としては、 array1 = [1,1,1] array2 = [1,7,9] だったら array1 = [1,1,2] array2 = [1,8,0] みたいな感じになるやつ。 実はLeetCodeでも解いたことがあったけど、 Plus One どうせならPythonっぽい答えを作ってみたかったので色々調べた感じ下のやつが良さげ。 def increment ( A : List [ int ] ) - > List [ int ] : A [ - 1 ] += 1 for i in reversed ( range ( 1 , len ( A ) ) ) : if A [ i ] != 10 : break A [ i ] = 0 A [ i -1 ] += 1 else : if A [ 0 ] == 10 : A [ 0 ] = 1 A . append ( 0 ) return A といった感じで行ける。あと読みやすい。 実行してみたら速度も気のせいか少し速くなった。 元々の解答 class Solution : def plusOne ( self , digits : List [ int ] ) - > List [ int ] : if digits [ - 1 ] < 9 : digits [ - 1 ] += 1 return digits elif digits [ 0 ] == 9 and len ( digits ) == 1 : return [ 1 , 0 ] else : digits [ - 1 ] = 0 digits [ 0 : - 1 ] = self . plusOne ( digits [ 0 : - 1 ] )

概要 問題 解法 概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day111「682. Baseball Game」 次回 その内 Twitter やってます。 問題 500. Keyboard Row 難易度はEasy。 問題としては、単語のリスト words が与えられます。 下の画像のような 英字キーボードの一行に存在するアルファベットだけで入力できる単語のみ をリスト形式で返してください、という問題です。 Example: Input: [“Hello”, “Alaska”, “Dad”, “Peace”] Output: [“Alaska”, “Dad”] Alaska と Dad は共に真ん中のキーボードの列に所属するアルファベットのみで構成されていますのでリストで返されています。 解法 class Solution : def findWords ( self , words : List [ str ] ) - > List [ str ] : first = [ "q" , "w" , "e" , "r" , "t" , "y" , "u&q