Kuehar's Blog

スタック スタックについて 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

アップデートしたら使えるようになっていた 公式 からリリースされている通り、 BraveのiPhoneとiPadアプリのユーザーは、 新機能「Playlist」 を、 v1.25版 から利用可能になりました。これはユーザーが動画・音声コンテンツを好きなプラットフォームから保存し、楽しめるようにする機能です。Brave Playlistを使うと、ユーザーは複数のプラットフォームから選んだコンテンツを1つのプレイリストに保存して、いつでも、どこでもアクセスできます。音楽、動画、ポッドキャストなどを、通勤や旅行、日常生活で楽しむのに最適な機能です。 オフライン でYouTubeの動画を手元にダウンロードし、どこでも視聴可能になる機能が今回のアップデートで追加されました。 いやいや、これ相当便利ですね。 Braveを使っている方なら、Braveを通してYouTubeを視聴すれば広告を見なくて済むということを知ってらっしゃるとは思うのですが、まさかオフラインでも視聴可能になるとは・・・ AdBlockなどを活用すれば他のブラウザでも広告をブロックすること自体はできたのですが、まさか無償でブラウザ側が実装してくれるとは！ ただ、広告収入をメインにしているYouTube側から規制されそうな気もしますが・・・ どうなんでしょうか？ ちなみにこの機能、よくみたら5日前の段階でリリースされていたようなのですが、チェックできていなかったので先ほどアップデートをしたときに驚きました。 使い方 直感的に使えるので、すぐに使い方は分かるようになるかと思います。 1. YouTubeを開く 2.保存したい動画を開く。この時、画面下部に「Brave Playlistに追加する」と表示されるのでタップ。 3.画面右下の「・・・」をタップし、表示されたPlaylistをタップ 4.ダウンロードが始まっているので、完了するまで待つ。 5.ダウンロードが完了次第いつでもどこでも楽しめるように！ これで完了です。 例えば機内モード(左上の飛行機マークに注目してください)にしたとしても問題なく動画は再生されます。 これで広告無し、しかもオフラインでもYouTubeを楽しめるようになりました！

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