C++

問題概要2つの二分木「original（元の木）」と「cloned（クローン木）」が与えられ、さらに元の木に存在する特定のノード target への参照が渡されます。クローン木は元の木とまったく同じ構造を持つコピーです。ここでの課題は、クローン木の中から target に対応する同じ位置のノードへの参照を見つけ出すことです。例えば、下図のような木が与えられ、target の値が 3 である場合、出力は 3 となります。解決のアプローチこの問題は、元の木とクローン木を同時に再帰的にたどることで解けます。両方の木は構造が完全に一致しているため、元の木の走査中に target を発見した時点で、クロ

本記事では、以下の操作をサポートするカスタムスタックをC++で設計する方法を解説します。ポイントは、インクリメント操作を毎回全要素に適用するのではなく、遅延評価（lazy propagation）の考え方を使って効率化することです。サポートする操作CustomStack(int maxSize)：最大要素数 maxSize を持つスタックを初期化します。スタックが maxSize に達した場合、それ以上の追加は行われません。void push(int x)：スタックのサイズが maxSize に達していない場合、要素 x をスタックの先頭に挿入します。int pop()：スタックの先頭要素を削

問題概要 二分探索木（BST）が与えられたとき、同じノード値を持つ「バランスの取れた二分探索木」を構築することを考えます。二分探索木がバランスしているとは、すべてのノードにおいて、左右の部分木の深さの差が1を超えないことと定義されます。条件を満たす結果が複数存在する場合は、そのいずれかを返して構いません。 例えば、次のような片寄った木が与えられたとします。 解き方のアプローチ この問題を解く鍵となるのは、「二分探索木を中順走査（in-order traversal）すると、ノードの値が昇順にソートされた配列が得られる」という性質です。ソート済みの配列から毎回中央の要素を根として選び、再帰的

整数xの「パワー」とは、次の手順を繰り返してxを1へ変換するまでに必要なステップ数として定義されます。xが偶数の場合：x = x / 2xが奇数の場合：x = 3 * x + 1例えば、x = 3のパワーは7です。これは、3が1になるまでに7ステップかかるためです（3 → 10 → 5 → 16 → 8 → 4 → 2 → 1）。なお、この変換手順は「コラッツ予想」として知られる数列に関連しており、任意の正の整数は必ず1に到達すると予想されています。ここで、整数lo、hi、kが与えられたとします。区間[lo, hi]内のすべての整数をパワー値の昇順にソートし、パワー値が同じ場合は整数そのものの

整数配列 nums が与えられたとき、その中から「約数がちょうど4個」である整数を見つけ出し、それらの約数の総和を計算する問題を考えてみましょう。もし該当する整数が配列内に1つも存在しない場合は、0 を返します。例えば、入力が [21, 4, 7] の場合、出力は 32 になります。これは次のような理由によるものです。21 の約数は 1, 3, 7, 21 の4つ → 条件を満たす4 の約数は 1, 2, 4 の3つ → 条件を満たさない7 の約数は 1, 7 の2つ → 条件を満たさないしたがって、答えは条件を満たす 21 の約数の総和である 32 となります。解法のアプローチこの問題を解く

問題の概要昇順にソートされた単方向連結リストが与えられたとき、それを高さ平衡な二分探索木(BST)に変換することを考えます。例えば、リストが [-10, -3, 0, 5, 9] の場合、生成される木は次のようになります。アルゴリズムのポイントこの問題を効率よく解く鍵は、リストの中央ノードを見つけて、それを木のルートにすることです。中央ノードより前の部分リストからは左部分木を、後ろの部分リストからは右部分木を再帰的に構築します。中央ノードの探索には、2つずつ進む高速ポインタ(fast)と1つずつ進む低速ポインタ(slow)を組み合わせる手法が便利です。手順リストが空の場合はNULLを返します。

問題の概要 複数の単語からなる文字列が与えられたとき、その文字列内の単語の並び順を逆にすることを考えます。たとえば、入力文字列が「The quick brown fox jumps over a lazy dog」であれば、出力は「dog lazy a over jumps fox brown quick The」となります。 解き方のアプローチ この問題は、以下の手順で解くことができます。 getString() 関数を定義します。引数として文字列 s を受け取り、次のように動作します。 i := 0、j := s のサイズ − 1 で初期化します。 s[i] が空白であり、かつ i が

