Python

問題概要数値のリスト nums が与えられます。これと同じ長さの新しいリストを作成し、インデックス i の位置には、nums[i] よりも大きい「右側の次の要素」を格納します。ここで重要なのは、リストの末尾に達したら先頭に戻って探索を続けるという循環（リング状）の扱いです。もし右側により大きい数が存在しない場合は -1 を設定します。たとえば、入力が [4, 5, 1, 3] の場合、出力は [5, -1, 3, 4] となります。4 の右側で最初に現れるより大きい数は 55 の右側にそれより大きい数はないので -11 の右側では 33 の右側では、末尾を超えて先頭に戻ると 4 が見つかるアル

問題概要 二分木（バイナリツリー）が与えられたとき、ルートノードからリーフノードへ至る任意のパスの中で、合計値が最大となるものを求める必要があります。 例として、次のような二分木が入力された場合を考えてみましょう。 この場合の出力は 29 になります。ルートから「5 → 9 → 7 → 8」というパスを辿ったときの合計が 29 となるためです。 解法のアプローチ この問題は、深さ優先探索（DFS）を用いて、ルートから各リーフまでのすべてのパスを再帰的に走査することで解けます。具体的な手順は以下のとおりです。 walk() 関数を定義します。引数として現在のノード node と、そこまでの

問題の概要各セルにコインが置かれた2次元行列（マトリックス）があるとします。左上の [0,0] の位置からスタートし、右または下にのみ移動できるという制約のもとで、右下隅まで移動する過程で収集できるコインの最大数を求めるのがこの問題です。例として、次のような入力が与えられた場合を考えてみましょう。14226005この場合、出力は 14 になります。これは、パス [1, 4, 2, 2, 5] を通ることで、合計14枚のコインを集められるためです。解き方（動的計画法）この問題は動的計画法（DP）を使うと効率的に解けます。考え方はシンプルで、「あるセルに到達した時点でのコインの最大累積数」は、「そ

2次元マトリクスMが与えられます。各セルには色を表す値が格納されており、上下左右に隣接する同色のセル同士はひとつのグループとして扱われます。ここで、「ひとつのグループに含まれるすべてのセルを任意の色に塗り替える」という操作を考えます。すべてのセルを同じ色に揃えるために必要な最小の操作回数を求めるのが本記事のテーマです。ただし、一度色を変えたセルは、それ以降二度と変更できないという制約があります。 入力例と出力 例として、次のようなマトリクスを考えてみましょう。 222211112321 この場合の出力は2となります。たとえば、下段左端の「2」のセルを色1で塗り、続いて下段の「3」を色1で塗る

問題の概要 同じ行数・列数を持つ2つの行列、元の行列 M とターゲット行列 T が与えられているとします。使用できる操作は「ある1つの列を選んで反転する」だけで、この操作を行うと、その列内のすべての 1 が 0 に、0 が 1 に変換されます。一方、行の並べ替えは何度でも無料で行えるものとします。この条件下で、行列 M を T と完全に一致させるために必要な最小の操作回数を求めてください。どうしても一致させられない場合は -1 を返します。 たとえば、入力が次のようなケースを考えてみましょう。 M = 001011 T = 011011 このとき出力は 1 になります。まず、行を次のように並べ

完全二分木とは二分木が与えられたとき、その木が完全二分木(complete binary tree)であるかどうかを判定することを考えます。完全二分木とは、最後のレベルを除くすべてのレベルがノードで埋め尽くされており、最後のレベルのノードはすべて可能な限り左側に寄せられている二分木のことです。例えば、次のような二分木が入力として与えられた場合、出力は True になります。アルゴリズム(BFSによる判定方法)この問題は、幅優先探索(BFS)を使って効率的に解けます。木をレベル順に走査し、初めて空のノード(None)が出現した後に再びノードが出現したら、その木は完全二分木ではないと判断できます。

問題概要0から n-1 までの番号で表される n 個の都市と、ある都市から別の都市へ向かう一方通行の道路のリストが与えられます。このとき、「どの都市から出発しても、他のどの都市にも到達できるか」どうかを判定します。たとえば、入力が n = 3、roads = [[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]] の場合、出力は True になります。これは、都市0から都市1へ移動でき、都市1から都市0へも戻れるためです。解法のアプローチこの問題は、グラフが「強連結(strongly connected)」であるかどうかを判定する問題と同じです。以下の

