Kuehar's Blog

:= ⇦なんか可愛い ぼちぼち遊びで解いてるLeetCode。 374. Guess Number Higher or Lower を解いた後にいい感じの解き方あるかなーってDiscussを流し見していると、 こんな解答があった。 やってることは自分で実装した二分探索と同じことをやっているが、その中の解法でこんな書き方あったなってことでメモがてら残しておく。 ちなみにその書き方はこれ。 while ( res : = guess ( myGuess ) ) != 0 : 名前を知らなかったけどWarlus演算子っていうらしい。セイウチって呼んでた。 := 　⇦目と牙に見えますよね？だからWarlus(セイウチ)ってことらしいです んで、上のコードのやっていることとしては res = guess ( myGuess ) while res != 0 : と同じで、これを1行で書けるよーってこと。 機能自体は Python3.8 のリリースノートに書いてあったので結構前に使えるようになっていたはずなのですが、そこまで最新機能を追いかけていなかったのでここでメモとして残して勉強したってことで。

スタック スタックについて Pythonでのスタック利用例 Pythonでの表記法と注意点 連結リストの要素を逆転させる 逆ポーランド記法の計算 ディレクトリ構造の短縮化 スタック について改めて使い道を模索してみたのでメモ。 スタックについて 底のある箱の中に積み木を積んでいくイメージ。 いわゆるLIFO(last in first out)、最後に入れたものを最初に取り出す、というデータ構造。 要素を取り出す時の操作を pop 、要素を入れる時の操作を push という。 スタックを連結リスト、もしくは配列で実装した場合のpop、pushの操作はO(1)の計算量となります。 Pythonでのスタック利用例 Pythonでの表記法と注意点 他の言語と同様に、Pythonでも Stack が組み込み関数として用意されています。 ここで注意すべきなのは上記で用意したPythonでリストを用いてスタックを表す場合には push ではなく、 append を使う点です。 スタックとして使う場合は以下のように要素の出し入れを行います。 >> > stack . append ( 6 ) >> > stack . append ( 7 ) >> > stack [ 3 , 4 , 5 , 6 , 7 ] >> > stack . pop ( ) 7 >> > stack [ 3 , 4 , 5 , 6 ] >> > stack . pop ( ) 6 >> > stack . pop ( ) 5 >> > stack [ 3 , 4 ] 他にもスタックには様々な使い道があります。 連結リストの要素を逆転させる def reverse_linked_list ( head ) : nodes = [ ] while head : nodes . append ( head . data ) head = head . next 逆ポーランド記法の計算

意外と意識せずに使っている・・・ ということで。 この _ ってなんですかい？ for _ in range ( n ) って思ったりするも深くは考えていなかったので調べてみた。 他人のコードを読むと使う人は結構使われていらっしゃるのですが、よく知らないまま使うのって気持ち悪いよね。 ループのカウンタがループ内で使用されていないことを示すために使うようで、 arr1 = [ 0 for _ in range ( 5 ) ] arr2 = [ 0 for i in range ( 5 ) ] arr1 と arr2 を比べた時に、 i よりも _ の方がループのカウンタとして使っているということが分かりやすいですよね。 他にも、 for _ in range ( 10 ) : print ( _ ) という使い方は良くないです。 なぜならば出力という形でfor文の中で使ってしまっているから。 対して、 for _ in range ( 10 ) : print ( "Hello world" ) これだとループのカウンタとして使えているので良い例かと。

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

概要 問題 解法 概要 海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。 どうやら多くのエンジニアはその対策として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なるサイトで対策を行うようだ。 早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。 と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。 ただ、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