Python

整数が与えられたとき、それが回文数（パリンドローム）であるかどうかを判定する方法を解説します。回文数とは、前から読んでも後ろから読んでも同じ並びになる数値のことです。例えば「454」は逆順にしても「454」となるため回文数です。一方、「-565」を逆順にすると「565-」となり、マイナス記号の位置が変わるため元の数と一致せず、回文数にはなりません。解法の考え方この問題は非常にシンプルに解けます。手順は以下の通りです。1. 数値をstr()で文字列に変換する2. Pythonのスライス記法[::-1]を使って文字列を反転させる3. 元の文字列と反転した文字列を比較し、一致すればTrue、一致しな

ローマ数字とはローマ数字は、以下のような記号を使って数値を表現します。記号値I1V5X10L50C100D500M1000ローマ数字の基本的なルールローマ数字の読み方を詳しく見てみましょう。たとえば「II」は2を表します。これは「I」が2つ足し合わされているためです。「XII」であれば X + II = 10 + 2 = 12 となります。しかし、4は「IIII」ではなく「IV」と表記されます。ここが少し注意が必要なポイントです。ローマ数字には減算則と呼ばれる特別なルールがあります。「I」は「V(5)」や「X(10)」の前に置かれると、それぞれ 4 と 9 を表します（IV = 4、IX =

配列に複数の文字列が格納されている場合、それらの文字列に共通する最長共通プレフィックス（Longest Common Prefix）を見つける必要があります。ここでは、すべての文字列が小文字であると仮定します。また、共通のプレフィックスが存在しない場合は空文字列 を返すものとします。 例えば、文字列の配列が [school, schedule, scotland] のような場合、すべての文字列に共通して含まれているのは sc であるため、最長共通プレフィックスは sc となります。 解決のアプローチ この問題を解くためには、以下の手順で処理を進めます。 最初の文字列を基準（current）

2つのソート済み（昇順に並べ替えられた）リストAとBがあるとします。これらをマージして、1つのソート済みリストCを作成することを目標とします。なお、2つのリストのサイズは同じである必要はありません。例えば、A = [1, 2, 4, 7]、B = [1, 3, 4, 5, 6, 8] の場合、マージ後のリストCは [1, 1, 2, 3, 4, 4, 5, 6, 7, 8] となります。アルゴリズムの考え方この問題は再帰を使うことでシンプルに解くことができます。merge() 関数の動作は以下のようになります。関数 merge() にリストAとBを渡すAが空ならBを返し、Bが空ならAを返す（ベ

ここでは、ソート済みのリストから重複する要素をすべて削除し、その後の配列の長さ（ユニークな要素の個数）を返す問題を扱います。重要な制約として、O(1)の追加メモリで実行する必要があります。つまり、新しい配列を作成せずに、元の配列をインプレース（in-place）で操作しなければなりません。問題の例例えば、次のような入力が与えられたとします。A = [1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5, 6]この場合、重複を除いたユニークな要素は「1, 2, 3, 4, 5, 6」の6つなので、出力は 6 となります。解法のアプローチこの問題は、以下の手順で解くことができ

問題概要2つの文字列 str（対象文字列）と sub_str（検索する部分文字列）が与えられたとします。このとき、str の中で sub_str が最初に出現する位置（インデックス）を見つける必要があります。例えば、str が「helloworld」で、sub_str が「lo」である場合、出力は 3 となります。C言語では標準ライブラリの strstr() 関数を使うことで同様の処理を行えますが、ここでは strstr() と同じ動作をする関数をPythonで独自に実装していきます。アルゴリズムの手順この問題は、以下の手順で解くことができます。i := 0、j := 0 で初期化し、m を

この記事では、有名な文字列処理のアルゴリズム問題である「Count and Say（数えて言う）」数列について、その仕組みとPythonでの実装方法を詳しく解説します。 Count and Say 数列とは？ Count and Say 数列は、直前の項を「読み上げる」ことで次の項を生成していく特殊な数列です。最初のいくつかの項は以下のようになります。 1 11 21 1211 111221 数列の生成ルール この数列は、前の項を「数字を数えながら声に出して読む」というルールに従って作られます。具体的には以下の通りです。 1（イチ）→ 最初の項は単に「1」 11（1が1つ）→ 前の項

