Python

数値のリスト nums と、2つの整数 size と k が与えられているとします。ここで、「長さ size の連続する部分リストを選び、その範囲内のすべての要素を1ずつ増やす」という操作を考えます。この操作は最大 k 回実行でき、その結果として nums 内で実現可能な最小値の最大値を求めるのがこの問題です。問題例たとえば、入力が次のような場合を考えてみましょう。nums = [2, 5, 2, 2, 7]size = 3k = 2この場合、出力は 3 になります。具体的には、まず [2, 5, 2] の範囲に操作を適用して [3, 6, 3, 2, 7] とし、次に [6, 3, 2] の

同じ長さの数値リスト A と B、および二次元リスト C が与えられます。C の各要素は [i, j] という形式で、「A[i] と A[j] は何度でも入れ替えてよい」ということを表しています。このとき、入れ替えを行った後の A[i] = B[i] となるペアの最大数を求めるのがこの問題です。たとえば、入力が A = [5, 6, 7, 8]、B = [6, 5, 8, 7]、C = [[0, 1], [2, 3]] の場合、出力は 4 になります。A[0] と A[1]、そして A[2] と A[3] をそれぞれ入れ替えることで、すべての位置で A[i] = B[i] を満たすことができる

問題の概要二分木が与えられたとき、親子関係にある2つのノードを同時に選ばないという制約のもとで、選択できるノードの値の合計の最大値を求める問題を考えてみましょう。例えば、次のような二分木が入力として与えられたとします。この場合、出力は 17 になります。これは、10、4、3 の3つのノードは互いに親子関係（隣接関係）にないため、すべて選択できるからです。解き方のアプローチこの問題は、各ノードについて「そのノードを選ぶ場合」と「選ばない場合」の2つの状態を再帰的に計算することで解けます。手順は以下の通りです。関数 f() を定義します。引数としてノードを受け取ります。ノードが null（存在しな

小文字のアルファベットのみで構成された文字列のリスト words が与えられたとき、互いに共通する文字を1つも持たない2つの異なる単語を選び、その長さの合計の最大値を求める問題を考えてみましょう。 例えば、入力が words = [abcd, mno, abdcmno, amno] の場合、出力は 7 になります。これは、共通する文字を持たない単語の組み合わせが [abcd, mno] であり、その長さの合計が 4 + 3 = 7 となるためです。 解決のアプローチ この問題はビットマスク(bitmask)を使うことで効率的に解くことができます。各単語に出現する文字を26ビットの整数として表現

はじめに複数のソート済みリストが与えられたとき、それらを1つのソート済みリストにまとめる問題は、アルゴリズム学習における定番の課題です。この問題を効率的に解くには、ヒープ（優先度付きキュー）というデータ構造を利用するのが有効です。たとえば、[1, 4, 5]、[1, 3, 4]、[2, 6] という3つのソート済みリストがある場合、マージ後の最終的なリストは [1, 1, 2, 3, 4, 4, 5, 6] になります。アルゴリズムの手順この問題は、次の手順で解くことができます。リスト群 lists のサイズを n とします。空のヒープ（heap）を用意します。各リスト lists[i] を走

0と1のみが含まれるリストがあるとします。このリストに対して、先頭または末尾から値を削除できるものとします。最終的に、残ったリスト内の0と1の個数が等しくなるようにするには、最小で何回の削除が必要かを求めるのが目的です。問題の例たとえば、入力が nums = [1, 1, 1, 0, 0, 1] の場合を考えてみましょう。先頭の「1」と末尾の「1」を1つずつ削除すれば、残りは「1」が2個、「0」が2個となり、バランスが取れます。したがって、出力は 2 となります。解法のアプローチこの問題は、「累積和（prefix sum）」とハッシュマップを組み合わせたテクニックで効率的に解けます。考え方の手

2つのリスト間の最小差とは2つのリスト L1 と L2 が与えられたとき、L1 のある要素と L2 のある要素を組み合わせたときに生じる「差」の中で、最も小さいもの（絶対値が最小となる差）を求める問題です。例えば、入力が L1 = [2, 7, 4]、L2 = [16, 10, 11] の場合、出力は 3 になります。これは、10 − 7 = 3 という差が最も小さいためです。解法のアプローチ：ソート＋双方向ポインタこの問題は、両方のリストをソートしてから、2つのポインタを使って効率的に比較していくことで解けます。手順は以下の通りです。リスト L1 をソートし、リスト L2 もソートするans

