C++

はじめにC++のsetとunordered_setは、どちらもデータを効率的に格納・検索・挿入するための連想コンテナ(データ構造)です。しかし、内部実装やデータの保持方法に大きな違いがあり、用途に応じた使い分けが重要になります。本記事では、setとunordered_setの主な違いを比較表で整理し、実際のコード例を通じてそれぞれの動作の違いを確認します。setとunordered_setの主な違い項目setunordered_set定義キーと値のペアでデータを格納する連想コンテナの一種。要素の値そのものがキーとして機能するため、すべての要素は一意である必要があります。C++ STL(標準テン

ソート済み配列 arr とターゲット値が与えられたとき、ターゲットが配列内に存在する場合はそのインデックスを返します。存在しない場合は、順序を保ったまま挿入したと仮定した場合の挿入位置（インデックス）を返します。例えば、入力が [1,3,4,6,6]、ターゲットが 5 の場合、出力は 3 になります。インデックス 3 に 5 を挿入すると、配列は [1,3,4,5,6,6] となるためです。解法のアプローチ（二分探索）この問題は、二分探索（バイナリサーチ）を使うことで O(log n) の計算量で効率的に解くことができます。手順は以下の通りです。n := A のサイズとするn < 1 の

問題概要文字列 s が与えられます。s には英字と空白が含まれます。このとき、文字列に含まれる最後の単語の長さを求める必要があります。最後の単語が存在しない場合は 0 を返します。たとえば、入力が「I love Programming」の場合、最後の単語は「Programming」なので、出力は 11 となります。解法のアプローチこの問題は、stringstream を使って文字列を単語ごとに分割し、最後に読み取った単語の長さを記録することで解けます。手順は以下の通りです。変数 n を 0 で初期化します。stringstream を使って文字列から単語を順番に読み込みます。各単語 temp

ソート済みの連結リスト（リンクリスト）が与えられたとき、各要素が1回だけ出現するように、すべての重複を取り除くことを考えます。たとえば、入力が [1,1,2,3,3,3,4,5,5] の場合、出力は [1,2,3,4,5] となります。リストがすでにソートされているため、同じ値を持つノードは必ず隣接しており、隣接するノード同士を比較するだけで重複を検出できるのがポイントです。アルゴリズムの流れこの問題は、ダミーノードを使ったシンプルな走査で解決できます。手順は以下の通りです。値が -inf（INT_MIN）の新しいノード「dummy」を作成しますdummy の next を head（元のリス

2つの二分木が与えられたとき、それらが「同じ」であるかどうかを判定する関数を定義することを考えます。二分木が同じとみなされるのは、構造が完全に一致し、かつすべての対応するノードの値が等しい場合です。例えば、入力が [1,2,3] と [1,2,3] の場合、両木は構造も値も一致しているため、出力は True になります。解法のアプローチこの問題は再帰を用いることで簡潔に解くことができます。以下の手順に従います。isSameTree という関数を定義します。この関数は2つの木のノード p と q を引数として受け取ります。p と q がどちらも NULL の場合は、両木ともそこにノードが存在しな

二分木が与えられたとき、その木の最小深度（minimum depth）を求めることを考えます。最小深度とは、根ノードから最も近い葉ノードまでの最短経路に含まれるノード数のことです。 例えば、次のような二分木が入力として与えられた場合を考えてみましょう。 この場合、出力は 2 になります。これは、根ノード 3 から葉ノード 9 までの経路が最短だからです。 解決のためのアプローチ この問題は、幅優先探索（BFS）を用いて各レベルを順番に調べることで効率的に解決できます。手順は以下の通りです。 ツリーノードを格納する配列 aa を定義し、その末尾に root を挿入します 別の配列 ak を

パスカルの三角形 II とは0 以上のインデックス k（k ≤ 33）が与えられたとき、パスカルの三角形の k 行目を求める問題を考えてみましょう。例えば、入力が 3 の場合、出力は [1, 3, 3, 1] となります。パスカルの三角形とは、各行の両端が 1 であり、それ以外の要素が直上の行の左右隣接する2つの値の和になるという性質を持つ三角形です。この問題では、空間計算量 O(k) だけを使って、指定された行のみを効率的に生成することが求められます。解法のアプローチこの問題は「1次元配列をその場で更新する（in-place更新）」テクニックを使うことで、追加の配列を用意せずに解くことができ

問題の概要正の整数が与えられたとき、その数に対応するExcelシート上の列タイトル（列名）を求めることを考えます。対応関係は次のとおりです。[1 : A]、[2 : B]、[26 : Z]、[27 : AA]、[28 : AB] …たとえば、入力が28であれば、出力は「AB」となります。解法のアプローチこの問題は一見すると単純な26進法への変換のように思えますが、Excelの列名には「0」に相当する文字が存在しない点が重要なポイントです。つまり、これは通常の26進法ではなく、1〜26を1桁として扱う特殊な記数法（バイジェクティブ26進法）になっています。そこで、各桁を求める前に必ずnから1を引

同型文字列とは？2つの文字列 s と t が与えられたとき、両者が「同型（isomorphic）」であるかどうかを判定する問題を考えてみましょう。同型文字列とは、s の文字を適切に置き換えることで t が得られるような文字列のペアのことです。ただし、置き換えには以下のルールがあります。ある文字が出現する箇所は、すべて同じ文字に置き換えなければなりません文字の出現順序は保持される必要があります2つの異なる文字が同じ文字へマップされることは許されませんただし、1つの文字が自分自身にマップされることは可能です例えば、s = egg、t = add という入力の場合、e → a、g → d という一対

問題概要 配列と整数 k が与えられます。このとき、配列の中に異なる 2 つのインデックス i と j が存在し、nums[i] = nums[j] かつ i と j の絶対差が k 以下となるかどうかを判定するのが本問題です。 たとえば、入力が [1,2,4,1]、k = 3 の場合を考えてみましょう。インデックス 0 と 3 の要素はどちらも 1 であり、そのインデックスの差は 3 なので、出力は True になります。 解法のアプローチ この問題は、次の手順に従って解くことができます。 (値, インデックス) のペアを格納する配列 nn を定義します。 i を 0 から nums の

キューでスタックを実装するとはキューを使ってスタックを実装することを考えてみましょう。そのためには、スタックに対して以下のメソッドを定義する必要があります。push(x) – 要素xをスタックにプッシュします。pop() – スタックの先頭（トップ）要素を削除し、その値を返します。top() – スタックの先頭要素を参照して返します。empty() – スタックが空かどうかを判定して返します。例えば、push(10)とpush(20)を順に呼び出した後、pop()を2回呼び出すと、出力は「20」「10」の順になります。これはスタックのLIFO（Last In First Out：後入れ先出し）

問題概要パターン pattern と文字列 str が与えられたとき、str がそのパターンに従っているかどうかを判定します。ここで「従う」とは、パターン中の各文字と、文字列中の空でない各単語との間に全単射（一対一対応）が成り立つことを意味します。たとえば、pattern = cbbc、str = word pattern pattern word の場合、文字 c が単語 word に、文字 b が単語 pattern に対応しているため、結果は True となります。解き方の考え方この問題は、パターン側と単語側をそれぞれ「数値の並び」に正規化して比較するのが有効です。具体的な手順は以下の通

ニムゲームとはニムゲームは、2人のプレイヤーが交互に石を取り合う古典的なゲームです。山になっている石から、各ターンで1個から3個の石を取り除くことができ、最後の石を取ったプレイヤーが勝者となります。ここでは、プレイヤー1が先手として最初に石を取るものとします。また、両プレイヤーとも非常に賢く、常に最適な戦略を取ると仮定します。与えられた石の総数をもとに、プレイヤー1が勝利できるかどうかを判定するアルゴリズムを考案しましょう。例えば、入力が5の場合、出力はtrue（真）になります。石が5個あるとき、プレイヤー1が最初に1個取れば4個残ります。次にプレイヤー2が何個取ろうと（1〜3個）、その後に必

問題概要 整数が与えられたとき、その数が4の累乗であるかどうかを判定する問題です。 例えば、入力が16であれば、出力はTrueになります。 解決アプローチ この問題は、ビット演算を活用することで効率的に解くことができます。以下の手順に従って判定を行います。 num < 0 の場合 → false を返す num & (num - 1) の結果が 0 以外の場合 → false を返す num & 0x55555555(バイナリ表記で 0101...0101)の結果が 0 の場合 → false を返す 上記のチェックすべてを通過した場合 → true を返す アル

プログラミングでは、2つの配列が与えられたときに、両方に共通して含まれる要素（共通部分・積集合）を求めたい場面がよくあります。 例えば、入力が [1,5,3,6,9] と [2,8,9,6,7] の場合、両方の配列に存在する要素は 9 と 6 なので、出力は [9, 6] になります。 解決のアプローチ この問題は、ハッシュマップ（unordered_map）を使って各配列の要素の出現回数を記録することで、効率的に解くことができます。手順は以下の通りです。 2つのマップ mp1、mp2 を定義します 結果を格納するための配列 res を定義します nums1 の各要素 x について、mp1

問題概要ここでは、いわゆる「数当てゲーム(Guess Game)」を考えます。このゲームのルールは以下のとおりです。プレイヤー1が1からnまでの範囲からある1つの数を選びます。プレイヤー2は、その数が何であるかを推測しなければなりません。プレイヤー2の推測が外れるたびに、プレイヤー1は「選んだ数はもっと大きい」か「もっと小さい」かを教えてくれます。この問題では、guess(num)という関数を利用できます。この関数は次の3つの値のいずれかを返します。-1:プレイヤー1が選んだ数は、numよりも小さい1:プレイヤー1が選んだ数は、numよりも大きい0:推測が的中した(数が一致した)たとえば、入力

問題の概要小文字の英字のみで構成された2つの文字列 s と t が与えられます。文字列 t は、s をランダムにシャッフルした後、ランダムな位置にさらに1文字を追加して生成されたものです。このとき、t に追加されたその1文字を見つけることが課題となります。例えば、入力が mnopq と pqmnot の場合、出力は t になります。これが追加された余分な文字です。解法のアプローチ：文字コードの合計値を利用するこの問題を効率的に解くには、各文字のASCIIコード（文字コード）の合計値を利用する方法が有効です。考え方は以下の通りです。変数 sSum と tSum を0で初期化します。文字列 s の

整数が与えられたとき、それを16進数の文字列に変換するアルゴリズムを設計します。負の数を扱う場合は、2の補数（twos complement）の方式を用いて処理します。 例えば、入力が 254 と -12 であれば、出力はそれぞれ「fe」と「fffffff4」になります。 解法のアルゴリズム この問題は、以下の手順に従って解くことができます。 num1 が 0 と等しい場合は、「0」を返します。 num := num1 とします。 s := 空の文字列 とします。 num が 0 でない間、次の処理を繰り返します。 temp := num mod 16（num を 16 で割った余り）と

本記事では、C++を使って「与えられた文字列の文字から構築できる最長回文の長さ」を求めるアルゴリズムを解説します。問題の概要小文字・大文字の英字のみで構成された文字列が与えられたとき、それらの文字を自由に並べ替えて作れる最長の回文の長さを求めます。なお、この問題では大文字と小文字は区別されるため、「Aa」のような組み合わせは回文とはみなされません。例えば、入力が abccccdd の場合、出力は 7 になります。これは、dccaccd のような長さ7の回文を構築できるためです。解法のアプローチ回文の性質に着目すると、以下のように考えることができます。偶数個出現する文字は、すべて左右対称に配置で

空でない整数配列が与えられたとき、その中の3番目に大きい数（第3最大値）を求める問題を考えます。第3最大値が存在しない場合は、代わりに最大値を返します。ここでのポイントは、線形時間 O(n) で解く必要があるという点です。 例えば、入力が [5,3,8,9,1,4,6,2] の場合、出力は 6 となります。 解法のアプローチ この問題は、上位3つの値を常に追跡する変数を用意すれば、配列を一度走査するだけで解けます。手順は以下の通りです。 3つのポインタ変数 a、b、c を NULL で初期化します。それぞれ最大値・2番目・3番目に大きい値へのポインタとして機能します。 i := 0 から配