最大部分配列問題とは 整数配列 A が与えられたとき、長さが 1 以上の連続する部分配列の中で、要素の合計が最大になるものを見つけ、その合計値を返すことを考えます。 例えば、配列 A = [-2, 1, -3, 4, -1, 2, 1, -5, 4] の場合、最大の合計は 6 となり、これは部分配列 [4, -1, 2, 1] の合計に相当します。 解き方：動的計画法（DP） この問題は、動的計画法（Dynamic Programming）を使うことで効率的に解くことができます。手順は以下の通りです。 配列 A と同じサイズの配列 dp を定義し、0 で初期化する dp[0] := A[0]

整数の配列 A があるとします。A は n 個の非負の整数を要素として持ち、配列全体で1つの大きな数を表しています。例えば、A = [5, 3, 2, 4] が与えられた場合、これは数値 5324 を意味します。この配列 A を受け取り、その数に 1 を加算した結果を、同じく配列形式で返す必要があります。つまり、加算後の A は [5, 3, 2, 5] となるわけです。 解決のための手順 この問題は、以下の手順で解くことができます。 配列の各要素を文字列に変換しながら連結し、1つの文字列を作成する その文字列を整数型に変換し、1 を加算する 加算結果を桁ごとに分割し、新しい配列として組み立

非負の整数 x が与えられたとき、標準ライブラリの関数を使わずに x の平方根を求めることを考えます。つまり、sqrt(x) を計算する独自の関数を実装する必要があります。この関数では、結果の小数点以下は切り捨て、整数部分のみを返します。 例を挙げると、x = 4 の場合は答えは 2 です。x = 8 の場合も答えは 2 になります。なぜなら sqrt(8) ≈ 2.82842 ですが、整数部分だけを取り出すためです。 アルゴリズムの考え方：二分探索 この問題は二分探索（バイナリサーチ）を使うと効率的に解けます。平方根の候補となる範囲を半分ずつ絞り込んでいくことで、高速に答えを求められます。

問題の概要2つのソート済み配列AとBが与えられたとき、それらをマージして1つのソート済み配列Cを作成することを考えます。なお、両者のサイズは異なっていても構いません。例えば、A = [1,2,4,7]、B = [1,3,4,5,6,8] の場合、マージ後のリストCは [1,1,2,3,4,4,5,6,7,8] となります。アルゴリズムの手順この問題を解くには、以下の手順に従います。i := 0、j := 0、end := Aの長さ − 1 を定義しますend >= 0 かつ A[end] が空(0)である間、end を 1 ずつ減らしていきますj が Bの長さ未満である間、以下の処理を繰

本記事では、Pythonを使って二分木が対称（シンメトリック）であるかどうかを判定するアルゴリズムを解説します。対称な二分木とは？ある二分木について、鏡像（左右反転した像）をとったときに元の木と完全に一致する場合、その木は「対称な木」であると定義されます。例えば、次のような2つの木を考えてみましょう。1つ目の木：左部分木と右部分木が鏡像の関係になっている → 対称2つ目の木：一部のノード配置が左右で異なる → 非対称解法のアプローチこの問題は、再帰（recursion）を使うことでエレガントに解くことができます。基本的な考え方は、「根の左側と右側を同時にたどり、互いに鏡像の関係にあるかを確認す

