アルゴリズム
この記事について Union-findに続き、コーディング面接に備える上で大事そうなデータ構造であるセグメント木を勉強したので、セグメント木を使用して解ける問題を解いてみます。 セグメント木とは? セグメント木自体の説明は、また他の方のスライドに丸投げ…
この記事について Union-findについて勉強したので、LeetCodeのNumber of Islandsという問題をUnion-findを使用して解いてみます。 Union-findとは? Union-findは素集合データ構造を操作するためのアルゴリズムで、2つの要素が同じ集合に属しているのかを判…
この記事で扱う問題 LeetCodeの392 Is Subsequenceという問題を解きます。 文字列 s と t があるとき、sがtの部分列 (subsequene)かどうかを判定せよ。sとtは英語の小文字のみを含む文字列で、tは長い(50万文字)こともあるが、sは短い文字列(100文字以下)で…
この記事で扱う問題 LeetCodeのCounting Bitsという問題を解きます。問題を適当日本語訳で引用すると、 負でない整数 num が与えられる。 0 例:num = 5 の場合、戻り値は [0,1,1,2,1,2] となる。 https://leetcode.com/problems/counting-bits/ といった感…
今回解いた問題 「加算演算子(+)だけを使用して、減算・乗算・除算を実装せよ」『世界で闘うプログラミング力を鍛える150問 トップIT企業のプログラマになるための本 』を解いている際に見つけた問題を解いてみました。 以前LeetCodeでも似たような問題を解…
最近問題を解いていて n & (n - 1) == 0 というような条件式をたまに見かけます。結論から言うとこれは n が0または2の累乗 (= )かどうかを判定する条件式なのですが、どうしてそうなるのか丁寧に見ていきたいと思います。
C++のstd::mapとstd::unordered_mapの実装の違いを知らなくて恥ずかしい思いをしたので、調べた結果をまとめておきます。 記事のまとめ std::mapは平衡二分探索木、std::unordered_mapはハッシュテーブルで実装されている。 キーの順番を保持したい場合はmap…
順列苦手で解けなかったのでメモ。問題はLeetCodeに掲載されていたものを使用します。LeetCode自体の紹介はこちら。 LeetCode: コーディング面接に向けた練習に使えるサイトの紹介 - 今日も窓辺でプログラム 問題 適当な和訳 整数の配列が入力として与えられ…
LeetCodeに、スタックを使ってキューを実装せよという問題がありました。 Implement Queue using Stacks - LeetCode Articlespushが計算量、popも償却計算量がとなる方法が紹介されていたので、まとめておきます。 償却計算量が何かについては、私の以前の記…
時間計算量というと、平均計算量と最悪計算量についてはよく見聞きしましたが、償却計算量という言葉を知らなかったので、それについてまとめておきます。