C++

二分木が与えられたとき、そのノードの値を垂直順序で走査する問題について解説します。同じ行と列に複数のノードがある場合は、左から右の順序で出力します。 問題の例 以下のような二分木を考えます。 この木に対する垂直順序走査の結果は [[9], [3, 15], [20], [7]] となります。 アルゴリズム 水平距離（x座標）をキーとするマップ m を定義する。値はノードの値のリスト。 再帰関数 solve(node, x) を定義し、深さ優先探索でノードをマップに登録する。 ノードが null の場合は終了 左の子を x - 1 で再帰呼び出し

ある単語が与えられたとき、その単語の一般化された略語（generalized abbreviations）をすべて生成する関数を定義することを考えます。 一般化された略語とは、単語の中の任意の連続する文字を、その文字数を表す数字に置き換えたものです。例えば、入力が word の場合、出力は次のようになります。 [word, 1ord, w1rd, wo1d, wor1, 2rd, w2d, wo2, 1o1d, 1or1, w1r1, 1o2, 2r1, 3d, w3, 4] このように、元の単語そのものも含め、各位置の文字を「そのまま残す」か「数字に置き換える」かの組み合わせによって、すべて

本記事では、C++を用いて無向グラフの連結成分（Connected Components）の数を求めるアルゴリズムについて解説します。問題の概要0 から n-1 までのラベルが付いた n 個のノードと、無向エッジのリストが与えられたとき、グラフ内に存在する連結成分の数を返す関数を実装します。例として、入力が次の場合を考えてみましょう。n = 5edges = [[0, 1], [1, 2], [3, 4]]この場合、ノード {0, 1, 2} がひとつのグループを形成し、{3, 4} がもうひとつのグループを形成するため、出力は 2 となります。解決アプローチ：深さ優先探索（DFS）この問題は

整数型の配列 nums と目標値 k が与えられたとき、要素の合計がちょうど k になる「部分配列(連続する要素の並び)」の中で最も長いものの長さを求める問題です。該当する部分配列がひとつも存在しない場合は、代わりに 0 を返します。たとえば、入力が nums = [1, -1, 5, -2, 3]、k = 3 の場合、出力は 4 になります。これは、部分配列 [1, -1, 5, -2] の合計が 3 となり、条件を満たす中で最も長いためです。解法のアプローチこの問題は「累積和(プレフィックスサム)」とハッシュマップを組み合わせることで、O(n) の時間計算量で効率的に解けます。全ての部分配

二分木が与えられたとき、その中に含まれる「最大のBST（二分探索木）サブツリー」を見つけることを考えます。ここで「最大」とは、含まれるノードの数が最も多いサブツリーを指します。 例えば、次のような二分木が入力として与えられた場合を考えてみましょう。 この場合の出力は 3 となります。ハイライトされた部分が、ノード数最大のBSTサブツリーだからです。 解法のアプローチ この問題は、再帰的に各ノードの情報を収集することで効率的に解けます。具体的には、以下の手順に従います。 Data という構造体を定義します。この構造体には4つの値を持たせます。sz（サブツリーのノード数）、maxVal（最大

問題概要 Androidスマートフォンでおなじみの3×3パターンロック画面を考えてみましょう。ここで、2つの整数 m と n(1 ≤ m ≤ n ≤ 9)が与えられます。このとき、m個以上n個以下のキーを使って描けるロック解除パターンの総数を求めるのが本記事の目的です。 パターンのルール 各パターンは、少なくともm個、最大でもn個のキーを結ぶ必要があります。 同じキーを複数回使うことはできません(すべてのキーは一意)。 パターン内で連続する2つのキーを結ぶ直線が別のキーの上を通る場合、その通過されるキーはすでに選択済みでなければなりません。 未選択のキーをまたいで「ジャンプ」することは禁止

研究者の論文の被引用数を表す配列が与えられ、その研究者のH指数（h-index）を計算する関数を定義することを考えます。H指数とは、研究者の論文が持つ影響力を測るための指標で、一般的に次のように定義されます。「研究者の指数が h であるとは、N 本の論文のうち h 本がそれぞれ少なくとも h 回引用されており、残りの N − h 本の論文がそれぞれ h 回以下しか引用されていないことをいう。」具体例たとえば入力が citations = [5, 4, 1, 2, 6] の場合、出力は 3 となります。これは「少なくとも 3 回引用されている論文が 3 本以上存在する」（4回・5回・6回引用の

