Python

ハッピー数とは？ハッピー数（Happy Number）とは、任意の正の整数から始めて「その数を各桁の数字の2乗の和で置き換える」という操作を繰り返し行ったとき、最終的に1に到達する数のことです。1に到達できない場合、計算結果は同じ値のサイクルを永遠に繰り返します。そして、1に到達できた数だけがハッピー数とみなされます。具体例：19の場合例えば、数値19がハッピー数かどうかを確認してみましょう。この場合、結果はTrue（ハッピー数である）になります。実際の計算過程は以下の通りです。12 + 92 = 8282 + 22 = 6862 + 82 = 10012 + 02 + 02 = 1アルゴリズ

最小共通祖先（LCA）とは二分探索木（Binary Search Tree）が与えられたとき、指定された2つのノードの最小共通祖先（Lowest Common Ancestor：LCA）を求める問題を考えてみましょう。ノード p と q の LCA とは、「p と q の両方を子孫として持つノードの中で、最も深い位置にあるノード」のことです。例えば、次のような二分木があるとします。[6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]この木は以下のような構造になります。この場合、2 と 8 の LCA は 6 となります。6 は 2 と 8 の両方を子孫に持ち、それより

問題の概要 ある会社で、プロダクトマネージャーが新しい製品を開発するチームを率いているとします。最新バージョンが品質チェックに不合格となった場合、各バージョンは前のバージョンをベースに開発されているため、不良バージョン以降のすべてのバージョンも不良になると仮定できます。 そこで、n個の要素を持つ配列 A = [1, 2, …, n] が与えられたとき、この中から最初の不良バージョンを見つける必要があります。 ここでは、指定されたバージョンが不良かどうかを判定する関数 isBadVersion(version_id) が用意されているものとします。例えば、n = 5 でバージョン4が最初の不良バ

文字列内の母音を反転するとは小文字のみで構成された文字列が与えられたとき、その中に含まれる母音(a・e・i・o・u)だけを逆順に入れ替える問題を考えてみましょう。たとえば、文字列が「hello」の場合、母音は「e」と「o」なので、これらを反転すると結果は「holle」になります。同様に、「programming」の場合は「prigrammong」が出力されます。解決のための手順この問題は、次の手順に沿って解くことができます。文字列を走査し、母音の一覧を作成すると同時に、その出現位置(インデックス)も記録します収集した母音のリストを逆順に並べ替えますカウンター idx を 0 で初期化しますi

問題概要2つの配列 A と B が与えられたとき、これらの配列に共通して含まれる要素（交差・共通部分）を求めます。例えば、A = [1, 4, 5, 3, 6]、B = [2, 3, 5, 7, 9] の場合、両方の配列に存在する要素は 3 と 5 だけなので、結果は [3, 5] となります。この種の問題では重複の扱いがポイントになります。ある要素が両方の配列に複数回現れる場合は、その出現回数のうち少ない方の回数だけ結果に含める必要があります。解法のアプローチこの問題は、ハッシュマップ（Pythonでは辞書型 dict）を使って要素の出現頻度を管理することで、効率的に解くことができます。手順

二分木の直径とは二分木が与えられたとき、その木の直径(diameter)を計算することを考えます。二分木の直径とは、木の中の任意の2つのノードをつなぐ最長経路の長さのことです。重要なポイントとして、この経路は必ずしも根(ルート)を通るとは限りません。例えば、次のような木を考えてみましょう。この場合、経路 [4, 2, 1, 3] または [5, 2, 1, 3] の長さが3本の辺で構成されているため、直径は3となります。解法のアプローチこの問題はDFS(深さ優先探索)を使うことで効率的に解くことができます。手順は以下の通りです。DFSで各ノードを訪問しながら直径を求めます。まず答えを格納する変

問題の概要2n 個の整数からなる配列が与えられたとき、これらの整数を (a1, b1), (a2, b2), ..., (an, bn) のように n 組のペアに分组することを考えます。その際、各ペアの小さい方の値、つまり min(ai, bi) をすべて合計した値が最大になるようにペアを作る必要があります。例えば、入力が [1, 4, 3, 2] の場合、出力は 4 となります。このとき n = 2 であり、最適なペアの組み合わせは次のようになります。min(1, 2) + min(3, 4) = 1 + 3 = 4解法のアプローチこの問題は貪欲法（グリーディ法）で効率よく解くことができます

