C++

単語のリストと、word1・word2 という2つの単語が与えられたとき、リスト内におけるこれら2つの単語間の最短距離を求めるのが本問題です。注意点として、word1 と word2 が同じ単語であるケースも存在します。例として、words = [practice, makes, perfect, skill, makes] というリストを考えてみましょう。このとき、入力が word1 = makes、word2 = skill であれば、出力は 1 となります。解法のアプローチこの問題は、リストを先頭から一度走査しながら、各単語の最新の出現位置を記録していくことで、線形時間で効率よく解くこと

問題の概要 長さ n が与えられたとき、その長さをもつすべての回転対称数（ストロボグラマティック数）を求めることを考えます。 回転対称数とは、180度回転させても見た目が変わらない数のことです。回転しても有効な数字と対応する組み合わせは、次の5種類だけです。 0 ↔ 0 1 ↔ 1 8 ↔ 8 6 ↔ 9 9 ↔ 6 奇数桁の数では、中央に置けるのは回転しても自分自身である 0・1・8 の3種類に限られます。 たとえば入力が n = 2 の場合、出力は [11, 69, 88, 96] となります。「69」は180度回転しても「69」に見えるため、条件を満たしています。 解法のアプローチ：

問題の概要 ある文字列に対して、各文字をその次の文字へ「シフト」する操作を考えます。たとえば「abc」は「bcd」に変換でき、この操作を繰り返すことで「abc」→「bcd」→ … →「xyz」という一連のシフト系列が形成されます。ここで、小文字の英字のみから構成される空でない文字列のリストが与えられたとき、同じシフト系列に属する文字列どうしをすべてグループにまとめることが求められます。 たとえば、入力が [abc, bcd, acef, xyz, az, ba, a, z] の場合、出力は [[abc,bcd,xyz], [az,ba], [acef], [a,z]] となります。「abc」「

問題の概要 二分木が与えられたとき、その中に含まれる「ユニバリュー（単一値）部分木」の数を数えることを考えます。ここでいうユニバリュー部分木とは、その部分木を構成するすべてのノードが同じ値を持つような部分木のことです。 例えば、入力が root = [5,1,5,5,5,null,5] の場合を考えてみましょう。 このとき出力は 4 になります。これは、値 5 を持つ葉ノードが2つ、右側の値 5 を根とする部分木（親子ともに 5）が1つ、さらにその先の葉ノードが1つ存在し、合計 4 つのユニバリュー部分木が見つかるためです。 解法のアプローチ この問題は、木を再帰的にたどりながら「そのノー

2次元ベクトル（vector of vectors）が与えられたとき、それを平坦化して1つずつ要素を取り出せるようにするイテレータを設計・実装することを考えます。このイテレータには、主に次の2つのメソッドを実装します。next() — 現在位置の次の要素を返します。hasNext() — 次の要素がまだ存在するかどうかを判定します。動作例たとえば、入力が [[1,2],[3],[4]] の場合、メソッドを次の順序で呼び出すとします。iterator.next(); iterator.next(); iterator.next(); iterator.hasNext(); iterator.ha

問題概要 会議の開始時刻と終了時刻のペアからなる区間の配列 [[s1,e1],[s2,e2],...] が与えられます。各区間は (si < ei) を満たすものとします。このとき、すべての会議を開催するために最低限必要な会議室の数を求めるのがこの問題です。 たとえば、入力が [[0, 30], [5, 10], [15, 20]] の場合、出力は 2 になります。[0, 30] の会議が進行している間に [5, 10] と [15, 20] の会議が行われるため、もう 1 つの会議室が必要になるからです。 解法のアプローチ この問題は優先度付きキュー（priority queue）を

ある整数が与えられたとき、その数は複数の因数（因子）の積として表すことができます。例えば、8 = 2 × 2 × 2 = 2 × 4 のように表せます。本記事では、整数 n を受け取り、その因数のすべての組み合わせを返す関数を C++ で実装する方法を解説します。例えば、入力が 12 の場合、出力は [[2, 6], [2, 2, 3], [3, 4]] となります。なお、n 自身だけを要素とする組み合わせ（例：[12]）は結果に含めないのが一般的です。アルゴリズムの考え方この問題は再帰（バックトラッキング）を使うことで効率的に解けます。手順は以下の通りです。solve() 関数を定義します。

