Python

文字列 s が与えられたとき、その文字列を「すべての部分が回文になるように」分割する方法が何通りあるかを求める問題について解説します。回文とは、前から読んでも後ろから読んでも同じになる文字列のことです。例えば「x」「yy」「xyyx」などはいずれも回文です。問題の例入力が s = xyyx の場合、出力は 3 になります。これは以下の3通りの分割方法が存在するためです。[x, yy, x][x, y, y, x][xyyx]解法のアプローチ(動的計画法)この問題は動的計画法(DP)を使って効率的に解くことができます。ここでは、table[i] を「文字列の先頭から i 文字目までを回文に分割す

問題の概要 数値のリスト nums が与えられたとします。このリストは複数の部分リスト(サブリスト)に分割でき、それぞれの部分を個別にソートすることが可能です。ここで求めたいのは、分割・ソートを行った後にリスト全体がソート済みの状態になるような、部分リスト数の最大値です。 例えば、入力が nums = [4, 3, 2, 1, 7, 5] の場合、答えは 2 になります。[4, 3, 2, 1] と [7, 5] の2つの部分リストに分割し、それぞれをソートすれば [1, 2, 3, 4, 5, 7] という完全にソートされたリストが得られるためです。 解法の考え方:累積和による分割境界の検

問題概要数値のリスト nums と整数 k が与えられたとき、リストをペアに分割し、それぞれのペアの合計が k で割り切れるかどうかを判定するプログラムを作成します。例えば、nums = [4, 7, 2, 5]、k = 6 の場合を見てみましょう。(4, 2) と (7, 5) というペアに分割すると、合計はそれぞれ 6 と 12 となり、どちらも 6 で割り切れます。したがって、この場合の出力は True になります。解法のアプローチこの問題は、各数値を k で割った余り(剰余)に着目することで、効率的に解くことができます。手順は以下の通りです。リストの要素数が奇数の場合、ペアが作れないた