問題概要文字列 J は「宝石」とみなされる文字の集合を表し、もう一方の文字列 S は手元にある「石」を表しています。この課題では、S の中に宝石として扱える石がいくつ含まれているかを求めます。J と S に含まれる文字は大文字・小文字が区別される点に注意してください。たとえば、J = aZc、S = catTableZebraPicnic の場合、宝石に該当する文字は 7 個含まれています。解き方のアプローチこの問題を効率よく解くには、まず文字列 J を辞書（ハッシュマップ）に変換し、各文字をキーとして登録します。その後、文字列 S を先頭から順に走査し、各文字が辞書に存在するかどうかを確認し

文字列の回転マッチング問題とは2つの文字列 A と B が与えられたとき、文字列 A を回転させて、いずれかの時点で B と一致するかどうかを判定する問題を考えてみましょう。一致する回転位置が存在すれば True を返し、存在しなければ False を返します。例えば、A = abcde、B = cdeab の場合、A を2文字分回転させると cdeab になるため、答えは True となります。一方、B = acdeb のような場合はどれだけ回転しても一致しないため、False が返されます。解法のアプローチこの問題は「連結テクニック」を使うと効率的に解けます。基本的な考え方は以下の通りです

文字列（文）が与えられ、その中にはいくつかの単語が含まれています。各単語は小文字と大文字の英字で構成されています。この課題は、文をヤギラテン語（Goat Latin）形式に変換することです。ヤギラテン語はピッグラテン語（Pig Latin）に似た言語遊びの一種で、以下のようなルールに従って変換を行います。 単語が母音で始まる場合：単語の末尾に「ma」を付け加える 単語が子音で始まる場合：先頭の文字を取り除いて末尾に移動させ、その後に「ma」を付け加える 文の中での単語の位置（インデックス）に応じて、1番目の単語から順に「a」を1個、2番目の単語に2個というように、末尾へ追加していく 例え

この記事では、Pythonを使って「フェアキャンディスワップ（公平なキャンディ交換）」問題を解く方法を解説します。数式ベースのシンプルなアプローチとセット（集合）による高速な探索を組み合わせることで、効率よく答えを導き出します。 問題の概要 AさんとBさんは友人同士で、それぞれ異なるサイズのキャンディバーを持っています。ここで、A[i]はAさんが持っているi番目のキャンディバーのサイズ、B[j]はBさんが持っているj番目のキャンディバーのサイズを表します。 二人は友人なので、お互いにキャンディバーを1本ずつ交換し、交換後に両者の持つキャンディの総量（所有するキャンディバーのサイズの合計）が等し

問題の概要 いくつかの数値を含む配列 A が与えられたとします。この配列を、偶数が先頭に集まり、その後に奇数が続くように並べ替えます。 たとえば、配列が A = [1, 5, 6, 8, 7, 2, 3] の場合、期待される結果は [6, 8, 2, 1, 5, 7, 3] のようになります。 解法のアプローチ：2つのポインタを使う この問題は、いわゆる「2ポインタ法」と呼ばれるシンプルな手法で効率よく解けます。配列を一度だけ走査しながら、偶数を見つけるたびに配列の前方へ移動させていく考え方です。 具体的には、次の手順に従います。 インデックス i := 0 と j := 0 を初期化する

文字列 S が与えられたとき、英字（アルファベット）だけの位置を反転させ、記号や数字などの英字以外の文字は元の位置にそのまま残すという問題を考えてみましょう。 たとえば、入力文字列が a-bC-dEf-ghIj の場合、出力は j-Ih-gfE-dCba となります。ハイフン「-」の位置は変わらず、英字部分だけが逆順に入れ替わっているのがポイントです。 解決のアプローチ この問題は、いわゆる2ポインタ法（two-pointer technique）を使うことで効率的に解けます。先頭から走査するインデックスと、末尾から走査するインデックスの2つを用意し、両側の文字がどちらも英字であれば入れ替える