数値のシーケンスが与えられたとき、それがある二分探索木（BST）の正しい先行順走査（プレオーダートラバーサル）の結果であるかどうかを判定する問題を考えてみましょう。ここでは、シーケンス内の各数値はすべて一意であるものと仮定します。 例として、次のような二分探索木を想定します。 この木の場合、入力が [5,2,1,3,6] であれば、出力は true になります。 解法のアプローチ この問題は、スタックによるシミュレーションを用いることで効率的に解くことができます。手順は以下の通りです。 itr := -1（スタックのトップ位置を表すインデックス） low := -∞（これまでに確定した下

問題概要n個の整数からなる配列 nums とターゲット値 target が与えられたとき、インデックスの三つ組 (i, j, k) のうち、i, j, k がすべて 0 以上 n − 1 以下の範囲にあり、かつ nums[i] + nums[j] + nums[k] < target を満たすものの個数を求めます。例えば、入力が nums = [-2, 0, 1, 3]、target = 2 の場合、出力は 2 になります。これは、和が 2 未満となる三つ組が [-2, 0, 1]（和は -1）と [-2, 0, 3]（和は 1）の 2 つ存在するためです。解法のアプローチこの問題は、配

n個のノードが0からn-1までのラベルで与えられ、無向辺のリスト [u, v] があるとします。これらの辺が有効な木（ツリー）を構成しているかどうかを判定する関数を定義する必要があります。 例えば、入力が n = 5、edges = [[0,1], [0,2], [0,3], [1,4]] の場合、出力は true になります。 解決のためのアプローチ この問題は、深さ優先探索（DFS）を用いて解くことができます。グラフが木であるためには、次の2つの条件を満たす必要があります。 閉路（サイクル）が存在しないこと すべてのノードが連結していること DFSの実行中に各ノードの状態を visi

文字列 s が与えられたとき、その文字を並べ替えて作ることができる「回文（パリンドローム）」となる順列をすべて求める問題です。結果に重複は含めず、回文順列がひとつも存在しない場合は空の結果を返します。 たとえば、入力が aabb の場合、出力は [abba, baab] となります。 解法のアプローチ この問題はバックトラッキング（試行と巻き戻し）を使うことで効率的に解けます。まず各文字の出現回数を数え、奇数回現れる文字が2種類以上ある場合は回文を構成できないため、その時点で空の結果を返します。回文にできる場合は、左右対称の位置へ同じ文字をペアで配置しながら再帰的に文字列を組み立てていきます

