C++

問題概要 ソートされていない整数配列 nums が与えられます。これを並べ替えて、nums[0] < nums[1] > nums[2] < nums[3] のように、隣接する要素の大小関係が交互に入れ替わる「揺らぎ（wiggle）」構造を作ります。例えば、入力が [1,5,1,1,6,4] の場合、出力は [1,6,1,5,1,4] のようになります。なお、条件を満たす答えは複数存在する場合があります。 アルゴリズムのアプローチ この問題は、ソート済み配列を「小さい半分」と「大きい半分」に分け、それぞれを逆順で偶数番目・奇数番目のインデックスへ配置することで効率的に解けま

問題概要2次元のボードが与えられ、その中に何隻の戦艦（バトルシップ）が存在するかを数えることを考えます。戦艦は記号「X」で表され、空きマスは「.」で表されます。この問題では以下のルールが保証されています。与えられるボードは有効であり、戦艦または空きマスのみで構成されています。戦艦は水平方向または垂直方向にのみ配置されます。つまり、戦艦の形状は必ず 1xN（1行N列）または Nx1（N行1列）のいずれかであり、Nは任意のサイズを取れます。2つの戦艦の間には、少なくとも1つの水平方向または垂直方向の空きマスが存在します。つまり、戦艦同士が隣接することはありません。例として、以下のようなボードが与え

N分木（N-ary Tree）が与えられたとき、そのノードの値をレベル順走査（Level Order Traversal）、つまり上の階層から順に同じ深さごとにまとめて取得することを考えます。N分木の入力データはレベル順走査の形式でシリアライズされており、各子ノードのグループは null 値で区切られて表現されます。例えば、下図のようなツリーは [1,null,3,2,4,null,5,6] と表されます。この場合、期待される出力は [[1],[3,2,4],[5,6]] となり、第1レベルにはルートの「1」、第2レベルには「3, 2, 4」、第3レベルには「5, 6」が含まれます。解法のアプ

問題概要複数の区間（インターバル）のコレクションが与えられたとき、残りの区間同士が互いに重なり合わないようにするために、削除が必要な区間の最小数を求める問題です。例えば、区間が [[1,2], [2,3], [3,4], [1,3]] であった場合、他のすべての区間が重複しない状態にするには [1,3] を削除すればよいため、出力は 1 となります。解決のためのアプローチこの問題は貪欲法（グリーディ法）を使うことで効率的に解くことができます。手順は以下の通りです。n := 配列のサイズとしますn が 0 の場合は 0 を返しますcount := 1 で初期化します区間の終了時刻に基づいて配列を

二分探索木（BST：Binary Search Tree）が与えられます。ここで1つのキー k を受け取り、そのキー k をBSTから削除して、更新されたBSTを返すことを考えます。 例えば、次のような木があるとします。 そして、削除するキーが k = 3 の場合、出力される木は次のようになります。 アルゴリズムの考え方 この問題を解くために、まず「ルートノードを削除する」処理を担当する補助メソッド deleteRoot() を定義します。このメソッドは以下のように動作します。 root が null の場合は、null を返します。 root に右部分木が存在しない場合は、roo