数値のリスト nums が与えられます。ここでは「ある要素を任意の値に書き換える」という操作を最大3回まで実行できるものとし、操作後のリストにおける最大値と最小値の差（レンジ）を最小化することを目指します。 例えば、入力が nums = [2, 3, 4, 5, 6, 7] の場合、出力は 2 になります。これは、リストを [4, 3, 4, 5, 4, 4] のように書き換えることで、最大値 5 から最小値 3 を引いた差が 2 になるためです。 解決のためのアプローチ この問題を解く鍵となるのは、次のような発想です。 3つの要素を自由に書き換えられるということは、実質的に「ソート済みリ

問題の概要各行に3つの値を持つタスクの行列と、もうひとつの値 k が与えられているとします。タスクの中から k 行を選び、それを S と呼ぶことにします。このとき、次の合計値が最小になるように行を選択し、その合計を答えとして返すのが目的です。max(S[0, 0], S[1, 0], ..., S[k-1, 0]) + max(S[0, 1], S[1, 1], ..., S[k-1, 1]) + max(S[0, 2], S[1, 2], ..., S[k-1, 2])言い換えると、3つの列それぞれがコストに寄与し、各列のコストは「S 内でのその列の最大値」として計算されます。なお、空のリス

問題の概要 数値のリスト nums ともうひとつの値 k が与えられたとき、「min(S) + max(S) ≤ k」を満たす空でない部分集合 S の個数を求めます。ここで重要なのは、部分集合がマルチセット（重複を許す集合）として扱われる点です。部分集合はリスト内の「値」そのものではなく「特定の位置にある要素」を参照するため、同じ値の要素が複数あっても、それらは互いに異なる部分集合としてカウントされます。 たとえば、入力が nums = [2, 2, 5, 6]、k = 7 の場合、出力は 6 になります。条件を満たす部分集合は、[2]、[2]、[2, 2]、[2, 5]、[2, 5]、[2,

問題の概要二分木が与えられたとき、最も頻繁に出現する「部分木の合計値」を求めることを考えます。ここでいうノードの部分木合計とは、そのノード自身を含め、ノードより下にあるすべての値を足し合わせたものです。たとえば、次のような入力が与えられたとします。この場合、出力は「3」になります。なぜなら、3は2回出現するからです。1回目は左の葉ノードの値として、もう1回は木全体の合計値 3 + 6 + (-6) = 3 として現れるためです。解決のアプローチこの問題を解くには、次の手順に従います。count := 空のマップ（辞書）を作成する関数 getSum() を定義する。この関数はノードを引数として受

問題の概要0からn-1までの番号で表されるn人の人がいるとします。また、友人関係を表すタプルのリストfriendsが与えられ、friends[i][0]とfriends[i][1]は互いに友人であることを示しています。このとき、全員が少なくとも1人の友人を持っているかどうかを判定するプログラムを作成します。具体例例えば、入力が n = 3、friends = [[0, 1], [1, 2]] の場合、出力はTrueになります。その理由は以下の通りです。人0は人1と友人である人1は人0と人2の両方と友人である人2は人1と友人であるこのように全員が少なくとも1人の友人を持っているため、結果はTru

問題の概要すべての要素が正の整数である配列 nums があるとします。現在、私たちはインデックス 0 の位置にいます。配列の各要素は、その位置からジャンプできる最大距離を表しています。目標は、できるだけ少ないジャンプ回数で最後のインデックス(n-1)に到達することです。例えば、配列が [2,3,1,1,4] の場合、出力は 2 になります。これは、インデックス 0 からインデックス 1 へジャンプし、そこからインデックス 4(最後のインデックス)へジャンプすればよいためです。解決のための手順end := 0、jumps := 0、farthest := 0 で初期化するi を 0 から num

問題の概要0と1だけで構成される2次元のバイナリ行列が与えられ、その中に存在する「島」の数を求めるのがこの問題です。ここでは1を陸地、0を水とみなし、上下左右に隣接した1の集まり(斜め方向の隣接は考慮しない)で、周囲を水に囲まれた領域を1つの島としてカウントします。例として、次のような行列が入力された場合を考えてみましょう。101000010001100000001101111101この場合、島は4つ存在するため、出力は4となります。解き方のアプローチ(深さ優先探索：DFS)この問題は、グラフ探索アルゴリズムのひとつである深さ優先探索(DFS)を使うことで効率的に解けます。全体の流れは以下の通

問題の概要ある文字列 s が与えられたとき、その中に含まれる「回文」となっている部分文字列の個数を求めることを考えます。例えば、入力が s = level の場合、出力は 7 になります。これは、回文となっている部分文字列が [l, e, v, e, l, eve, level] の7つ存在するためです。解き方：中心から左右へ拡張する手法この問題は、各位置を回文の中心とみなし、左右の文字が一致する限り外側へ広げていく「中心拡張（Expand Around Center）」という手法で効率的に解くことができます。check_palindrome() 関数の手順関数 check_palindrom

文字列 s が与えられたとき、そのすべての回文部分文字列の長さが奇数であるかどうかを判定する必要があります。 例えば、入力が s = level の場合、出力は True になります。 解法のアプローチ この問題は、以下の手順で解くことができます。 インデックス 1 から文字列の長さまでの範囲で i をループします s[i] と s[i - 1] が同じ文字であれば、False を返します ループが最後まで完了すれば、True を返します なぜこの方法で正しく判定できるのか ポイントは、偶数長の回文は必ず中央に同じ文字が隣接して並ぶペアを含むという性質です。つまり、隣り合う2つの文字が

数値のリスト nums が与えられたとき、新しく生成するリストの各インデックス i の要素が、元のリストのうちインデックス i の要素以外のすべての数値の積となるようなリストを求めます。ただし、この問題は除算を使用せずに解く必要があります。例えば、入力が nums = [2, 3, 4, 5, 6] の場合、出力は [360, 240, 180, 144, 120] となります。解法のアプローチこの問題は、「左側からの累積積」と「右側からの累積積」の2つの配列を組み合わせることで、O(n) の時間計算量で効率的に解くことができます。以下の手順に従います。nums のサイズが 1 未満の場合は、

2つの文字列 S と T が与えられたとき、それらが「編集距離0（完全に一致）」または「編集距離1」の関係にあるかどうかを判定する問題を考えてみましょう。ここでいう編集操作とは、文字の削除、文字の追加、文字の置換の3種類を指します。例えば、S = hello、T = hallo の場合、1文字だけ異なるため編集距離は1となり、出力は True になります。一方、S = abc、T = xyz のように複数箇所の変更が必要な場合は False を返します。アルゴリズムの考え方この問題は、両方の文字列を先頭から同時に走査しながら、不一致が見つかった回数をカウントするというシンプルなアプローチで解け

問題の概要数値のリスト nums があるとします。このリストから任意の2つの数を選んで取り除き、その合計をリストの末尾に追加する操作を繰り返すことで、リストの長さを減らすことができます。この操作にかかるコストは、取り除いた2つの整数の合計です。ここで、nums を最終的に1つの整数にまで減らすときの合計コストの最小値を求めます。入力例と動作の確認例えば、nums = [2, 3, 4, 5, 6] の場合、出力は 45 になります。手順を順番に見てみましょう。まず 2 と 3 を取り除き、合計 5 を追加 → [4, 5, 6, 5](コスト 5)次に 4 と 5 を取り除き、合計 9 を追加

数値の2次元リスト intervals が与えられ、その各行は [start, end]（両端を含む）という区間を表しているものとします。区間 [a, b]（a < b）のサイズは (b - a) で定義されます。ここで、このリストに区間を1つだけ追加し、すべての区間をマージした結果がちょうど1つの連続した範囲になるようにしたいと考えます。このとき、追加する区間のサイズとしてあり得る最小値を求めるのが本記事の目的です。例として、入力が intervals = [[15, 20],[30, 50]] の場合を考えてみましょう。このとき出力は 10 になります。[20, 30] という区間を