はじめに 数字だけで構成された文字列 s が与えられ、「その文字列の中に、連続して降順に並ぶ整数が含まれているかどうか」を判定することを考えます。 たとえば、入力が s = 99989796 の場合、この文字列は [99, 98, 97, 96] という連続した降順の整数列として分割できるため、出力は True になります。 アルゴリズムの考え方 この問題は、先頭から何桁分を最初の整数として切り出すかを順に試しながら、残りの部分が「前の値 − 1」という規則で続いているかを再帰的に確認するバックトラッキングで解くことができます。具体的な手順は次のとおりです。 引数に pos(現在の位置)と

一意な（重複のない）数値のリスト nums が与えられたとします。このとき、nums 内で連続している数値をひとつの包括的な区間としてまとめ、ソート済みの2次元配列として出力することを目標とします。たとえば、入力が nums = [10, 11, 12, 15, 16, 17, 28, 30] の場合、出力は [[10, 12], [15, 17], [28, 28], [30, 30]] となります。これは、10〜12 と 15〜17 がそれぞれ連続した数値のまとまりである一方、28 と 30 は前後の数値とつながっていないため、単独の区間 [28, 28]、[30, 30] として表現され

ある整数 n が与えられたとき、[0, n)(0 以上 n 未満)の範囲の数値を使って生成できる一意な二分探索木(BST)の個数を求めることを考えます。答えが非常に大きくなる可能性があるため、結果は 10^9 + 7 で割った余りを返します。 たとえば、入力が n = 3 の場合、出力は 5 になります。これは {0, 1, 2} の3つの値から作れる二分探索木の形状がちょうど5通り存在するためです。 この問題の鍵となる「カタラン数」 二分探索木の個数は、キーの具体的な値には依存せず、ノードの個数 n だけで決まります。n 個のノードから構成できる二分探索木の総数は、数学では「カタラン数」とし