監獄には8つの独房が一列に並んでおり、それぞれの状態はリスト内の0と1で表されます。1は入居中(占有)、0は空室を意味します。毎日、次のルールに従って独房の状態が更新されます。ある独房の両隣の状態が同じ(両方とも占有、または両方とも空室)であれば、その独房は翌日占有になります。それ以外の場合は空室になります。両端の独房には隣接する独房が1つしかないため、常に空室になります。この記事では、k日後の独房の状態を効率的に求めるPythonプログラムを解説します。問題の例たとえば、初期状態が nums = [1, 0, 1, 0, 0, 0, 0, 0] で k = 1 の場合、出力は [0, 1,

問題の概要4つの数値リスト A、B、C、D とターゲット値が与えられたとき、A[i] + B[j] + C[k] + D[l] がターゲットと等しくなるような異なる組（i, j, k, l）の個数を求めることを考えます。例えば、入力が以下のような場合を想定します。A = [5, 4, 3]B = [8, 4]C = [6, 2]D = [4, 10]target = 23このとき出力は 3 となり、条件を満たす組は [5, 8, 6, 4]、[3, 4, 6, 10]、[3, 8, 2, 10] の3つです。解法のアプローチすべての組み合わせを総当たりで調べると計算量が O(n⁴) となり、リ

問題の概要ここに2次元のマトリックス（リスト）があります。各行は [height, count] という2つの値を持っており、height はその人の身長、count は「その人の前方にいる、身長が自分と同じかそれ以上の人の数」を表します。このキューがシャッフルされてしまったとき、元の並び順を復元するのが今回の課題です。たとえば、入力が次のような場合を考えてみましょう。224050このとき、期待される出力は次のとおりです。405022結果を見ると、身長4と5の人は前方に自分以上の背の人がいないため先頭側に配置され、身長2の人の前には身長4と5の2人が立っているため、3番目に配置されていることが

グレイコードとは？ グレイコード（Gray Code）とは、隣り合う数値同士のビット表現が必ず「ちょうど1ビットだけ」異なるように並べた、二進数の順序付け方式です。デジタル回路やエンコーダなど、誤読を防ぎたい場面で活用されていることで知られています。 グレイコードの一例は次の通りです。[0, 1, 11, 10, 110, 111, …] 問題の定義 ある数 n が与えられたとき、n 番目のグレイコードを求めることを考えます。 例： 入力が n = 12 の場合、出力は 10 になります。これは、12 を二進数で表すと (1100) であり、それに対応するグレイコードは (1010)、その十

文字列 s と整数 k が与えられたとき、「同じ文字が k 個連続している部分」を繰り返し削除していき、最終的に残る文字列を求める問題を考えます。 例えば、入力が s = paaappmmmma、k = 3 の場合、出力は ma になります。処理の流れは以下のとおりです。 まず連続する3つの a を削除 → pppmmmma 次に連続する3つの p を削除 → mmmma 最後に4つある m のうち連続する3つを削除 → ma 解き方のアプローチ この問題は、次の手順で解くことができます。 以下の処理を、変更がなくなるまで繰り返します。 count を 0 で初期化する s に含まれる

数値のリスト target が与えられたとします。ここで、与えられたリストと同じ長さを持ち、すべての要素が 1 で埋められたリスト X を考えます。次の操作を何度でも実行できます。 操作： X の任意のインデックス i を選び、X[i] を X の現在の合計値で置き換える。 この操作を繰り返した結果、X を target に変換できるかどうかを判定するのが本記事の目的です。 例えば、入力が target = [5, 9, 3] の場合、出力は True になります。その理由を見てみましょう。 初期状態：X = [1, 1, 1] 合計値 3 で更新 → [1, 1, 3] 合計値 5 で更新

三項式（条件演算式）を含む文字列が与えられたとき、その評価結果を求める問題を考えます。式には真偽値を表す「T」（True）と「F」（False）、および条件を示す「?」と「:」の記号が使用されます。この問題には以下のような性質があります。 与えられる文字列の長さは10,000以下である。 条件式は右から左へ向かってグループ化される。 条件部分は必ず「T」または「F」であり、数字が現れることはない。 式の評価結果は常に「T」または「F」のいずれかになる。 たとえば、入力が「T ? T ? F : T : T」であれば、出力は「F」となります。 解法のアプローチ この問題は、スタックを使って文

問題の概要連結リストと2つの値 i・j が与えられたとき、i 番目から j 番目までのノードを逆順に並べ替え、更新後のリストを返すことを考えます。例えば、入力が [1,2,3,4,5,6,7,8,9]、i = 2、j = 6 の場合、出力は次のようになります。[1, 2, 7, 6, 5, 4, 3, 8, 9]アルゴリズムの手順この問題は、以下の手順で解くことができます。値が None のダミーノード prev_head を作成し、先頭ノードを指させます。prev を prev_head に、curr を先頭ノードに設定します。i 回だけループし、prev と curr を1つずつ前へ進めま

問題の概要 文字列と区切り文字(デリミタ)のリストが与えられたとします。このとき、区切り文字同士の相対的な順序はそのまま維持しながら、文字列内の単語だけを逆順に並べ替えるプログラムを作成します。 例えば、入力が以下の場合を考えてみましょう。 s = Computer/Network:Internet|tutorialspoint delims = [/, :, |] この場合、期待される出力は次のようになります。 tutorialspoint/Internet:Network|Computer 解決のアプローチ この問題は、以下の手順で解くことができます。 単語を格納するための新しいリ

はじめに2つの二分木が与えられたとき、それぞれの木を左から右へたどったときの葉ノードの並び（シーケンス）が一致しているかどうかを判定する問題を考えてみましょう。例えば、次のような2つの木が入力として与えられた場合を想定します。この場合、どちらの木も葉の並びは [2, 6] となるため、出力は True になります。解決のアプローチこの問題を解くためには、以下の手順に従います。結果を格納するための新しいリスト c を用意します。inorder() 関数を定義します。この関数はルートノードとリスト c を引数に取ります。c が null の場合は、新しい空のリストを作成します。ルートノードが nu

数値のリスト nums が与えられ、各要素は対応するタスクを完了するのにかかる時間（単位時間）を表しています。このとき、連続しないタスクに限りスキップすることが許されます。ここでの目的は、すべてのタスクを完了するまでにかかる合計時間の最小値を求めることです。例えば、入力が nums = [11, 6, 8, 16] の場合を考えてみましょう。この場合、最初と最後のタスクをスキップできるため、出力は 14 となります。解法のアプローチ：動的計画法（DP）この問題は動的計画法を使って効率的に解くことができます。各タスクについて「そのタスクをスキップした場合」と「実行した場合」の2つの状態を管理し、

問題の概要二分木が与えられたとき、2番目に深い葉ノードの深さを求めることを考えます。最も深い葉が複数存在する場合は、その次に高い位置にある葉ノードが「2番目に深い葉」とみなされます。なお、根（ルート）の深さは0であるとします。入力例と出力例えば、次のような二分木が与えられた場合を考えてみましょう。この木では、最も深い葉はノード7とノード8（深さ3）であり、その次に深い葉はノード3（深さ1）です。したがって、出力は 1 となります。解法のアプローチこの問題は、木をレベル（深さ）ごとに順番に辿っていく幅優先探索（BFS）の考え方を使うと、シンプルに解くことができます。各レベルで最初に見つかった葉ノ

問題の概要 数値のリスト items と整数値 n が与えられます。営業担当者は、さまざまなIDを持つ商品をカバンに入れて所持しており、カバンの中から最大で n 個の商品を販売(削除)することができます。このとき、n 個の商品を販売し終えた後にカバンへ残る「異なるIDの種類数」の最小値を求めるのが課題です。 入力例と出力例 たとえば、items = [2, 2, 6, 6]、n = 2 の場合を考えてみましょう。このとき出力は 1 になります。同じIDを持つ商品(ID 2 または ID 6)を2つまとめて販売すれば、残る商品のIDが1種類だけで済むためです。 解決のためのアプローチ この問題を

問題の概要 連結リスト（リンクリスト）が与えられたとき、そのリストを昇順に並べ替えることを考えます。 例えば、入力が [5, 8, 4, 1, 5, 6, 3] の場合、出力は [1, 3, 4, 5, 5, 6, 8] となります。 解決のアプローチ この問題は、以下の手順で解くことができます。 新しい空のリスト values を用意します。 head に先頭ノードへの参照を保存しておきます。 node が null でない間、次の処理を繰り返します。 node の値を values の末尾に追加します。 node を次のノードに進めます。 values を昇順にソートします。 v

プログラミングの定番問題のひとつに、「2次元行列（マトリクス）の要素を螺旋状（スパイラル順）に出力する」というものがあります。本記事では、Pythonを使ってこの問題を解くためのアルゴリズムの考え方と実装例を、初心者の方にもわかりやすく解説します。スパイラル順の出力とは？2次元行列 mat が与えられたとき、その要素を渦を巻くようにたどりながら出力します。具体的には、まず最初の行（mat[0][0]から）を左から右へすべて出力し、続いて最右列を上から下へ、次に最下行を右から左へ、さらに最左列を下から上へと訪問します。これを内側に向かって繰り返すことで、行列全体を一筆書きのように走査できます。入

4つの整数リスト A、B、C、D とターゲット値(target)が与えられたとき、A[i] + B[j] + C[k] + D[l] ≤ target を満たすようなインデックスの組み合わせ (i, j, k, l) の総数を求める問題です。たとえば、入力が A = [3, 2]、B = [5, 3]、C = [1]、D = [2, 3]、target = 9 の場合、出力は 3 になります。条件を満たす組み合わせとしては、[3, 3, 1, 2]、[3, 3, 1, 2]、[2, 3, 1, 3] の3通りが挙げられます。解法のアプローチ4つのリストすべての組み合わせを素朴に全列挙すると計算

数値のリスト nums があるとします。これは正方形のブロックを横一列に並べたときの、各列の高さを表しています。ここで、このブロック形状が直線 y = x に対して対称であるかどうかを判定する必要があります。 たとえば、入力が nums = [7, 5, 3, 2, 2, 1, 1] の場合、出力は True になります。 解き方のアプローチ この問題は、リストの両端から同時に走査していくことで効率的に判定できます。手順は次のとおりです。 i を 0、j を「リストの長さ - 1」で初期化します。 i <= j である間、次の処理を繰り返します。 h := nums[j](右側の