問題概要二次元空間上に複数の球形の風船が浮かんでいるとします。各風船については、その水平方向の直径の始点座標と終点座標が与えられ、始点は必ず終点より小さくなっています。風船の数は最大 104 個です。矢は x 軸上の任意の位置から真上へ垂直に射出できます。位置 xstart から xend にある風船は、xstart ≤ x ≤ xend を満たす位置 x から射出された矢によって破裂します。射出できる矢の本数に制限はなく、一度射出された矢は無限に上方へ飛び続けるものとします。このとき、すべての風船を破裂させるために必要な矢の最小本数を求めるのがこの問題です。具体例入力が [[10,16],[

正と負の整数値から構成される循環配列 nums を想定します。あるインデックスに格納された数値 k が正の数であれば、前方向に k ステップ移動し、負の数(−k)であれば、後ろ方向に k ステップ移動します。配列は循環しているため、最後の要素の「次」は最初の要素となり、最初の要素の「前」は最後の要素となります。このとき、配列 nums の中にループ(閉路)が存在するかどうかを判定するのが本問題です。 有効な閉路は、同一のインデックスで開始・終了し、長さが 1 より大きいものでなければなりません。たとえば入力が [2,-1,1,2,2] の場合、インデックス 0 → 2 → 3 → 0 という長

木のルートが与えられたとき、最も頻繁に出現する「部分木の合計」を求める問題を考えてみましょう。あるノードにおける部分木の合計とは、そのノードを根とする部分木に含まれるすべてのノード値（そのノード自身を含む）の総和のことです。最頻出の部分木の合計が複数あり同率となった場合は、どのような順序でもよいので、最大頻度を持つすべての値を返します。たとえば、木が [5,2,-5] で構成されている場合、答えは [2] となります。これは、葉ノード 2 の合計値と、根 5 の部分木全体の合計値（5 + 2 + (-5) = 2）が一致して 2 が 2 回出現する一方、-5 は 1 回しか出現しないためです。

二分木が与えられたとき、その木の最も深い行（最下層）における左端の値を求める問題を考えてみましょう。例えば、次のような二分木があるとします。 この場合、最下層は [7, 4] であり、その中で最も左にある要素は 7 なので、出力は 7 となります。 解法のアプローチ この問題は、深さ優先探索（DFS）を利用することでシンプルに解くことができます。ポイントは「必ず左側の子ノードから先に訪問する」ことです。こうすることで、それまでに到達した中で最も深いレベルへ最初に到達したノードが、自動的にそのレベルの左端のノードになります。 アルゴリズムの手順 最初に、答えを格納する ans と、現在の最大

二分木が与えられたとき、その木の各階層(レベル)ごとの最大値を求めることを考えます。例えば、次のような二分木があるとします。この場合、出力は [1, 3, 9] となります。ルート(最上位)の階層には「1」だけが存在するため、最大値は 1第1階層には「3」と「2」があり、最大値は 3第2階層には「5」「3」「9」があり、最大値は 9解決のためのアプローチこの問題は、再帰的な深さ優先探索(DFS) を使うことで簡潔に解くことができます。手順は以下の通りです。結果を格納するための配列 ans を定義します。再帰関数 solve() を定義します。この関数はツリーノードとレベル(初期値は 0)を引数

最大二分木（Maximum Binary Tree）とは？ ここでは、すべての要素が一意（重複なし）である整数配列が与えられたとします。この配列から構築される「最大二分木」は、以下のように定義されます。 根（ルート）には、配列内の最大値が格納されます。 左部分木は、最大値を基準に分割された左側の部分配列から構築された最大二分木です。 右部分木は、最大値を基準に分割された右側の部分配列から構築された最大二分木です。 この定義に従って最大二分木を構築します。たとえば、入力が [3,2,1,6,0,5] の場合、構築される木は次の図のようになります。 解き方のアプローチ この問題は、再帰的な

二分木が与えられたとき、その木の最大幅を求める関数を定義することを考えます。ここでいう木の幅とは、すべてのレベル（階層）の中で最も広いレベルの幅のことを指します。 二分木は完全二分木と同じ構造を持つものとみなしますが、一部のノードはnull（存在しない）である場合があります。あるレベルの幅とは、そのレベルにおける両端ノード（最左端と最右端の非nullノード）間の長さのことであり、両端ノードの間に存在するnullノードも長さの計算に含まれる点に注意が必要です。 例えば、次のような木を考えてみましょう。 この場合、最下層のノード構成は [5, 3, null, 9] となるため、最大幅は4になり

問題概要二分木のルートノード root が与えられ、すべてのノードの値は 0 または 1 のいずれかであるとします。この木から、1 を含まないすべての部分木を削除した結果の木を求めるのが目的です。たとえば、次のような木が与えられた場合 −解決のためのアプローチこの問題は、再帰的な手法を用いて以下の手順で解決できます −ノードを引数として受け取る再帰メソッド solve() を定義します。処理の流れは次のとおりです −ノードが null の場合は、null を返しますノードの左の子に対して solve(左の子) を実行し、その結果を左の子に代入しますノードの右の子に対して solve(右の子)

問題概要 整数からなる循環配列 C(固定バッファ A で表現)が与えられます。このとき、C の空でない部分配列の合計として考えられる最大値を求めてください。ただし、部分配列に含められるのはバッファ A の各要素につき最大1回までです。例えば、配列が [1, -2, 3, -2] の場合、出力は 3 になります。これは部分配列 [3] の合計が 3 であり、これが最大であるためです。 解法のアプローチ この問題を解くために、以下の手順に従います。 n := v のサイズとする サイズ n の配列 leftSum、leftSumMax、rightSum、rightSumMax を作成する l

ここでは、2つの整数列 pushed と popped（すべての値は重複なし）が与えられたとき、popped が「初期状態で空のスタック」に対する一連の push・pop 操作の結果として実現可能かどうかを判定する問題を扱います。 例として、pushed = [1,2,3,4,5]、popped = [4,5,3,2,1] の場合、答えは true になります。実際、次のような操作列で再現できます。 push(1), push(2), push(3), push(4) pop() → 4 を取り出し push(5) pop() → 5、pop() → 3、pop() → 2、pop() →

問題の概要 2つの二分木が与えられ、一方の木をもう一方の木へ変換できるかどうかを判定する問題を考えてみましょう。 ここでいうフリップ（反転）操作とは、任意のノードを1つ選び、そのノードの左側の子部分木と右側の子部分木を入れ替えることです。二分木 X にフリップ操作を何度か適用して二分木 Y と同じ形にできるとき、X と Y はフリップ等価であると言います。 本記事では、ルートノード root1 と root2 として与えられる2つの二分木がフリップ等価かどうかを判定するメソッドを、C++で実装していきます。 上図のような2つの木の場合、値が 1、3、5 のノードでフリップ操作を行えば、一方

完全二分木とは？二分木が与えられたとき、その木が完全二分木（Complete Binary Tree）であるかどうかを判定する問題を考えてみましょう。完全二分木とは、深さ n の木において、上から n-1 レベルまですべてのノードが埋まっており、最下層のノードは必ず左側から順に配置されている二分木のことです。例えば、次のような入力木が与えられたとします。この場合、すべてのノードが左詰めで配置されているため、出力は true（完全二分木である）になります。解法のアプローチこの問題は、幅優先探索（BFS）とフラグ変数を組み合わせることで効率的に解くことができます。具体的な手順は以下の通りです。木が

パンケーキソート(Pancake Sort)は、配列Aを並べ替えるユニークなソートアルゴリズムです。このアルゴリズム最大の特徴は、使用できる操作が「rev(arr, i)」、すなわち配列arrの先頭(0番目)からi番目までの要素を反転させるという1種類のみであるという点です。基本的な発想は選択ソートに似ています。最大の要素を繰り返し配列の末尾に移動させ、そのたびに扱う範囲(配列のサイズ)を1つずつ縮めていきます。例えば、入力が [54, 85, 52, 25, 98, 75, 25, 11, 68] であれば、出力は [11, 25, 25, 52, 54, 68, 75, 85, 98] に

問題の概要N個のノードを持つ二分木のルートが与えられます。各ノードには node.val 枚のコインが置かれており、木全体のコインの総数はちょうどN枚です。1回の操作では、隣接する2つのノード（親子関係にあるノード）を選び、1枚のコインだけを一方から他方へ移動できます（親から子への移動、子から親への移動のどちらも可能です）。すべてのノードがちょうど1枚のコインを持つ状態にするために必要な最小の操作回数を求めましょう。具体例例として、次のような木を考えてみます。ルート：0枚左の子：3枚右の子：0枚この場合の出力は 3 になります。まず左の子から2枚のコインをルートへ送ります（コイン1枚につき1操

鉄道旅行が盛んな国を、1年先の計画で旅することになったとします。旅行予定日は配列として与えられ、各日は1から365までの整数で表されます。切符（パス）は次の3種類が販売されています。1日パス：costs[0] ドル7日パス：costs[1] ドル30日パス：costs[2] ドルそれぞれのパスは、購入した日からその期間分だけ連続して乗車できます。たとえば2日に7日パスを購入すれば、2日・3日・4日・5日・6日・7日・8日の7日間にわたって旅行可能です。求めるのは、与えられた旅行日リストのすべての日をカバーするために必要な最小金額です。入力例と考え方たとえば days = [1,4,6,7,8,