C++

この記事では、二分木（バイナリツリー）がレベルごとにソートされているかどうかを確認する方法を解説します。レベルごとにソートされた二分木とは、次のような構造を持つ木のことです。各レベル内では、ノードが左から右に向かって昇順に並んでおり、さらに下のレベル（層）ほど、その上のレベルより大きな値を持つという特徴があります。アルゴリズムの考え方この問題は、レベル順走査（幅優先探索）を用いることで効率的に解決できます。手順は以下の通りです。1. レベル順走査を実行しながら、現在のレベルの最小値と最大値を記録します。2. 別の変数 prevMax を用意し、直前のレベルの最大値を保持します。3. 現在のレベ

はじめに二つの二分木が与えられたとき、小さい方の木がもう一方の二分木の部分木（サブツリー）として含まれているかどうかを判定する方法を解説します。例として、以下のような二つの木を考えてみましょう。この場合、2番目の木は1番目の木の部分木となっています。判定アルゴリズムの考え方この性質を確認するためには、大きい方の木を後順走査（post-order traversal）でたどり、各ノードを根とする部分木が2番目の木と完全に一致するかどうかを順番に調べます。一致する部分木が一つでも見つかれば、2番目の木は1番目の木の部分木であると判定できます。判定の流れは以下の通りです。1. 部分木側がNULLであ

本記事では、双方向連結リスト（Doubly Linked List）を用いて、文字列が回文（パリンドローム）であるかどうかを判定する方法を解説します。 まず、判定対象となる文字列の各文字を、双方向連結リストに順番に挿入します。その後、「left」と「right」という2つのポインタを用意し、リストの両端から同時に走査を行います。leftが指す文字とrightが指す文字が一致していれば、leftポインタを次のノードへ、rightポインタを前のノードへそれぞれ移動します。文字が一致しなかった場合は、その時点でfalseを返します。この処理は、leftとrightが同じノードを指すようになるか、ある

本記事では、ソートされていない配列の中に、互いにk距離（インデックス差）以内にある重複した要素が存在するかどうかを判定する方法を解説します。例えば、要素のリストが {1, 2, 3, 1, 4, 5} であり、k = 3 の場合を考えてみましょう。このとき、2つの「1」の間隔は3であるため、プログラムは true を返します。一方、k = 2 であれば、重複は検出されず false となります。アルゴリズムの考え方：ハッシュテーブル（セット）を活用この問題は、ハッシュテーブル（ここでは C++ の set）を使うことで効率的に解決できます。手順は以下の通りです。空のハッシュテーブル（セット）を

ここでは、与えられた二分木が「SumTree（総和木）」であるかどうかを判定する方法を解説します。まずは、SumTreeとはどのような木なのかを確認しておきましょう。 SumTreeとは SumTreeとは、すべての内部ノードが「左の子と右の子の値の合計」を保持する特殊な二分木です。木の根（ルート）には、それより下位に存在する全要素の合計値が格納されます。なお、葉ノードのみからなる木や空の木も、定義上はSumTreeとみなされます。以下はSumTreeの一例です。 例えば上図の木では、根の値26が左部分木（10 + 4 + 6 = 20）と右部分木（3 + 3 = 6）の合計と一致しており

原点を中心とする2つの同心円があるとします。内側の円の半径を r、外側の円の半径を R(R > r)とすると、この2つの円の間にはリング状の領域が生まれます。ここにもう1つ別の円があり、その半径 r1 と中心座標 (x, y) が与えられたとき、この円がリングの内側に完全に収まっているかどうかを判定するのが本記事のテーマです。 解き方の考え方 この問題は、三平方の定理(ピタゴラスの定理)を使うことで簡単に解けます。まず、対象の円の中心から原点までの距離 dis を次の式で計算します。 dis = √(x² + y²) 続いて、次の2つの条件を確認します。 内側の条件: 円のうち原点に最

この記事では、与えられた文字列が「サムストリング（sum-string：合計文字列）」であるかどうかを判定する方法を、C++のコード例とともにわかりやすく解説します。 サムストリングとは？ サムストリングとは、右端の部分文字列が、その直前にある2つの部分文字列の和として表せ、さらにその関係が文字列の先頭に向かって再帰的に成り立つ文字列のことです。 例として「12243660」という文字列を見てみましょう。 12 + 24 = 36 → 「36」は「12」「24」の直後に存在する 24 + 36 = 60 → 「60」は「24」「36」の直後に存在する このように条件が連鎖的に満たされるため

