Python

数値のリスト nums が与えられたとき、同じ値が連続して並んでいる要素をひとつのサブリストにまとめてパックするプログラムを作成します。ここで注意すべき点は、リスト内に1回しか出現しない要素であっても、それ単独のサブリストとして残す必要があるということです。たとえば、入力が nums = [5, 5, 2, 7, 7, 7, 2, 2, 2, 2] の場合、出力は次のようになります。[[5, 5], [2], [7, 7, 7], [2, 2, 2, 2]]同じ値でも離れて登場する場合は別々のサブリストになるため、2 が2箇所に分かれている点に注目してください。解き方の手順nums が空の場合

2次元グリッドがあり、各セルには文字列 r・g・b のいずれかの色が格納されているとします。このグリッドに対して、行 r・列 c を起点として、指定した色 target でフラッドフィル（flood fill：塗りつぶし）操作を行います。フラッドフィルとは、開始セル grid[r][c] と同じ色を持ち、上下左右に隣接して連結しているすべてのセルを、目標色 target へ一括置換する操作です。画像編集ソフトの「バケツツール」でおなじみのアルゴリズムですね。入力例と出力例たとえば、次のようなグリッドが与えられたとします。RRRRGBGBBここで (0, 0) を起点に緑（g）で塗りつぶすと、結

問題概要数値のリスト nums と、もう一つの値 target が与えられているとします。このとき、各ペアが i < j というインデックスの組み合わせであり、i と j が他のどのペアにも重複して使われず、かつ |nums[i] − nums[j]| ≥ target を満たすようなペアの最大数を求める必要があります。例えば、入力が nums = [2, 4, 6, 10, 11]、target = 5 の場合、出力は 2 になります。これは (2, 10) と (4, 11) という2組のペアを作れるためです。解法のアプローチこの問題は「ソート + 二重ポインタ(貪欲法)」で効率的に

連結リストが与えられたとき、隣り合う2つのノード(ペア)をすべて入れ替え、その結果の先頭ノード(head)を返すことを考えます。ここでの重要な制約は、ノードが持つ値を変更してはならないという点です。入れ替えられるのはノード自体(ポインタのつながり)のみです。例えば、リストが [1,2,3,4] の場合、実行結果は [2,1,4,3] となります。解決のためのアルゴリズムこの問題は、以下の手順に従って解くことができます。head が存在しない場合は、head をそのまま返します。first := head、second := head の次のノードとし、値 -1 を持つ新しいノード dummy

連結リスト（リンクリスト）が与えられたとき、その要素が回文を形成しているかどうかを判定することを考えます。例えば、リストの要素が [5,4,3,4,5] のような並びであれば回文ですが、[5,4,3,2,1] のような並びは回文ではありません。 この問題を解くために、ここでは「2つのポインタ（fast・slow）」を使った効率的な手法を採用します。前半部分を走査しながら逆順に連結し直し、後半部分と比較することで、追加のメモリをほとんど使わずに判定できます。 アルゴリズムの手順 fast := head、slow := head、rev := None、flag := 1 として初期化する

文字列 s が与えられたとき、その文字を並べ替えて(アナグラムを作って)回文にできるかどうかを判定する問題を考えてみましょう。 たとえば、入力が s = admma の場合、「admma」の文字を組み替えると「madam」という回文を作ることができるため、出力は True になります。 解法のアプローチ この問題は、次の手順で解くことができます。 c := 文字列 s に含まれる各文字の出現回数を記録するマップ(カウンター)を作る count := 0 で初期化する c のすべての値(出現回数)について、以下を繰り返す i が奇数の場合 count が 0 ならば、count を 1 増

問題の概要各ノードに0〜9のいずれかの数字が格納された二分木があるとします。この木を通り順走査（inorder traversal）した結果が回文（前から読んでも後ろから読んでも同じ並び）になっているかどうかを判定するプログラムを作成します。例えば、次のような木が入力として与えられた場合を考えてみましょう。この木の通り順走査の結果は [2, 6, 10, 6, 2] となり、左右対称の並びであるため、出力は True になります。解決のアプローチこの問題は、再帰を使わずにスタックを利用した反復的な通り順走査を行うことで解けます。手順は以下のとおりです。ルートが null の場合は True を