文字列 s が、開き括弧「(」と閉じ括弧「)」のみで構成されているとします。ここでは、括弧の対応（バランス）が正しく取れているかどうかを判定するプログラムを作成します。 たとえば、入力が s = (()())(()) の場合、すべての括弧が正しく入れ子になっているため、出力は True になります。一方、「)(」のように閉じ括弧が先に現れたり、開き括弧が余ったりする場合は False となります。 解き方のアプローチ この問題は、整数型のカウンターを1つ用意するだけで効率的に解けます。手順は次のとおりです。 カウンター num_open を 0 で初期化する。 文字列 s 内の各文字 c に

文字列処理の定番問題として、丸括弧「()」・波括弧「{}」・角括弧「[]」といった複数種類の括弧が混在する文字列が与えられ、その括弧がすべて正しく対応しているかどうか（バランスが取れている＝整形式であるか）を判定する方法を解説します。問題の概要たとえば、入力が s = ([()()]{[]})() のような文字列だった場合、開き括弧と閉じ括弧が正しい順序で対応しているため、出力は True になります。逆に、閉じ括弧が先に現れたり、種類の異なる括弧が交差していたりすると False を返す必要があります。アルゴリズムの考え方：スタックを使うこの問題はスタック（Stack）というデータ構造を使う

問題の概要二分探索木（BST）と2つの値 low、high が与えられたとき、[low, high] の範囲（境界値を含む）に該当しないノードをすべて木から削除するプログラムを作成します。例として、次のようなBSTを考えてみましょう。ここで low = 7、high = 10 とした場合、範囲外のノード（5 や 1 など）が削除され、出力は次のようになります。解法のアプローチこの問題は再帰を利用することで簡潔に解くことができます。手順は以下の通りです。関数 solve() を定義します。引数は root（現在のノード）、low、high の3つです。root が null（空）の場合は何もせず

はじめに：BSTとは何か二分木が与えられたとき、それが二分探索木（Binary Search Tree：BST）であるかどうかを判定することは、データ構造の学習やコーディング面接でよく出題される定番の問題です。BSTには以下のような重要な性質があります。左部分木に含まれるすべてのノードの値は、現在のノードの値より小さい右部分木に含まれるすべてのノードの値は、現在のノードの値より大きいこれらの性質は、木の中のすべてのノードに対して再帰的に成り立つたとえば、次のような二分木を考えてみましょう。ルート：5左の子：1右の子：9（その左の子：7、さらに左の子：6・右の子：8／右の子：10）この場合、すべ

問題の概要 文字列 s が与えられたとき、文字列内の2つの文字を最大1回だけ入れ替える（スワップする）ことで得られる、辞書式順序で最も小さい文字列を求めます。 例えば、入力が zyzx の場合、出力は xyzz となります。最初の文字 z を x と入れ替えることで、辞書式順序で最小の文字列が得られます。 解法のアプローチ この問題を解くために、以下の手順に従います。 temp：文字列 s と同じサイズの配列を作成し、0で初期化します。 m：文字列の長さから1を引いた値（末尾のインデックス）で初期化します。 i を文字列の末尾から先頭へ向かってループさせます。 s[i] < s[m

単一連結リストとターゲットとなる値が与えられたとき、リストの中からターゲットと同じ値を持つノードをすべて削除し、残りの連結リストを返すことを考えます。 たとえば、入力が [5,8,2,6,5,2,9,6,2,4] で削除したい値が 2 である場合、出力は [5, 8, 6, 5, 9, 6, 4] となります。 解き方のアルゴリズム 変数 head に先頭ノードを保存しておきます。 node と node.next がどちらも存在する間、以下の処理を繰り返します。 node.next の値がターゲットと等しい間、node.next を node.next.next で置き換えて、該当ノード

問題の概要 片方向リンクリスト(単方向連結リスト)があり、このリンクリストは最上位桁(MSB)から順に並んだ2進数を表しているとします。このリンクリストを受け取り、対応する10進数の値を返すプログラムを作成しましょう。 たとえば、入力が [1,0,1,1,0] の場合、2進数「10110」は10進数で 22 になるため、出力は 22 となります。 解決の手順 以下のステップで処理を進めます。 空のリスト l を用意する ノードが null になるまで、各ノードの値を l の末尾に追加し、node を次のノードへ進める k := 0、v := 0 と初期化する i をリストの末尾(サイズ −

数値のリスト nums と、+、-、/、* などの演算子を表す文字列 op、さらに値 val が与えられたとします。このとき、nums 内のすべての数値に対して val を用いた演算を実行し、その結果をリストとして返すプログラムを作成します。 たとえば、入力が [5, 3, 8]、演算子が *(掛け算)、val が 3 の場合、出力は [15, 9, 24] となります。 解決のための手順 結果を格納するための新しい空のリスト res を作成する nums の各要素 i について、以下の処理を繰り返す: op が + の場合:res の末尾に i + val を追加する op が - の

数値のリスト nums が与えられ、すべての値を等しくすることを考えます。ここで「リストから1つの要素を選び、それ以外のすべての値を1ずつ増やす」という操作が許されているとします。このとき、すべての要素の値を等しくするために必要な最小の操作回数を求めます。 たとえば、入力が [2, 4, 5] の場合、出力は 5 になります。 解法のポイント 「選んだ要素以外を1ずつ増やす」という操作は、相対的な差に注目すると「選んだ1つの要素だけを1減らす」操作と同じ効果があります。そこで、各要素をリストの最小値まで揃えることを考えると、各要素 num に必要な操作回数は num - min_val となり

問題の概要 数値のリスト nums が与えられたとき、各要素 nums[i] を「その要素より左側にある要素の中で最も小さい値」に置き換えることを考えます。ただし、先頭の要素 nums[0] の左側には要素が存在しないため、0 に置き換えます。 例えば、入力が [15, 7, 9, 16, 12, 25] の場合、出力は [0, 15, 7, 7, 7, 7] となります。2番目以降の要素が、それぞれ自分より左側の最小値で置き換えられているのが分かりますね。 解き方のアプローチ この問題は、リストを一度だけ走査しながら「それまでに見た最小値」を変数に保持しておくことで、O(n) の計算量で効