C++

問題の概要 閉区間からなるリストが2つ与えられます。それぞれのリスト内では、区間どうしが互いに重複せず（ペアワイズに素）、昇順にソートされているものとします。このとき、2つの区間リストの共通部分（交差）を求めるのが本記事のテーマです。 閉区間 [a, b] とは、「a ≤ x ≤ b」を満たす実数 x 全体を表す集合のことです。2つの閉区間の共通部分は、空集合になるか、あるいは再び1つの閉区間として表されることが知られています。 たとえば、次のような入力を考えてみましょう。 A = [[0,2], [5,10], [13,23], [24,25]] B = [[1,5], [8,12],

最大二分木II（Maximum Binary Tree II）とは 本記事では、C++を用いて「最大二分木II」の問題を解く方法を詳しく解説します。 まず、最大木（Maximum Tree）についておさらいしましょう。最大木とは、すべてのノードが、その部分木に含まれる他のどの値よりも大きな値を持つ二分木のことです。 construct() メソッドの定義 リストAから根ノードを構築する construct() メソッドがあると仮定します。このメソッドは以下のように動作します。 リストAが空の場合、null を返します。 それ以外の場合、A[i] をリストAの最大要素とし、値 A[i] を持

文字列「abc」が有効(valid)であると定義します。さらに、任意の有効な文字列Vを2つの部分XとYに分割できるとき(X + Y = V、XまたはYは空でも可)、X + abc + Y もまた有効な文字列となります。例えば S = abc の場合、有効な文字列の例としては「abc」「aabcbc」「abcabc」「abcabcababcc」などが挙げられます。一方、「abccba」「ab」「cababc」「bac」などは無効な文字列です。この記事では、与えられた文字列Sが有効である場合にのみtrueを返すプログラムをC++で実装します。例えば、入力が「abcabcababcc」の場合、これは

二分木のルートが与えられたとき、異なる2つのノードAとB(AはBの祖先)が存在し、V = |Aの値 − Bの値| となるような最大値Vを求める問題を考えてみましょう。例えば、次のような二分木が与えられた場合を考えます。この場合、出力は 7 となります。祖先と子孫のノード間の差は [(8 - 3), (7 - 3), (8 - 1), (10 - 13)] のようになり、その中で最大なのは (8 - 1) = 7 だからです。解法のアプローチこの問題を解くには、以下の手順に従います。まず、答えを格納する変数 ans を 0 で初期化します。solve() というメソッドを定義します。このメソッド

問題の概要 ここでは、互いに異なる値を持つ二分探索木（BST）のルートが与えられたとします。この木を、各ノードの新しい値が「元の木に存在する値の中で、そのノードの値以上であるものの総和」と等しくなるように書き換えることを考えましょう。ただし、変更後も木が二分探索木としての性質（左の子 ＜ 親 ＜ 右の子）を保っている必要があります。 例として、入力の木が次のような場合を考えてみます。 このとき、出力される木は以下のようになります。 解決のためのアプローチ この問題は、逆中順走査（右部分木 → 現在のノード → 左部分木 の順で訪問する降順走査）を使うことでエレガントに解けます。BST

バイナリ行列の最短経路問題とは N×N の正方形グリッドを考えます。各セルは「空き(0)」または「ブロック(1)」のいずれかです。左上から右下へのクリアパスの長さが k であるとは、そのパスがセル C1, C2, …, Ck で構成され、次の条件をすべて満たすことを指します。 隣接するセル Ci と Ci+1 は8方向(上下左右+斜め)につながっている。つまり互いに異なり、辺または角を共有している。 C1 は位置 (0, 0) にある。 Ck は位置 (N−1, N−1) にある。 Ci が位置 (r, c) にあるとき、grid[r][c] は空き、すなわち 0 である。 この記事では、

文字列 s が、(・) および小文字の英字で構成されているとします。このとき、残った括弧列が「有効」になるように、括弧 ( または ) を任意の位置から最小限削除し、有効な文字列を1つ返すことを考えます。 括弧列が有効であるとは、次の条件を満たすことです。 空文字列である、または小文字のみを含む AB(A と B を連結した形)と表せる。ただし A・B はそれぞれ有効な文字列 (A) と表せる。ただし A は有効な文字列 たとえば、入力が a)b(c)d の場合、出力は ab(c)d となります。 アルゴリズムの考え方 この問題はスタックを使うことで効率的に解けます。対応する開き括弧を持た

