Kuehar's Blog

冪乗のお話。 解答 冪乗のお話。 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...

概要 問題 解法 概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 ゼロから始めるLeetCode 目次 前回 ゼロから始めるLeetCode Day110「1535. Find the Winner of an Array Game」 次回 その内 Twitter やってます。 問題 682. Baseball Game 難易度はEasy。 久しぶりでいろいろ忘れているのでひとまずEasy の問題を潰そうかなと思います。 問題としては、あなたは野球の試合に出場することになりました。このゲームはいくつかのラウンドで構成されており、過去のラウンドの得点が将来のラウンドの得点に影響を与える可能性があります。 ゲームの最初に、あなたは空のレコードで開始します。ops[i]はレコードに適用しなければならない第一の操作であり，以下のいずれかである． 整数 x - x の新しいスコアを記録します。 “+” - 前の2つのスコアの合計を新しいスコアとして記録します。前の 2 つのスコアが常に存在することが保証されています。 “D” - 前のスコアの2倍の新しいスコアを記録します。これは、常に前のスコアが存在することを保証します。 “C” - 前回のスコアを無効にし、記録から削除します。これは、常に前のスコアが存在することを保証するものです。 レコード上のすべてのスコアの合計を返します。 Example 1: Input: ops...

Elements of Programming Interviews in Python C++とかJavaとかで解説をしている本はあったけどPythonで解説している本はなかったので5000円ちょい出して本を買ってみた。 この本は以下の記事でたまたま知ったのだが、 【21新卒SWE】 私はこうしてGoogleに落ちた ~Googleに挑んだ120日~ 個人的にPythonを使ってLeetCodeを解いていた時期があったので読んでおいて損はないのだろうと思い、本にしては高いが楽しく時間が潰せそうだったので海外から取り寄せた。(上の記事の人のスペックが高すぎて初めて読んだ時に驚いた) もちろん英語なのでパラパラっと読むのにも時間はかかったけども、ざっと読んで見た感じアルゴリズムとデータ構造だけではなくてPythonの言語的な仕様について触れていたり、オブジェクト指向はなんぞやとかシステムデザインについてだったりとかこれ一冊を読んで場数を踏めば面接の通過率がかなり上がりそうな感じ。 今の所そういう面接とかを受けたりする予定はないけど、将来どうなるかなんて分からないし、何より面接で必要とされるということはITエンジニアとして知っておいておかないとまずいということだから格闘しながら詳細まで読んでいくべきなのかなー、と思いました。 それにしても、今の段階でもあー、Pythonでコーディング面接受けるならこれ読んどけば大丈夫そうだなって感じがするくらいデカくて分厚い。 もちろん面接に臨む以上、問題との相性の運とか募集しているポジションに合う人材とかその他諸々の要素はあるんだろうけども、僕はその場の機転が効くタイプではないのでコツコツ勉強して地道に実力を伸ばしていくしかない。 コツコツ読んでハマりそうな部分をメモって直前に思い出すだけでも全然違うし、何より業務、もしくは趣味で触ったことがあっても僕の劇弱記憶装置では覚えていても正確に説明できるか分からないので、そう言った所で自信を持って臨めるようにするためにも頑張ろ〜って感じで！ あ、ちなみにPythonを書いて競技プログラミングとかやられてる人にも良い本だとは思うのですが、英語の壁、そして日本語の本( Ｐｙｔｈｏｎで学ぶアルゴリズムとデータ構造 (データサイエンス入門シリーズ )  )とかで十分だと思うのでそういった所に...

 久しぶりにLeetCodeを開いたらヘッダーにこんな物が。 ん？こんなのあったっけ？ って思って開いてみると どうやら実際に面接形式で時間を測って問題に挑戦でき、他の人とスコアを競いあったりできるらしい。 ということでひとまず試しに一番最初の問題に挑戦してみた。 問題が二つ出題されて、片方は数字の配列が与えられて両隣の値よりも大きい値(ここではPeakと呼んでいた)のインデックスを返してね！っていう問題。 もう片方は文字列が与えられて、文字列が繰り返しになっていればTrueを、それ以外だったらFalseを返す問題。 うろ覚えだけどこんな感じでした。 これから解く人もいるかもしれないので解き方は割愛。 ちなみに僕は解いたことがあった問題だったので比較的スムーズに解けました。 解いたらこんな感じでスコアが出て、へぇー、ってなる(小並感) こういう形式で解く練習はかなり慣れるために良いのでは？と感じたので時間があるときに解いていこうと思った。 ただ、いきなり行き当たりばったりでコードを書いたりするのではなくて、しっかり紙とかに疑似コード的な奴を書きながらの方がより良い練習になりそうな気がするので次回からはそんな感じで。 にしても僕が見てなかっただけで、もともとあったのかもしれませんがとてもいい機能だと思います。なかなか制限時間ありのこういうので勉強することはなさそうですし。 では今回はここまで。

概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。 Leetcode Python3で解いています。 リンク集 この記事をストックしておくと新しい記事の追加時に通知されます。 コードだけ見たい方はこちらの Github をご覧ください。 番号はLeetCodeの問題へのリンク、問題のリンクは解説記事についてのリンクです。 間違えているリンク等あればコメント頂けると幸いです。 Day 番号 問題 難易度 1 1389 Create Target Array in the Given Order Easy 2 1108 Defanging an IP Address Easy 3 1313 Decompress Run-Length Encoded List Easy 4 938 Range Sum of BST Easy 5 1266 Minimum Time Visiting All Points Easy 6 1342 Number of Steps to Reduce a Number to Zero Easy 7 104 Maximum Depth of Binary Tree Easy 8 1302 Deepest Leaves Sum Medium 9 701 Insert into a Binary Search Tree Medium 10 1431 Kids...