文字列のリストが与えられたとき、そのリスト全体を1つの文字列にエンコードするアルゴリズムを設計し、さらにエンコードされた文字列を元のリストへ復元（デコード）する仕組みを実装することを考えます。エンコーダーとデコーダーはそれぞれ別のマシンに配置されており、以下のような2つの関数として構成されます。 マシン1（送信側）が持つ関数 string encode(vector<string> strs) { // 文字列を読み込み、encoded_string を返す } マシン2（受信側）が持つ関数 vector<string> decode(string s)

n人の人（0からn-1までのラベル付き）がいて、その中に「有名人」が1人存在する可能性があるとします。人xが有名人であるとは、他のn-1人全員がxを知っている一方で、xは彼らの誰一人として知らないことを指します。この課題では、有名人が誰であるかを見つけるか、あるいは有名人が存在しないことを確認します。 情報を得るために許されているのは、人Aに対して「Aさん、Bさんのことを知っていますか？」と質問することだけです。有名人を特定するには、質問の回数を最小限に抑える必要があります。入力はgraphというリストのリストで与えられ、i番目の人がj番目の人を知っている場合はgraph[i][j] = 1

問題概要 ソートされていない整数型の配列 nums が与えられます。この配列をインプレース（追加メモリを使用せず）で並べ替え、次の条件を満たすようにします。 nums[0] <= nums[1] >= nums[2] <= nums[3] ... つまり、隣り合う要素の大小関係が「小さい・大きい・小さい…」と交互に波打つように（wiggle＝揺らぐように）配置するのが目標です。 例として、入力が nums = [3,5,2,1,6,4] の場合、出力は [3,5,1,6,2,4] のようになります。なお、条件を満たす答えは複数存在する可能性があります。 解法のアプローチ こ

ジグザグイテレータとは？2つの1次元配列が与えられたとき、それぞれの要素を交互に順番に返すイテレータを実装することを考えます。このイテレータには、次の2つのメソッドが必要です。next() — 次の要素を取得します。hasNext() — 次の要素がまだ存在するかどうかを判定します。例えば、入力が v1 = [1,2]、v2 = [3,4,5,6] の場合、出力は [1,3,2,4,5,6] となります。つまり、v1 と v2 から交互に1つずつ要素を取り出し、片方が尽きた後は残りの配列の要素をそのまま返していきます。解法のアプローチ：キューを使った実装この問題は、キュー（queue）とペア（

問題の概要二分探索木（BST）と、その木に含まれるあるノードが与えられたとき、そのノードの「中間順後継（In-order Successor）」を探索する問題を考えてみましょう。ここでいうノード p の後継とは、「p.val よりも大きいキーの中で最小の値を持つノード」のことを指します。例入力が root = [2,1,3]、p = 1 の場合を考えてみます。この場合、出力は 2 となります。値1の次に大きい値は2だからです。解法のアプローチこの問題は、BSTの性質を利用した再帰的なアプローチで効率よく解くことができます。手順は以下の通りです。再帰メソッド inorderSuccessor()

問題概要m × n の2次元グリッドを考えます。このグリッドは、以下の3種類の値で初期化されています。-1：壁または障害物0：ゲート（門）INF：空き部屋（無限大を表す）ここでは、INF として 2^31 − 1 = 2147483647 を使用します。ゲートまでの距離は必ず 2147483647 未満になると仮定できるためです。求めたいのは、各空き部屋に対して、最も近いゲートまでの距離です。もしゲートへ到達できない部屋があれば、その部屋は INF のままにします。入力例INF-10INFINFINFINF-1INF-1INF-10-1INFINF出力例3-101221-11-12-10-13

問題概要フリップゲームは、2人のプレイヤーが対戦するゲームです。「+」と「-」の2種類の文字のみからなる文字列が与えられ、プレイヤー1とプレイヤー2が交互に、連続する2文字の「++」を「--」へと反転していきます。自分の番に打てる手がなくなったプレイヤーが負けとなり、相手が勝者となります。この記事では、先手のプレイヤーが必ず勝利できるかどうかを判定する関数を定義します。例えば、入力が s = ++++ の場合、出力は true（1）になります。先手のプレイヤーは中央の「++」を反転して「+--+」という局面を作れば、その後どちらに相手が打っても必ず勝てるからです。解法アプローチこの問題はメモ化

問題の概要二分木が与えられたとき、最長の連続シーケンス経路の長さを求める問題を考えます。ここで「経路」とは、ある開始ノードから親子のつながり(親から子へのエッジ)に沿って、木の中の任意のノードまでをたどるノードの列を指します。最長の連続経路は必ず親から子の方向へ進む必要があり、逆方向(子から親)へさかのぼることは認められません。たとえば、次のような二分木が入力として与えられた場合を考えてみましょう。この場合、最長の連続シーケンス経路は 3 → 4 → 5 となるため、出力は 3 になります。アルゴリズムのアプローチこの問題は、木を深さ優先探索(DFS)でたどりながら、連続する値の並びを追跡する

2つの行列 A と B が与えられたとき、その積 AB を求めることを考えます。ここで、A の列数と B の行数は等しいものと仮定します。 例として、入力が [[1,0,0],[-1,0,3]] と [[7,0,0],[0,0,0],[0,0,1]] の場合を見てみましょう。 100-103 700000001 この場合、出力は [[7,0,0],[-7,0,3]] となります。 700-703 スパース行列の乗算を効率化するポイント 通常の行列積では O(r1 × c1 × c2) の計算量が必要ですが、スパース行列(大部分の要素が 0 である行列)の場合、0 を含む掛け算は結果に寄与しな