二分木が与えられたとき、最初の要素に葉ノード（リーフノード）の数、2番目の要素に非葉ノードの数を格納した2つの数値のペアを求める問題を考えてみましょう。例えば、次のような二分木が入力として与えられた場合を考えます。この木には葉ノードが3つ、非葉ノードが2つ存在するため、出力は (3, 2) となります。解き方のアルゴリズムこの問題は、再帰処理を使って以下の手順で解くことができます。ノード n が null（None）である場合は、(0, 0) を返します。n の左の子と右の子がどちらも null の場合（つまり n が葉ノードの場合）は、(1, 0) を返します。left := solve(n

問題の概要値「0」「1」「2」を含む二分木があるとします。根（ルート）には、少なくとも1つの「0」ノードと1つの「1」ノードが存在しています。ここで、「木の辺（エッジ）を1本削除すると、木が2つの異なる木に分割される」という操作を考えます。このとき、削除後に生成される2つの木のどちらにも「0」と「1」のノードが同時に含まれないように、辺を1本削除する方法が何通りあるかを求めるのがこの問題です。入力例例えば、次のような二分木が与えられたとします。この場合、出力は 1 となります。「0」から「2」へ向かう辺だけが、条件を満たす唯一の削除対象だからです。解法のアプローチこの問題は、DFS（深さ優先探

問題の概要 正の整数からなる2つのリスト coins と salaries が与えられます。coins[i] は i 番目のコインの価値を、salaries[j] は j 番目の労働者に支払うべき最低金額を表します。各種類のコインは1枚ずつしかなく、すべての労働者にちょうど1枚ずつコインを渡す必要があります。このとき、コインの配り方が何通りあるかを計算してください。ある労働者に渡されるコインの種類が異なる場合、その2つの配り方は「異なる」とみなします。答えが非常に大きくなる可能性があるため、結果は 109+7 で割った余りを返します。 例として、coins = [1, 2, 3]、salar

問題概要同じ長さを持つ2つのリスト weights（重さ）と values（価値）、および整数 capacity（容量）が与えられます。weights[i] と values[i] は、それぞれ i 番目のアイテムの重さと価値を表します。ここで特別なルールとして、各アイテムは何個でも（何度でも）選んでよいものとします。合計の重さが capacity を超えない範囲でアイテムを選ぶとき、得られる価値の合計の最大値を求めるのがこの問題です。これは「無制限ナップサック問題（Unbounded Knapsack Problem）」として知られる古典的な動的計画法の応用例です。たとえば、次の入力を考えて

nums という配列が与えられたとき、少なくとも1つの要素を含む「連続した部分配列」の中から、要素の積が最大になるものを見つけて、その積を返すことを考えます。例えば、配列が [1,9,2,0,2,5] の場合、連続する部分配列 [1,9,2] の積が最大となるため、出力は 18 になります。 解法のアプローチ この問題は動的計画法（DP）を使って効率的に解くことができます。ポイントは、負の数同士を掛けると正の数になる可能性があるため、各位置における「最大積」と「最小積」の両方を追跡することです。 具体的な手順は以下の通りです。 max_list：nums と同じサイズのリストを作成し、0で初

非負整数からなる長さ n の配列が与えられているとします。各要素はバーの高さを表し、それぞれのバーの幅は1です。このとき、雨が降った後に溜め込むことのできる水の総量を計算するのが本記事のテーマです。状況を図にすると、以下のようになります。図を見ると、水が溜まっている部分（青い箱）は全部で8個あります。したがって、このケースの出力は8となります。解法のアプローチこの問題は「スタック」を利用することで効率よく解けます。全体の手順は以下の通りです。スタック st、変数 water := 0、インデックス i := 0 を用意するi が高さ配列のサイズ未満である間、次の処理を繰り返すスタックが空である

数値のリスト nums と操作のリスト operations が与えられているとします。各操作は [L, R, X] という3つのフィールドを持ち、「インデックス L から R まで（両端を含む）のすべての要素に X を加算する」という意味です。すべての操作を適用し、最終的なリストを返すのがこの問題の目的です。 問題の例 たとえば、入力が次のような場合を考えてみましょう。 nums = [8, 4, 2, -9, 4] operations = [[0, 0, 3], [1, 3, 2], [2, 3, 5]] このときの出力は [11, 6, 9, -2, 4] になります。初期リストが [

はじめに 数値のリスト nums が与えられたとき、リスト内に複数回出現する要素を削除し、一度だけ出現する要素だけを、元のリストでの出現順序を保ったまま残すことを考えます。 例えば、入力が nums = [2, 4, 6, 1, 4, 6, 9] の場合、出力は [2, 1, 9] となります。これは、2・1・9 の3つの要素がそれぞれ一度しか登場しておらず、4 と 6 は2回ずつ出現しているため除外されるからです。 解決のアプローチ この問題は、各要素の出現回数を記録する辞書（ハッシュマップ）を使うことで効率的に解決できます。手順は以下の通りです。 出現回数をカウントするための空の辞書を

数値を格納した連結リスト（リンクリスト）が与えられたとき、複数回出現する要素を削除し、それぞれの値を1つだけ残すことを考えます。その際、元の連結リストにおける出現順序は維持しなければなりません。例えば、入力が 9] の場合、重複が取り除かれた結果は 9] となります。最初に出現した「4」と「6」は保持され、2回目以降の出現だけが削除されている点に注目してください。アルゴリズムの考え方この問題は、セット（set）を使って既に見た値を記録することで効率的に解けます。具体的な手順は以下の通りです。ノードが null でない場合：空のセット l を作成する一時ポインタ temp を先頭ノードに設定

