今日も窓辺でプログラム

外資系企業勤めのエンジニアが勉強した内容をまとめておくブログ

アルゴリズム

LeetCode 307: Range Sum Query - Mutable をセグメント木で解く

この記事について Union-findに続き、コーディング面接に備える上で大事そうなデータ構造であるセグメント木を勉強したので、セグメント木を使用して解ける問題を解いてみます。 セグメント木とは? セグメント木自体の説明は、また他の方のスライドに丸投げ…

LeetCode 200: Number of Islands をUnion-findを使って解く

この記事について Union-findについて勉強したので、LeetCodeのNumber of Islandsという問題をUnion-findを使用して解いてみます。 Union-findとは? Union-findは素集合データ構造を操作するためのアルゴリズムで、2つの要素が同じ集合に属しているのかを判…

LeetCode 392: Is Subsequence

この記事で扱う問題 LeetCodeの392 Is Subsequenceという問題を解きます。 文字列 s と t があるとき、sがtの部分列 (subsequene)かどうかを判定せよ。sとtは英語の小文字のみを含む文字列で、tは長い(50万文字)こともあるが、sは短い文字列(100文字以下)で…

LeetCode 338: Counting Bits

この記事で扱う問題 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 & (n - 1) == 0 というような条件式をたまに見かけます。結論から言うとこれは n が0または2の累乗 (= )かどうかを判定する条件式なのですが、どうしてそうなるのか丁寧に見ていきたいと思います。

mapとunordered_mapの実装や性能の違い

C++のstd::mapとstd::unordered_mapの実装の違いを知らなくて恥ずかしい思いをしたので、調べた結果をまとめておきます。 記事のまとめ std::mapは平衡二分探索木、std::unordered_mapはハッシュテーブルで実装されている。 キーの順番を保持したい場合はmap…

LeetCode 31: Next Permutation

順列苦手で解けなかったのでメモ。問題はLeetCodeに掲載されていたものを使用します。LeetCode自体の紹介はこちら。 LeetCode: コーディング面接に向けた練習に使えるサイトの紹介 - 今日も窓辺でプログラム 問題 適当な和訳 整数の配列が入力として与えられ…

LeetCode 232: Implement Queue using Stacks

LeetCodeに、スタックを使ってキューを実装せよという問題がありました。 Implement Queue using Stacks - LeetCode Articlespushが計算量、popも償却計算量がとなる方法が紹介されていたので、まとめておきます。 償却計算量が何かについては、私の以前の記…

償却計算量とは何か

時間計算量というと、平均計算量と最悪計算量についてはよく見聞きしましたが、償却計算量という言葉を知らなかったので、それについてまとめておきます。