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では中間値の宣言を 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 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を試した)は ここ 。 時間がある人はぜひ解いてみてください。

組み込み型を知ること Elements of Programming Interviews in Python: The Insiders’ Guide 数値関連 abs(x) math.ceil(x) math.floor(x) min(x,y) max(x,y) pow(x,y) sqrt(x) 組み込み型を知ること お仕事で書かないのでどうしても行き当たりばったりで書くことが多いのでたまには地味な基礎的なこととか書きたいなと。 何回かに分けて書きます。 Elements of Programming Interviews in Python: The Insiders’ Guide 以前 こちらの記事 でも紹介したいわゆるコーディングインタビュー対策用の本、 Elements of Programming Interviews in Python: The Insiders’ Guide 。 この本の中にChapter4にPrimitive Typesという章があったので、せっかくだし記事にしようとなりました。 公式の組み込み関数はこちら 数値関連 abs(x) 数値xの絶対値 |x|を求めるときに。 >> > abs ( - 10 ) 10 math.ceil(x) 公式のmath(数学関数)はこちら math.ceil は天井、引数として与えた x 以上の最小の整数を返します。 例えば、 >> > import math >> > math . ceil ( 2.17 ) 3 といったように、小数に関してもカバーしています。 math.floor(x) 対して math.floor です。 ceil(天井) と反対の床を意味することから、真逆の結果を返すような関数であることが想像できますよね。 返り値として x の「床」 ( x 以下の最大の整数) を返します。 >> > math . floor ( 2.17 ) 2 min(x,y) max(x,y) これらは書かなくても知ってるよ！となる気がするので軽く。 min(x,y) で x,y が数値型の場合、 x,y のいず...

Webスクレイピングとか 試していたらこれが突然出た。 macOS用公式インストーラーのPython 3.6でCERTIFICATE_VERIFY_FAILEDとなる問題 という記事に解決策が書いてあったが、 python.orgで配布されているmacOS用の公式インストーラーでインストールしたPython 3.6を使い、 urllib.request.urlopen() で https:// のWebページを取得しようとすると、以下のエラーが発生します。 で、このタイトルのエラーに当たっていたよう。 私の場合はPython3.8.5を使っていたので $ /Applications/Python\ 3.8/Install\ Certificates.command というコマンドをターミナルで叩くことで事なきをえた。 読んでないのが悪いとはいえこれはハマる人が多いんじゃなかろうか。

たまたま目にしたので Create Phone Number たまたま目にしたので CodeWars なるサイトがあるとのことで試しに登録してみた。 サイトで問題を解いてコーディングスキル上げてね！みたいなサイトです。 Create Phone Number そこで２問目(3問目だったかも)で出てきた Create Phone Number についてPythonで解いていました。 この問題はリストで10桁の数字が与えられるので、それらの値を電話番号のフォーマット、下のような形式で変換して返してほしいという問題です。 create_phone_number ( [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 0 ] ) # => returns "(123) 456-7890" 僕は愚直にfor文の中で分岐を何度も挟むことで作る、という方法を取りました。 def create_phone_number ( n ) : phone_number = '(' for i , num in enumerate ( n ) : if i < 3 : phone_number += str ( num ) if i == 2 : phone_number += ') ' elif i <= 13 : phone_number += str ( num ) if i == 5 : phone_number += '-' return phone_number でもよく見たらこれって書く量も多いし、なんかあんまりいけてないなぁと思っていたところ他の方の回答を見たところ、こんな解答を見つけました。 def create_phone_number ( n ) : return "({}{}{}) {}{}{}-{}{}{}{}" . ...

djoserとは 使い方 djoserとは djoser とはDjango REST Framework上での基本的なユーザー認証や登録などの認証周りをサポートしてくれるライブラリです。 カスタムモデルに対しても使え、Djangoのコードを再利用するような形をとるのではなく、Single Page Application(以下SPA)によりフィットするようなアーキテクチャを目指して作られています。 今回はdjoserの最もシンプルな認証機能の実装について書きます。 なお、この認証はセキュリティの面などから実際に使用するべきではなく、以下のJWT認証のようなより強固なセキュリティの設定があります。 あくまでお手軽な認証として紹介します。 ソースコードは こちら なお、以下の全てが導入後にエンドポイントとして使えます。 /users/ /users/me/ /users/confirm/ /users/resend_activation/ /users/set_password/ /users/reset_password/ /users/reset_password_confirm/ /users/set_username/ /users/reset_username/ /users/reset_username_confirm/ /token/login/ (Token Based Authentication) /token/logout/ (Token Based Authentication) /jwt/create/ (JSON Web Token Authentication) /jwt/refresh/ (JSON Web Token Authentication) /jwt/verify/ (JSON Web Token Authentication) Getting started djoser関連の記事を他にも書いています。 djoserを使ったDjango REST Frameworkでの認証機能の実装 djoserを使ったDjango REST FrameworkでのJWT認証機能の実装 なお、今回はJWT認証を用いたユーザー認証を実装することとします。 使い方 途中...

スタック スタックについて 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 逆ポーランド記法の計算 ...

けんちょん本を読むと・・・ けんちょん本 って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 ...

意外と意識せずに使っている・・・ ということで。 この _ ってなんですかい？ 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]