本記事では、C++を使って与えられた木グラフ（ツリーグラフ）が「線形（リニア）」であるかどうかを判定する方法を解説します。線形の木グラフとは、すべてのノード（頂点）を一本の線上に連ねて表現できるグラフのことです。 線形木グラフとは たとえば、下の図のようなグラフは一本の線で表現できるため、線形の木グラフです。 一方、次のように途中で分岐（複数の子ノード）を持つ木は線形ではありません。 線形グラフを判定する条件 ある木グラフが線形かどうかは、次の2つの条件で確認できます。 ノード数が1の場合、その木グラフは線形である。 n個のノードのうち (n − 2) 個のノードの次数が2である場合、そ

グラフが強連結（strongly connected）であるかどうかを、コサラジュ（Kosaraju）のアルゴリズムと深さ優先探索（DFS）を使って判定する方法を解説します。強連結グラフとは？グラフ内の任意の2つの頂点の間に、双方向へのパスが存在するとき、そのグラフは「強連結」であるといいます。なお、無向グラフは辺が双方向に移動できるため、連結であれば自動的に強連結となります。一方、有向グラフの場合は注意が必要です。連結ではあっても強連結ではないグラフも存在します。例えば、ある頂点から別の頂点へ一方通行でしか到達できない場合、そのグラフは連結ですが強連結ではありません。コサラジュのアルゴリズム

円と1本の直線があるとします。この課題では、直線が円に接するか、交わるか、あるいは円の外側を通るかを判定します。つまり、直線と円の位置関係には次の3つの場合が考えられます。判定の手順この問題は、以下の手順で解くことができます。円の中心から直線までの垂線の長さ P を求める垂線の長さ P と半径 r を比較するP > r の場合:直線は円の外側を通るP = r の場合:直線は円に接するP < r の場合:直線は円と交わる(円の内部を通る)垂線の距離を求める公式直線が ax + by + c = 0 で表され、円の中心点が (h, k) の場合、中心から直線までの垂線の距離は次の公式で

本記事では、与えられた行列が可逆（invertible、逆行列を持つ）かどうかをC++で判定する方法を解説します。可逆行列の条件ある行列 M の逆行列 M-1 は、次の式で表されます。$$M^{-1}=\frac{adj(M)}{|M|}$$この式から分かるように、分母には行列式（determinant）が含まれています。したがって、行列Mの行列式が0以外（非ゼロ）である場合にのみ逆行列が存在し、行列式が0の場合は逆行列を求めることができません。つまり、「行列が可逆かどうか」を判定するには、その行列式が非ゼロであるかを確認すればよいことになります。行列式の求め方行列式の計算は再帰的な処理として

問題の概要N × M の2次元配列が与えられたとします。この課題は、各行から1つずつ数値を選択し、選んだ要素のXOR（排他的論理和）が0以外（0より大きい値）になるようにできるかどうかを判定することです。例えば、次のような行列を考えてみましょう。77710107この場合、2行目の最後の要素以外が7と10で異なるため、XORを計算すると0以外の値になります。解法のアプローチこの問題の解法は非常にシンプルです。以下の手順で判定できます。まず、各行の最初の列の要素のXORを計算します。その結果が0以外であれば、答えは「可能」です。XORが0だった場合は、いずれかの行に2つ以上の異なる要素が含まれてい

問題の概要バイナリ文字列と整数 k が与えられたとき、その文字列が k ビットの2進数のすべての順列(パターン)を含んでいるかどうかを判定する問題です。例として、文字列「11001」で k = 2 の場合を考えてみましょう。2ビットで表せる数値のパターンは「00」「01」「10」「11」の 22 = 4 通りです。この文字列にはこれらすべてのパターンが部分文字列として含まれているため、有効な文字列と判断できます。アルゴリズムの考え方長さ k のビット列の組み合わせは合計 2k 通り存在します。判定は以下の手順で行います。長さ k のすべての2進パターンを生成し、文字列としてリストに格納するリス