二分探索木(BST)とあるノードの値が与えられたとき、そのノードの「中順後続ノード(Inorder Successor)」を求めることを考えます。中順後続ノードとは、ノード p の値よりも大きいキーの中で、最小の値を持つノードのことです。 例として、次のような二分探索木を考えてみましょう。 このとき p = 1 とすると、1 より大きい値の中で最小のものは 2 なので、出力は 2 になります。 解法のアプローチ この問題は、二分探索木の性質(左の子 < 親 < 右の子)を利用すると、再帰的に効率よく解けます。手順は以下の通りです。 再帰メソッド inorderSuccesso

はじめに要素が非減少順（昇順）に並んでいる単方向連結リストが与えられたとき、それを高さ平衡な二分探索木（BST）へ変換する問題を考えてみましょう。例えば、リストが [-10, -3, 0, 5, 9] の場合、変換後の木は次のようになります。この問題では、リストの中央の要素を根（ルート）として選び、その左右の部分リストをそれぞれ再帰的に変換することで、自然にバランスの取れた木を構築できます。以下の手順で解いていきましょう。アルゴリズムの手順リストが空の場合は null を返します。リストの先頭ノードを受け取る再帰メソッド sortedListToBST() を定義します。高速ポインタ・低速ポイ

問題概要2次元平面上にn個の点が与えられます。このとき、y軸に平行な直線で全ての点を鏡映（反射）した結果が、元の点集合と完全に一致するような直線が存在するかどうかを判定します。言い換えれば、ある直線を対称軸として全ての点を反転させたとき、反転後の点の集合が元の集合と同一になるかを確認する問題です。例えば、入力が points = [[1,1],[-1,1]] の場合を考えてみましょう。この場合、x = 0 の直線（y軸）を対称軸とすると、点 (1,1) は (-1,1) へ、(-1,1) は (1,1) へと移ります。点集合全体としては変化がないため、出力は true となります。解法のポイン

問題の概要 ソート済みの整数配列 nums と、3つの整数値 a、b、c が与えられます。配列内の各要素 x に対して二次関数 f(x) = ax² + bx + c を適用し、最終的な配列をソート済みの状態で返すことが求められます。 たとえば、入力が nums = [-4, -2, 2, 4]、a = 1、b = 3、c = 5 の場合、出力は [3, 9, 15, 33] となります。 アプローチ：二ポインタ法による O(n) の解法 この問題は、二次関数のグラフ（放物線）の性質を利用すると、追加のソート処理なしに線形時間 O(n) で解くことができます。鍵となるのは次の性質です。 a

問題の概要2次元グリッドが与えられ、各セルは壁「W」、敵「E」、空きマス「0」のいずれかです。この問題では、1つの爆弾で倒せる敵の最大数を求めます。爆弾は設置した地点を起点として、同じ行・同じ列にいるすべての敵を、壁にぶつかるまで倒します。ただし、爆弾を設置できるのは空きマス（0）のみです。例えば、次のようなグリッドが入力として与えられたとします。この場合、出力は 3 となります。緑色のマスに爆弾を設置すると、3体の敵を同時に倒せるためです。解法のアプローチすべてのマスについて毎回行・列の敵を数え直すと非効率です。そこで、行方向と列方向の敵の数を再利用することで計算を効率化します。具体的には、

本記事では、過去5分間（300秒）に受け取ったヒット数を記録・集計するヒットカウンターをC++で設計する方法を解説します。 このシステムでは、秒単位のタイムスタンプを引数として受け取る関数を使用します。呼び出しは必ず時系列順に行われ、タイムスタンプは単調増加すると仮定します。また、最初のタイムスタンプは1から始まるものとします。 なお、複数のヒットがほぼ同じタイミングで到着する可能性がある点にも注意が必要です。 ヒットの記録には hit() 関数を、直近5分間のヒット数の取得には getHits() 関数を使用します。 アルゴリズム（解決手順） 以下の手順で問題を解決します。 サイズ300の