問題概要0（陸地）と1（水）で構成される2次元グリッドが与えられます。島とは、上下左右の4方向に連結した0の最大のグループのことであり、閉じた島（Closed Island）とは、完全に水（1）に囲まれた島を指します。この記事では、グリッド内に存在する閉じた島の個数をC++で求める方法を解説します。例として、次のようなグリッドを考えてみましょう。1111111010000110101011101000010111111110このときの出力は 2 となります。完全に水に囲まれた島がちょうど2つ存在するためです。解法のアプローチ：DFS（深さ優先探索）この問題はDFSを用いて解くのが定石です。ポイ

問題の概要次のようなルールに従う二分木を考えます。root.val == 0 であるtreeNode.val が x であり、treeNode.left が NULL でない場合、treeNode.left.val = 2 * x + 1 となるtreeNode.val が x であり、treeNode.right が NULL でない場合、treeNode.right.val = 2 * x + 2 となるここで、この二分木は「汚染」されているものとします。つまり、すべてのノードの値が -1 に書き換えられている状態です。まず二分木を復元した上で、以下の FindElements クラスを実

問題の概要 商品名の文字列配列 products と、検索語 searchWord が与えられたとします。ここで、searchWord の各文字がタイプされるたびに、products の中から共通の接頭辞（プレフィックス）を持つ商品名を最大3つ提案するモジュールを設計することを目標とします。 候補となる商品が3つより多い場合は、辞書順で最小の3つを返す必要があります。つまり、検索語の各文字が入力されるたびに、その時点での推奨商品リストを求めるのがこの課題です。 入力例と出力例 例えば、入力が次のようになっている場合を考えます。 products = [mobile, mouse, mone

この記事では、C++ STLにおけるlistコンテナのswap()関数の機能と使い方について詳しく解説します。STLにおけるlistとは？listは、シーケンス内の任意の位置で定数時間での挿入と削除を可能にするコンテナです。listは双方向リンクリストとして実装されており、非連続的なメモリ割り当てを行います。配列、vector、dequeと比較して、listはコンテナ内の任意の位置への要素の挿入・抽出・移動において優れたパフォーマンスを発揮します。一方で、要素への直接アクセス（ランダムアクセス）は遅いという特徴があります。listはforward_listと似ていますが、forward_lis

本記事では、C++ STLにおけるdequeのmax_size()関数の機能と使い方について詳しく解説します。Deque（両端キュー）とは？Dequeは「Double Ended Queue（両端キュー）」の略で、コンテナの先頭と末尾の両方から要素の追加・削除が可能なシーケンスコンテナです。通常のキュー（待ち行列）データ構造では、データの挿入は末尾からのみ、削除は先頭からのみ行えます。バス停の行列をイメージすると分かりやすいでしょう。新しく来た人は列の「後ろ」に並び、列の「先頭」にいる人から順に乗車していきます。一方、両端キュー（Deque）では、先頭と末尾のどちら側からでも自由にデータを挿入

C++ STLにおけるlist::empty()およびlist::size()関数の動作、構文、具体的な使用例について詳しく解説します。 STLにおけるlistとは？ listは、シーケンス内の任意の位置で定数時間での挿入と削除を可能にするコンテナです。listは双方向リンクリストとして実装されており、非連続的なメモリ割り当てを行います。配列、vector、dequeと比較して、コンテナ内の任意の位置への要素の挿入・抽出・移動において優れたパフォーマンスを発揮します。一方で、要素への直接アクセス（ランダムアクセス）は遅いという特徴があります。listはforward_listと似ていますが、f

本記事では、C++のSTLにおけるlistのoperator=（代入演算子）の機能と具体的な使い方について詳しく解説します。STLにおけるlistとは？listは、シーケンス内の任意の位置に対して定数時間での挿入・削除を可能にするコンテナです。内部的には双方向リンクリストとして実装されており、非連続的なメモリ割り当てを行う点が大きな特徴です。listは、配列やvector、dequeと比較して、コンテナ内の任意の位置への要素の挿入・抽出・移動において優れたパフォーマンスを発揮します。一方で、要素への直接アクセス（ランダムアクセス）は遅いという弱点もあります。また、listはforward_li

C++のSTLにおいて、listコンテナが提供するremove()およびremove_if()関数の機能と使い方について詳しく解説します。 STLにおけるlistとは？ listは、シーケンス内の任意の位置に対して定数時間での挿入・削除を可能にするコンテナです。内部的には双方向リンクリストとして実装されており、非連続的なメモリ割り当てを行います。そのため、配列やvector、dequeと比較して、コンテナ内の任意の位置への要素の挿入・抽出・移動において優れたパフォーマンスを発揮します。一方で、要素への直接アクセス（ランダムアクセス）は遅いという特徴があります。listはforward_list

本記事では、C++ STLにおけるset::cbegin()関数とset::cend()関数について、その構文、動作、戻り値を詳しく解説します。C++ STLにおけるsetとは？C++ STLのsetは、必ず一意（重複なし）の要素を保持するコンテナです。set内では要素の値そのものがその要素を識別するため、同じ値を複数持つことができません。一度setコンテナに追加された値は後から変更できませんが、要素の削除や追加は可能です。内部的にはsetは二分探索木として実装されており、要素は常にソートされた順序で自動的に保持されます。set::cbegin()とはcbegin()関数はC++ STLに組み

本記事では、C++ STLにおける set::emplace_hint() 関数について、その構文、動作の仕組み、戻り値を詳しく解説します。C++ STLにおけるsetとは？C++ STLのsetは、重複しない一意な要素を保持するコンテナであり、通常はソートされた順序で要素を管理します。setの要素は「値そのもの」が識別子として機能するため、同じ値を複数持つことはできません。一度setコンテナに追加した値は後から変更できませんが、要素の削除や追加は自由に行えます。setは内部的に二分探索木（バイナリサーチツリー）として実装されており、高速な検索を実現しています。set::emplace_hin

本記事では、C++ STLに用意されている set::equal_range() 関数について、その構文、動作の仕組み、そして戻り値の内容を詳しく解説します。C++ STLにおけるset（セット）とは？C++ STLにおけるsetは、要素が必ず一意（ユニーク）であることが保証されたコンテナです。これは、要素の値そのものがその要素を識別する役割を果たすためです。一度setコンテナに追加した値は後から変更できませんが、値の削除や新たな追加は可能です。内部的には二分探索木として実装されており、高速な検索が行えるのが特徴です。set::equal_range()とはequal_range() はC++

本記事では、C++ STLのset::find()関数について、その構文、動作、そして戻り値をわかりやすく解説します。C++ STLにおけるsetとは？C++ STLのsetは、重複のない一意な要素を自動的にソートされた順序で格納する連想コンテナです。set内では要素の値そのものが識別子として機能するため、すべての要素が一意である必要があります。一度setに追加した値は後から変更できませんが、要素の追加や削除はいつでも可能です。また、setは内部的に二分探索木（赤黒木）として実装されており、高速な検索処理を実現しています。set::find()とはfind()関数は、<set>ヘッ

本記事では、C++ STLのset::get_allocator()関数について、その構文、動作、そして戻り値を詳しく解説します。C++ STLにおけるsetとは?C++ STLのsetは、要素が必ず一意である必要がある連想コンテナの一種で、要素は決められた順序で保持されます。set内では要素の値そのものがその要素を識別するキーとなるため、重複した要素を持つことができません。また、一度setコンテナに追加した値は後から変更することはできませんが、値の削除や新たな追加は可能です。setは内部的に二分探索木として実装され、高速な検索を実現しています。set::get_allocator()とは?g