問題の概要「12345678910111213...」のように無限に続く整数列を考えます。この数列のn番目の桁がどの数字になるかを求めるのが本記事の課題です。例えば、入力が11の場合、数列を並べると「123456789101112」となり、11番目の桁は「0」であるため、出力は0になります。アルゴリズムの考え方すべての数字を実際に並べて数えるのは非効率です。そこで、桁数ごとの数字の個数を利用し、n番目の桁がどの数に属するかを効率的に特定します。1桁の数(1〜9)は9個で合計9桁、2桁の数(10〜99)は90個で合計180桁、3桁の数(100〜999)は900個で合計2700桁というように、各桁

負でない整数 num が文字列として与えられているとき、そこから k 桁を取り除き、残った数字で作られる新しい数をできるだけ小さくすることを目指します。例えば、入力が「1432219」で k = 3 の場合、結果は「1219」となります。 この問題は、スタックを活用した貪欲法（グリーディアルゴリズム）によって効率的に解くことができます。 解法のアプローチ 基本となる発想は、「大きい数字がその後ろの小さい数字より先に現れている箇所を優先的に削除する」というものです。文字列を左から右へ走査しながらスタックに数字を積んでいき、スタックの先頭にある数字がこれから読み込む数字より大きい場合は、それをポッ

「等差数列」とは、少なくとも3つの要素から構成され、隣り合う任意の2要素の差がすべて等しい数列のことです。例えば、[1, 3, 5, 7, 9]、[7, 7, 7, 7]、[3, -1, -5, -9] などは等差数列ですが、[1, 1, 2, 5, 7] は差が一定ではないため等差数列にはなりません。 問題の定義 N個の数からなる0始まりの配列Aが与えられます。この配列の「スライス」とは、0 <= P < Q < N を満たす整数のペア(P, Q)が表す部分配列のことです。スライス(P, Q)が表す数列 A[P], A[P+1], ..., A[Q-1], A[Q] が等差

問題概要 rows × cols のサイズを持つスクリーンと、空でない単語からなるリストで表現された文（センテンス）が与えられます。このとき、与えられた文がスクリーン上に何回完全に収まるかを求めます。この問題には以下の条件があります。 単語が2行にまたがって分割されることはありません。 文中の単語の並び順は変更してはいけません。 隣接する単語の間にはスペースが1つだけ入ります。 文に含まれる単語の総数は100を超えません。 各単語の長さは1以上10未満です。 1 ≤ rows, cols ≤ 20,000 です。 例として、rows = 3、cols = 6、文が [a, bcd, e]

問題概要 区間のリストが与えられたとき、各区間 i について、「始点が区間 i の終点以上であるような区間 j」が存在するかどうかを調べます。このとき、区間 j は区間 i の「右側」にあると言います。 各区間 i に対して、条件を満たす区間 j のうち始点が最小となるもののインデックスを記録します。該当する区間が存在しない場合は -1 を格納し、最終的に各区間に対応する値を配列として出力します。 たとえば、入力が [[3,4], [2,3], [1,2]] の場合、出力は [-1, 0, 1] となります。 [3, 4]: 右側に位置する区間が存在しないため -1 [2, 3]: 始点が

任意の深さでネストされた三項式（三項演算子による条件式）を表す文字列が与えられたとき、その式を解析して最終的な評価結果を求めるのが本問題です。入力となる式は常に有効であり、構成要素は数字「0〜9」、「?」、「:」、「T」、「F」のみです（TとFはそれぞれTrue・Falseを表します）。この問題には以下のような性質があります。 与えられる文字列の長さは10000以下である。 各数値は必ず1桁である。 条件式は右から左に向かってグループ化される。 条件部分は必ずTまたはFであり、数値が条件になることはない。 式の評価結果は、必ず0〜9のいずれかの数字、T、またはFのいずれかになる。 動作例