Pythonで二分木の最大深度を求める二分木が与えられたとき、その最大深度を求める問題を考えます。木の最大深度とは、根（ルート）から葉ノードまでの最も長い経路をたどったときに通過するノード数のことです。例えば、下図のような二分木の場合、最大深度は 3 となります。解法のアプローチこの問題は再帰を使うことで、非常にシンプルに解くことができます。手順は以下のとおりです。再帰用のヘルパーメソッド solve(root, depth=0) を定義します。root が空（None）の場合は、そこまでの深さ depth をそのまま返します。それ以外の場合は、左部分木に対する solve(left, dep

ソートされた配列 A が与えられたとき、そこから高さバランスの取れた二分探索木(BST)を生成することを考えます。ここで「高さバランスの取れた二分木」とは、すべてのノードにおいて、左右の部分木の深さの差が常に1以下であるような二分木のことを指します。例として、配列が [-10, -3, 0, 5, 9] の場合、出力の一例は [0, -3, 9, -10, null, 5] のようになります。解法のアプローチこの問題は、配列の中央要素をルートに選ぶというシンプルな発想で解くことができます。具体的な手順は以下の通りです。配列 A が空の場合は、Null(None)を返します。配列の中央の要素を見

パス合計問題とは二分木と目標の合計値が与えられたとき、根から葉までの経路をたどった際のノード値の合計が、与えられた値と一致するような経路が存在するかどうかを判定します。例として、木が [0, -3, 9, -10, null, 5] という構成で、合計値が 14 の場合を考えてみましょう。このとき、0 → 9 → 5 という経路が存在し、その合計はちょうど 14 になるため、答えは True となります。解法のアプローチこの問題は再帰を使うことで簡潔に解くことができます。手順は以下の通りです。根ノードが null（空）の場合、False を返します。左右の子ノードが両方とも空（つまり葉ノード）

問題概要ある配列 A が与えられ、A[i] は i 日目における特定の銘柄の株価を表しているものとします。このとき、得られる最大の利益を求めるのが目的です。取引（株の購入と売却の一連の操作）は最大でも1回しか行えません。また、複数の取引を同時に抱えることはできないため、新しい株を購入する前に、必ず現在保有している株を売却しておかなければならない点にも注意が必要です。例として、配列が A = [7, 1, 5, 3, 6, 4] の場合を考えてみましょう。このとき答えは 5 となります。2日目（インデックス1）に株価 1 で株を買い、5日目に株価 6 で売却すれば、利益は 6 − 1 = 5 と

問題概要 配列Aが与えられ、A[i] は i 日目の株価を表すものとします。このとき、達成できる最大の利益を求めます。取引（株の買いと売り）は何度でも行えますが、同時に複数の取引を持つことはできません。つまり、新しい株を購入する前に、必ず保有中の株を売却しておく必要があります。 具体例 例えば、配列が A = [7, 1, 5, 3, 6, 4] の場合、答えは 7 になります。 2日目（インデックス1）に株価 1 で購入し、3日目に株価 5 で売却すると、利益は 5 − 1 = 4。続いて、4日目に株価 3 で再び購入し、5日目に株価 6 で売却すると、利益は 6 − 3 = 3 となりま

問題の概要 英数字や記号が混在した文字列を考えます。文字列には小文字と大文字の両方が含まれています。ここでは、小文字のみを対象とし（大文字はすべて小文字に変換）、カンマやスペースなどの記号は無視して、その文字列が回文（前から読んでも後ろから読んでも同じ並び）になっているかどうかを判定します。 たとえば、文字列が A Man, a Plan, a Canal: Panama の場合、これらのルールを適用すると amanaplanacanalpanama となります。これは回文です。 解き方の手順 空文字列 x = を定義する 文字列 str 内の各文字 c を順番に読み取る c が小文字

配列Aの中に、2回ずつ出現する数値がたくさん含まれているとします。その中で、たった1つだけ1回しか出現しない要素があります。この要素を配列から見つけ出すのが課題です。例えば、A = [1, 1, 5, 3, 2, 5, 2] の場合、出力は 3 になります。すべての数値が2回ずつ現れるため、XOR(排他的論理和)を使うことで、ペアになる要素を打ち消し合って残りの一意な要素を導き出せます。これは、同じ数値同士のXORが必ず0になるという性質(y XOR y = 0)を利用したテクニックです。さらに、XORには交換法則と結合法則が成り立つため、要素の出現順序に関係なく、同じ数値同士は必ずペアとして

配列の右回転とは？ 配列Aが与えられたとき、それを右にkステップ回転することを考えます。例えば、配列 A = [5, 7, 3, 6, 8, 1, 5, 4]、k = 3 の場合、出力は [1, 5, 4, 5, 7, 3, 6, 8] となります。 各ステップでの配列の変化は以下の通りです。 1回転後：[4, 5, 7, 3, 6, 8, 1, 5] 2回転後：[5, 4, 5, 7, 3, 6, 8, 1] 3回転後：[1, 5, 4, 5, 7, 3, 6, 8] つまり、1回転ごとに末尾の要素が先頭に移動し、残りの要素が一つずつ後ろにずれていくイメージです。 解法のアプローチ こ