問題の概要 二分木が与えられているとします。まずすべての葉（子ノードを持たないノード）を収集して取り除き、その操作を木が空になるまで繰り返します。 例えば、次のような二分木が入力として与えられた場合を考えてみます。 このとき、出力は [[4,5,3],[2],[1]] となります。最初のラウンドで葉である 4、5、3 が取り除かれ、続いて 2 が、最後に根の 1 が残るという流れです。 解法のアプローチ この問題は、各ノードの「高さ」（最も深い葉から数えた距離）をDFSで求めると効率的に解けます。同じ高さを持つノードは、必ず同じラウンドで葉になるためです。具体的な手順は以下の通りです。

問題の概要負でない整数が、各桁の数字を要素とする空でない単方向連結リストとして表現されているとします。ここでの課題は、その整数に1を加算することです。整数には余計な先行ゼロが含まれていない(数値0そのものを除く)ものとみなせるものとし、連結リストでは最上位の桁が先頭ノード(head)に格納されています。例えば、入力が [1,2,3] の場合、出力は [1,2,4] になります。解法のアプローチこの問題を解くために、以下の手順に従います。head が NULL の場合は、head をそのまま返します。curr = head、req = NULL として初期化します。curr が NULL になる

問題概要 サイズnの整数配列が与えられ、すべての要素が0で初期化されているとします。さらに値kが与えられ、k回の更新操作を行います。各操作は [startIndex, endIndex, inc] という3つ組で表され、部分配列 A[startIndex ... endIndex]（startIndexとendIndexを含む）の各要素に inc を加算します。k回の操作をすべて実行した後の、変更後の配列を求めるのがこの問題です。 例えば、入力が length = 5、updates = [[1,3,2],[2,4,3],[0,2,-2]] の場合、出力は [-2, 0, 3, 5, 3]

本記事では、次の3つの操作をサポートする電話帳（Phone Directory）クラスをC++で設計する方法を解説します。 get ― まだ誰にも割り当てられていない番号を1つ取得する check ― 指定した番号が利用可能かどうかを確認する release ― 使用済みの番号を解放し、再利用できる状態に戻す コンストラクタでは、あらかじめ最大 n 個の番号を初期化しておきます。 解法のアプローチ この問題は、「使用中の番号を記録するセット」と「利用可能な番号を保持するキュー」という2つのデータ構造を組み合わせることで、効率的に解くことができます。キューによって番号を取得する順序が保証

この記事では、与えられた部分シーケンスの集合 seqs から、元のシーケンス org を一意に再構築できるかどうかを判定する問題をC++で解く方法を解説します。問題の概要元のシーケンス org は、1からnまでの整数の順列です。ここで n の範囲は 1 ≤ n ≤ 10^4 とします。「再構築」とは、seqs 内のシーケンスすべての最短共通超列（shortest common supersequence）を作ることを意味します。つまり、seqs から再構築できるシーケンスがただ1つであり、それが元のシーケンス org と一致するかどうかを確認する必要があります。入力例例えば、入力が org =

問題概要D と I の2種類の文字だけで構成された「秘密の署名」を考えます。D は隣接する2つの数の間の減少関係を、I は増加関係を表します。この署名は、1 から n までの相異なる整数をすべて含む特別な整数配列から構成されます。たとえば、署名 DI は [2, 1, 3] や [3, 1, 2] のような配列から構成できます。一方、[3, 2, 4] や [2, 1, 3, 4] のような配列では構成できず、不正な構成となります。ここでの課題は、入力として与えられた署名に一致する [1, 2, ..., n] の順列のうち、辞書順で最小のものを見つけることです。入力が DI の場合、出力は

0と1のみから構成されるバイナリ配列が与えられたとき、「0を最大1回だけ反転できる」という条件下で、配列内に存在する連続した1の最大個数を求める問題について解説します。 例えば、入力が [1,0,1,1,0] の場合、出力は 4 となります。最初に出現する0を反転すれば [1,1,1,1,0] となり、先頭から4つ連続した1が得られるためです。 解法の考え方:スライディングウィンドウ この問題は、スライディングウィンドウ(尺取り法)を用いることで、線形時間で効率的に解くことができます。ウィンドウ内に含まれる0の個数が「1個以内」に収まるように、右端を伸ばしながら左端を調整していくのがポイントで