132パターンとはn個の整数からなる数列 a1, a2, ..., an を考えます。「132パターン」とは、i < j < k を満たす部分列 ai, aj, ak のうち、ai < ak < aj が成り立つものを指します。つまり、「小さい値 → 大きい値 → 中間の値」という順序で並ぶ3つの要素が数列内に存在するかどうかを判定するアルゴリズムを設計するのが課題です。例として、入力が [-1, 3, 2, 0] の場合を考えてみましょう。このとき [-1, 3, 2]、[-1, 3, 0]、[-1, 2, 0] という3つのパターンが存在するため、出力は true

問題概要：「100ゲーム」とは「100ゲーム」は、2人のプレイヤーが交互に1から10までの整数を1つずつ選び、現在の合計値に加算していくゲームです。最初に合計を100以上にしたプレイヤーの勝ちとなります。ここでは、このゲームを少し変更したバージョンを考えます。プレイヤーは同じ整数を二度と使えないものとします。つまり、1〜15などの共通の数字プールから重複なしで数字を引き続け、合計が100以上に達した時点で勝敗が決まります。具体的には、整数 maxChoosableInteger（選べる最大の数字）と desiredTotal（目標となる合計値）が与えられたとき、両者のプレイヤーが最善を尽くす前

問題の概要 「abcdefghijklmnopqrstuvwxyz」というアルファベット順の文字列を無限に循環させた文字列 s を考えます。このとき s は次のような形になります。 「...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....」 ここで、別の文字列 p が与えられます。私たちの課題は、p の空でない部分文字列のうち、s に含まれるものが全部で何種類あるかを求めることです。つまり、入力として文字列 p を受け取り、s 内に存在する p の異なる非空部分文字列の個数を出力します。 例えば、入力が「zab」の場合

順番に頂点を結ぶと多角形になる点列が与えられたとき、その多角形が凸多角形であるかどうかを判定する問題を考えます。 制約条件は以下の通りです。 点の数は最低3個、最大10,000個 各座標の値は -10,000 以上 10,000 以下の範囲に収まる 与えられた点列が形成する多角形は常に単純多角形(simple polygon)であると仮定できる。つまり、各頂点でちょうど2本の辺が交わり、それ以外の場所で辺同士が交差することはない 例えば、入力が [[0,0],[0,1],[1,1],[1,0]] の場合、この4点は単位正方形を形成するため凸多角形であり、結果として true を返します。

問題の概要小文字の英字と半角スペースのみで構成されるフレーズのリストが与えられ、そこから「ビフォーアフターパズル（Before and After Puzzles）」と呼ばれる新しいフレーズを生成することを考えます。各フレーズには先頭・末尾にスペースがなく、連続するスペースも含まれていないものとします。ビフォーアフターパズルとは、2つのフレーズを結合してできるフレーズのことです。条件は「1つ目のフレーズの最後の単語」と「2つ目のフレーズの最初の単語」が一致することで、この共通単語を介して2つのフレーズをつなぎ合わせます。求めるのは、リスト内のすべての異なるペア phrases[i] と phr

問題の概要1、2、3の3種類の色が格納された配列colorsがあるとします。いくつかのクエリが与えられ、各クエリは2つの整数iとcから構成されます。このとき、指定されたインデックスiからターゲットの色cまでの最短距離を求める必要があります。該当する色が存在しない場合は-1を返します。例えば、colors配列が[1,1,2,1,3,2,2,3,3]、queries配列が[[1,3],[2,2],[6,1]]である場合、出力は[3,0,3]となります。その理由は以下の通りです。インデックス1から最も近い「3」はインデックス4に存在するため、距離は3インデックス2から最も近い「2」はインデックス2自

問題概要小文字の英字と括弧で構成された文字列 s が与えられます。最も内側の括弧から順に、対応する括弧のペアの中にある文字列を反転していき、最終的な結果には括弧が一切含まれないようにします。たとえば、入力が (hel(lowo)rld) の場合、出力は dlrlowoleh になります。処理は次のように段階的に進みます。(hel(lowo)rld) → (hel(owol)rld) → dlrlowolehまず最も内側の (lowo) が反転されて owol となり、続いて外側の括弧内全体 helowolrld が反転されて dlrlowoleh が得られます。解法のアプローチこの問題は、括弧