整数の配列 A と、クエリを格納した配列 queries があるとします。i番目のクエリでは、value = queries[i][0]、index = queries[i][1] となり、A[index] に value を加算します。そして、i番目のクエリに対する答えは、更新後の配列 A に含まれる偶数の合計値です。すべてのクエリに対する答えを順番に求め、それらを配列として返すのがこの問題の目的です。問題の例例として、配列が [1,2,3,4]、クエリ配列が [[1,0],[-3,1],[-4,0],[2,3]] の場合を考えてみましょう。このとき、答えの配列は [8,6,2,4] になり

ある整数が配列（リスト）形式で与えられている状況を考えてみましょう。例えば、数値が534の場合、[5, 3, 4] のように各桁が要素として格納されています。この配列形式の数値に対して、別の値 k を加算し、結果も同様に桁ごとの配列として返すのが課題です。解法のアプローチこの問題は、以下の手順で解くことができます。配列内の各桁を文字列に変換し、それらを連結して1つの文字列を作る連結した文字列を整数に変換し、k を加算する計算結果を再び文字列に変換し、各桁を取り出して配列（リスト）を作成する実装例以下のコードは、上記の手順を実装したものです。動作をより深く理解するために参考にしてください。cla

この記事では、10進数で与えられた整数に対して、その2進表現における補数（ビット反転）を求め、再び10進数に変換して返す方法を解説します。 例として、数値が 20 の場合を考えてみましょう。20の2進表現は 10100 です。これをビットごとに反転すると 01011 となり、これを10進数に戻すと 11 になります。これが求める答えです。 解法のアプローチ この問題は、以下の手順で解くことができます。 s を数値 n の2進表現の文字列とします（Pythonの bin() 関数を使うと「0b」プレフィックス付きの文字列が得られます）。 sum = 0、num = 1 で初期化します。 文字列

曲のリストが与えられ、i番目の曲の再生時間は time[i] 秒であるとします。このとき、2曲の合計時間（秒）が60で割り切れるようなペアの総数を求めるのが本記事のテーマです。問題の例たとえば、time配列が [30, 20, 150, 100, 40] の場合、答えは 3 となります。条件を満たすペアは次の3つです。(30, 150) → 合計180秒(20, 100) → 合計120秒(20, 40) → 合計60秒いずれも合計時間が60で割り切れることが確認できます。解法のアプローチすべてのペアを総当たりで調べると計算量がO(n²)となり非効率です。そこで、各曲の「60で割った余り」をハ

問題の概要整数の配列 A が与えられたとき、その配列を合計が等しい3つの空でない部分に分割できる場合にのみ true を返す問題を考えます。形式的には、i + 1 < j を満たすインデックス i, j が存在し、次の3つの区間の合計がすべて等しくなるとき、配列は分割可能とみなせます。第1部分:A[0] + A[1] + ... + A[i]第2部分:A[i+1] + A[i+2] + ... + A[j-1]第3部分:A[j] + A[j+1] + ... + A[len(A)-1]たとえば、入力が [0,2,1,-6,6,-7,9,1,2,0,1] の場合、出力は true になりま

問題の概要 それぞれ正の整数の重さを持つ石がいくつか与えられます。毎ターン、最も重い2つの石を選んで砕きます。2つの石の重さを x、y(x ≤ y)とすると、砕いた結果は次の2通りのいずれかになります。 x = y の場合: 2つの石はともに完全に破壊されます。 x ≠ y の場合: 重さ x の石は完全に破壊され、重さ y の石は新しい重さ y − x となります。 この操作を繰り返すと、最後には最大で1個の石が残ります。残った石の重さを求めてください(石が1個も残らない場合は 0 を返します)。 具体例 例として、石の重さが [2, 7, 4, 1, 8, 1] の場合を考えてみまし

問題の概要 小文字のみで構成された文字列 S が与えられたとします。この文字列に対して「重複削除操作」を行います。これは、隣り合っていて等しい2つの文字を選び、それらを削除するというものです。 この操作を繰り返し適用し、文字列 S に隣接する重複がなくなるまで削除を続けます。そして、すべての重複削除が完了した後の文字列を返します。なお、答えは一意であることが保証されています。 具体例 例えば、文字列が「abbacaca」の場合、答えは「caca」となります。処理の流れを見てみましょう。 まず「bb」を削除すると、文字列は「aacaca」になります 次に先頭の「aa」を削除すると、文字列は「