今日も窓辺でプログラム

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

LeetCode

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/ といった感…

n & (n - 1) == 0 の意味とは?

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

LeetCode: コーディング面接に向けた練習に使えるサイトの紹介

この記事について LeetCode Online Judge というアルゴリズムやデータ構造に関する問題を解いて、オンラインジャッジまでできるサイトがあるので、どのようなサイトかを簡単に紹介します。

LeetCode 31: Next Permutation

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

LeetCode 232: Implement Queue using Stacks

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