ここでは、二分木（バイナリツリー）が二分探索木（BST）ではない場合を想定します。この二分木の中に、同じ値を持つノードが2つ以上存在するかどうかを判定する必要があります。BSTであれば中順走査（in-order traversal）によって値が昇順に並ぶため簡単に確認できますが、通常の二分木にはその性質がありません。そこで本記事ではハッシュセットを活用した効率的な解法を紹介します。アルゴリズムの考え方基本的なアプローチは以下の通りです。ハッシュセット（unordered_set）を用意します。木を走査しながら、各ノードの値を順番にチェックします。その値がすでにハッシュセット内に存在する場合は重

問題の概要 二分木が与えられたとき、その木の中にサイズ2以上の同一の部分木(重複部分木)が存在するかどうかを判定するのが本記事のテーマです。例として、次のような二分木を考えてみます。 この木には、サイズ2の同一の部分木が2つ含まれています。このように、同じ構造・同じノード値を持つ部分木が複数存在するかどうかを効率よくチェックする必要があります。 アプローチ:シリアライズとハッシュの活用 この問題は、部分木のシリアライズ(文字列化)とハッシュテーブルを組み合わせることで効率的に解くことができます。基本的なアイデアは以下の通りです。 各ノードから再帰的に部分木を文字列としてシリアライズし、ハ

本記事では、二分木（バイナリツリー）がレベルごとにソートされているかどうかを判定する方法を解説します。レベルごとにソートされた二分木とは、以下のような構造を持つ木のことです。このような二分木では、各レベル内でノードが左から右へ向かって昇順に並んでおり、さらに下のレベルほど、その上のレベルより大きな値を持つという特徴があります。アルゴリズムの考え方この問題は、レベル順走査（幅優先探索：BFS）を用いることで効率的に解決できます。手順は以下の通りです。キューを使ってレベル順にノードを走査します。現在のレベルの最小値（min_val）と最大値（max_val）を記録します。前のレベルの最大値を保持す

問題の概要ドット（.）と数字から構成される文字列を考えます。ドットはそのセルが空であることを示し、あるセルに数字 x が入っている場合は、そのセルから文字列内を左右どちらかの方向へ x 歩移動できることを意味します。このとき、同じセルを複数回訪問できるかどうかを判定するのが本記事の課題です。例として、文字列が「.2...2..」である場合を考えてみましょう。この場合、4番目のセルには2通りの経路で到達できます。ひとつは2番目のセルから右へ2歩進む方法、もうひとつは6番目のセルから左へ2歩進む方法です。アルゴリズムの考え方この問題を解くために、各セルの訪問回数を記録する配列 visited[]

配列に格納された要素のリストが与えられたとき、その要素列が二分探索木（BST）の先行順トラバーサル（プレオーダー走査）として成立するかどうかを判定する問題について解説します。例えば、数列が {40, 30, 35, 80, 100} の場合、対応する二分探索木は次のようになります。スタックを使った効率的な解法この問題は、スタックを1つ使うことで線形時間 O(n) で解くことができます。基本的な考え方は、「先行順走査では親ノードが子ノードより先に現れる」という性質を利用し、スタックで祖先ノードの候補を管理するというものです。具体的には、以下の手順に従います。空のスタックを定義する変数 root

ハンケル行列（Hankel行列）とは、正方行列の一種で、左下から右上へ向かう各反対角線（スキュー対角線）上の要素が、すべて同じ値となる行列のことです。この記事では、与えられた正方行列がハンケル行列であるかどうかをC++で判定する方法を解説します。まず、次のような5×5の行列を例に考えてみましょう。1234523456345674567856789この行列では、反対角線ごとに値が一定（例：1 ／ 2, 2 ／ 3, 3, 3 …）になっているため、ハンケル行列であることがわかります。ハンケル行列の判定条件ハンケル行列かどうかを判定するには、すべての要素について mat[i][j] = ai+j

10桁の携帯電話番号が与えられたとき、その番号が「ファンシーナンバー（覚えやすい特別な番号）」であるかどうかを判定するのが本記事の目的です。ファンシーナンバーには以下の3つの条件があり、少なくとも1つでも満たしていれば、その番号はファンシーナンバーとみなされます。 同じ数字が3回連続して現れる：例えば「555」など 3つの連続する数字が昇順または降順に並んでいる：例えば「123」「321」など 同じ数字が4回以上現れる：例えば「8965499259」では「9」が4回出現しています 例として挙げる「9859009976」は、「9」が4回出現しているため3つ目の条件を満たしており、ファンシーナ