Kuehar's Blog

計算量の改善 って意外と取り組む事がないなぁと最近思い始めて、一回解いた問題の回答をより良くできる方法を考えたりしている今日この頃です。 昔に比べてメモリの性能が改善しているためよっぽど致命的なアルゴリズムを設計しない限りはなんとかなる ソートなどのアルゴリズムはライブラリのものを呼び出せばなんとかなる 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 ...

Braveとbitflyerが連携したらしい 連携したらしい。 ということで連携させてみよう！と思って以前登録しておいたBrave Creatorsのページを開いてみたら・・・ あれ？PayPalとしか連携できないじゃん。なんで？ なんとか連携させようと思って公式のプレスリリースを見に行ってみた。 すると こちら に解説があったので読んでいくと、 日本のクリエイターの方でBAP残高が残っている方は 、2021年4月30日までにPayPalアカウントを接続していただき、2021年5月8日に支払いを受けてください。BAPはBATとの交換ができず、この期間に支払われなかったBAP残高はクリエイター向け管理画面では表示されなくなります。確実に5月8日にBAP残高の支払いを受けるためには、PayPalアカウントの連携を行う必要があります。ご不明点がある場合、 サポート（日本）にお問い合わせください 。 5月8日にBAPの最終的な支払いが完了すると、PayPalアカウントはcreators.brave.comアカウントに表示されなくなり、クリエイターの方はbitFlyerアカウントを連携して新しいBATシステムを利用することになります。 ああ、受け取ったBATがあるからダメなのか。 ということでBATをみてみる。 やはり受け取り分がありました。 色々調べてみると、自身のアカウントを削除して再登録すれば大丈夫そう？ という事で思い切ってリセットしてみましょう。 ※リセットすると自身の受け取ったBATは失われてしまいます。失いたくない人はこの方法を行わないでください。 自身のBrave Creatorsのアカウントにログインする。 自身のBrave Creatorsのプロフィール欄を開く。 ページの一番下のアカウントを削除するをクリックし、アカウントを削除する。 これで無事削除されました。 そして新しくアカウントを作成してみます。 すると・・・ 無事bitflyerとの連携可能なアカウントが作成されていますね。これでbitflyerとの連携ができそうです。よかったよかった。 受け取り分がたくさんあってきちんと手元に受け入れてから連携したい！という方は上記で紹介した公式のプレスリリースに従って、4/30までにPayPalとのアカウント接続をお...

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