括弧のみで構成された文字列が与えられたとき、その文字列を「正しい括弧列」(すべての開き括弧が必ず対応する閉じ括弧と一致する状態)にするために削除すべき括弧の最小数を求める関数をPythonで作成します。例えば、入力が (()))( の場合、出力は 2 になります。これは、正しい文字列 (()) を得るために余分な )( の2文字を削除する必要があるためです。解法のアプローチこの問題は、文字列を一度走査するだけで効率的に解くことができます。具体的には、以下の手順に従います。カウンタ total と temp をそれぞれ 0 で初期化する文字列 s 内の各文字 p について、次の処理を行うp が

問題の概要文字列 s が与えられます。先頭側から見て最初に現れる「連続した重複文字」を繰り返し削除していき、最終的に残る文字列を求めます。たとえば、入力が s = xyyyxxz の場合を考えてみましょう。まず yyy という連続する重複文字が削除されて xxxz となり、続いて xxx が削除されるため、最終的な出力は z になります。解法のアプローチ：スタックを活用この問題は、スタック（後入れ先出し・LIFO）というデータ構造を使うと効率的に解けます。アルゴリズムの手順は以下のとおりです。空のスタックを用意し、インデックス i を 0 で初期化する。i が文字列の長さ未満である間、以下を繰

はじめに 連結リスト（リンクリスト）が与えられたとき、それを逆順に並べ替えることを考えます。例えば、リストが 2 → 4 → 6 → 8 の場合、反転後の新しいリストは 8 → 6 → 4 → 2 となります。 本記事では、再帰処理を用いてこの問題を解く方法を、アルゴリズムの考え方から実際のコードまで詳しく解説します。 解決のためのアプローチ この問題は、各ノードの next ポインタの向きを先頭から順番に付け替えていくことで解決できます。具体的には、以下の手順に従います。 solve(head, back) という手続きを定義し、リストの反転を再帰的に行う head が存在しない（空の）

有向グラフが与えられたとき、その反転グラフ（逆グラフ）を求めることを考えてみましょう。反転とは、元のグラフにおいて u から v へ向かう辺 を、v から u へ向かう辺 に変える操作です。入力は隣接リスト形式で与えられ、ノード数が n の場合、ノードは 0, 1, ..., n-1 という番号で表されます。例えば、次のようなグラフが入力として与えられた場合：出力は以下のようになります：解法のアルゴリズムこの問題は、以下の手順で解くことができます。頂点数 n と同じ長さの空リスト ans を用意しますグラフの各インデックス i と、それに対応する隣接リスト l について処理を行いますl 内の各