C++

2つの単語 S と T が与えられたとき、S を T に変換するために必要な最小の編集回数を求める問題を考えてみましょう。ここで使える操作は次の3種類です。1文字を挿入する1文字を削除する1文字を置換するこの「最小編集距離」は、レーベンシュタイン距離とも呼ばれ、スペルチェッカや差分検出ツール、DNA配列の比較など、さまざまな分野で応用されている有名なアルゴリズムです。たとえば、入力文字列が evaluate と fluctuate の場合、答えは 5 になります。解き方のアプローチ：動的計画法（DP）この問題は、動的計画法（Dynamic Programming）を使うことで効率的に解けます。

問題概要昇順にソートされた配列が、私たちには未知のあるピボット位置で回転されていると仮定します。この回転配列の中から最大値を見つける必要があります。例えば、配列が [3,4,5,1,2] の場合、出力は 5 となります。解法のアプローチこの問題は二分探索（バイナリサーチ）を応用することで効率的に解けます。先頭から順に調べる線形探索では O(n) の計算量が必要ですが、二分探索を活用すれば O(log n) まで計算量を抑えることができます。具体的な手順は以下の通りです。low := 0、high := 配列の最後のインデックス、n := 配列のサイズ、ans := 0 として初期化するlow

問題概要 同じ長さの文字列リスト genes があるとします。各要素は A、C、G、T のいずれかの文字のみで構成されており、次のルールが成り立ちます。 2つの文字列 s1 と s2 がちょうど1文字だけ異なる場合、s1 と s2 は同じ突然変異グループに属します。 s1 と s2 が同じグループに属し、s2 と s3 が同じグループに属するならば、s1 と s3 も同じグループに属します(推移性)。 このとき、生成できる突然変異グループの総数を求めるのが目的です。 具体例 たとえば、入力が genes = [ACGT, ACGC, ACTT, TTTT, TGTT] の場合、出力は 2

C++で二分木の高さバランスを判定する方法 二分木が与えられたとき、その木が「高さバランス」されているかどうかを判定する必要があります。 高さバランスされた木とは、すべてのノードにおいて、左部分木の高さと右部分木の高さの絶対差が0または1以内に収まっている木のことです。 例えば、以下のような二分木が入力として与えられたとします。 この場合、出力は True(バランスされている)となります。 解決のアプローチ この問題を解くには、DFS(深さ優先探索)を利用して各ノードの部分木の高さを計算し、その差を確認します。手順は以下の通りです。 dfs() 関数を定義し、ノードを引数として受け取ります

ある整数 n が与えられたとき、その2進表現の中で最も長く連続して現れる「1」の列の長さを求めることを考えます。例えば、入力が n = 312 の場合を考えてみましょう。312 を2進数で表すと 100111000 となり、ここには「1」が3つ連続した部分が存在するため、出力は 3 となります。解法のアプローチこの問題は、ビット演算を使って各ビットを順番に調べていくことで効率的に解くことができます。具体的な手順は以下の通りです。結果を格納する変数 ret と、現在の連続カウントを格納する変数 len をそれぞれ 0 で初期化します。i を 0 から 31 まで（32ビット分）ループさせます。各

C++で二分木の左側ビューを求める方法 二分木が与えられたとき、その木を左側から見ると、一部のノードだけが目に入ります。本記事では、このようにして見えるノードの一覧（左側ビュー）を取得・表示するプログラムをC++で実装する方法を解説します。 例えば、次のような二分木を考えてみましょう。 この木を左側から見ると、ルートの 1、次の階層の 2、さらにその下の 5 が見えます。したがって、出力は [1, 2, 5] となります。 解法のアプローチ：DFS（深さ優先探索） この問題は、深さ優先探索（DFS）を用いることで効率的に解けます。ポイントは、常に左側の子ノードから先に探索することです。こう

二分木が与えられたとき、それをレベル順（幅優先順）で走査することを考えます。例えば、次のような二分木があるとしましょう。この場合、レベル順走査による訪問順序は [1, 2, 3, 5, 4] となります。上から順に、同じ深さのノードは左から右へと処理していくイメージです。アルゴリズムの考え方レベル順走査を実現するには、キュー（FIFO：先入れ先出し） を利用するのが定番のアプローチです。手順は以下の通りです。ノードを格納するためのキューを用意するルートノードをキューに挿入するキューが空になるまで、以下の処理を繰り返すキューの先頭にあるノードを参照するそのノードの値を出力（または結果リストに記録

二分木（バイナリツリー）を考えます。根（ルート）のレベルを1とし、その子のレベルを2、さらにその下のレベルを3というように定義します。このとき、レベルXに存在するすべてのノードの値の合計が最小になるような、最も小さいレベルXを見つけるのが本記事の目的です。例として、次のような二分木を考えてみましょう。この場合、出力は 2 となります。なぜなら、レベル2のノードの値の合計は 4 + (-10) = -6 となり、これが全レベルの中で最小だからです。解法のアプローチこの問題は、幅優先探索（BFS）を使って各レベルごとにノードの値の合計を計算し、その中で最小となるレベルを記録していくことで解けます。

問題概要数値のリスト nums と整数 k が与えられたとします。このとき、「リストを、それぞれがちょうど k 個の連続的に増加する値を含むサブリストに分割できるかどうか」を判定するのが本記事のテーマです。たとえば、入力が nums = [4, 3, 2, 4, 5, 6]、k = 3 の場合、出力は True になります。リストを [2, 3, 4] と [4, 5, 6] に分割でき、どちらのサブリストも3つの要素を持ち、値が1ずつ増加しているためです。解法の考え方この問題は、各数値の出現回数をマップ(連想配列)で管理し、貪欲法でグループを組み立てることで解けます。ポイントは、「自分より1

数値のリストが与えられたとき、その中から「最長ビトニック部分列(バイトニックサブシーケンス)」の長さを求める問題を考えてみましょう。 ビトニック列とは、まず厳密に増加し、その後に厳密に減少するような数列のことです。なお、厳密に増加のみの数列や、厳密に減少のみの数列についても、ビトニック列として扱われます。 例えば、入力が nums = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15](要素数16)である場合、出力は 7 になります。 解法のアプローチ この問題は動的計画法(DP)を用いて効率的に解くことができます。基本的な手順は以下の

2つの文字列 text1 と text2 が与えられたとき、それらの最長共通部分列（Longest Common Subsequence：LCS）の長さを求めることを考えます。まず用語を整理しましょう。文字列の部分列（subsequence）とは、元の文字列からいくつかの文字を削除して作られる新しい文字列のことであり、残った文字の相対的な順序は変わりません。例えば「abe」は「abcde」の部分列ですが、「adc」は順序が崩れるため部分列ではありません。そして共通部分列とは、2つの文字列のどちらにも現れる部分列のことです。共通部分列が存在しない場合は 0 を返します。例えば入力が「abcde」

2つの小文字からなる文字列 X と Y が与えられたとき、両方の文字列に共通して現れる部分文字列の中で最も長いもの（最長共通部分文字列）の長さを求めます。例えば、X = helloworld、Y = worldbook という入力の場合、最も長い共通部分文字列は world であり、その長さは 5 となるため、出力は 5 になります。この問題は動的計画法（DP）を使うことで効率的に解くことができます。各位置で文字が一致した場合に、左上のセルの値に1を加えていくことで、連続する一致の長さを記録していきます。アルゴリズムの手順(m+1) × (n+1) のサイズを持つ2次元配列 longest を

2つの二分木が与えられ、一方の木をもう一方の木の上に重ね合わせることを考えてみましょう。このとき、両方の木の一部のノードは互いに重なり合い、それ以外のノードは重ならずに残ります。本記事では、こうした2つの木を1つの新しい二分木へとマージする方法を解説します。マージのルールは次の通りです。2つのノードが重なっている場合には、それらのノード値を合計したものを、マージ後のノードの新しい値とします。どちらか一方にしか存在しないノードについては、空でない側のノードをそのまま新しい木のノードとして利用します。例えば、次のような2つの木があったとします。これらをマージすると、結果は次のようになります。解き方

正の整数 n が与えられたとき、その和がちょうど n に等しくなるような完全平方数の最小個数を求める問題を考えます。例えば n = 10 の場合を考えてみましょう。10 = 9 + 1 と表せるため、必要な完全平方数は 2 個となり、出力は 2 になります。解法のアプローチ（動的計画法）この問題は、動的計画法（DP）を使うことで効率的に解くことができます。手順は以下の通りです。長さ n + 1 の DP テーブルを作成し、すべての要素を無限大（INF）で初期化するdp[0] = 0 と設定する（0 を作るのに必要な個数は 0）i = 1 から始めて、i × i ≤ n を満たす間、以下を繰り返

後置記法とは後置記法（ポストフィックス記法）は「逆ポーランド記法（Reverse Polish Notation）」とも呼ばれる数式の表記方法で、演算子をオペランドの後に配置するのが特徴です。この記法で書かれた式を評価するには、スタックというデータ構造を利用するのが一般的です。例えば、式が「21+3*」であれば、計算結果は 9 になります。これは通常の中置記法でいう「(2 + 1) × 3 = 9」に相当します。評価アルゴリズムの手順スタックを使って後置記法の式を評価する際の基本的な流れは以下の通りです。後置記法の式に含まれる各文字 ch について、次の処理を行います。ch が演算子 ⊙ の場

複数の区間(インターバル)が与えられたとき、残りの区間同士が互いに重ならないようにするために削除すべき区間の最小数を求める問題について解説します。例えば、区間が [[8,10],[3,5],[6,9]] の場合、出力は 1 になります。これは [6,9] を1つ削除すれば、残りのすべての区間が重ならなくなるためです。解決のためのアプローチこの問題は貪欲法(グリーディーアルゴリズム)を使うことで効率的に解けます。各区間を終了時刻の昇順に並べ替え、終了時刻が早い区間から順に選んでいくことで、できるだけ多くの非重複区間を確保でき、結果として削除が必要な区間の数が最小になります。具体的な手順は以下の通

数列 nums ともう一つの整数 k が与えられているとします。ここで、リストから連続する部分リスト（サブリスト）を高々一度だけ削除できるものとします。削除後のリストの中で、「k より厳密に小さい数」と「k より厳密に大きい数」の個数が等しくなるような、最長のリストの長さを求めるのが目的です。 たとえば、入力が nums = [6, 10, 8, 9, 3, 5]、k = 6 の場合を考えてみましょう。このとき出力は 5 になります。部分リスト [9] を削除すると [6, 10, 8, 3, 5] が得られ、6 より小さい数は [3, 5] の2つ、6 より大きい数は [10, 8] の2つ

長さ n の棒（ロッド）と、各長さに対応する価格リストが与えられているとします。このとき、棒を適切な位置で切断して市場で売却することで得られる最大の利益を求めるのが、いわゆる「ロッドカッティング問題」です。さまざまな位置で切断した場合の売上を比較し、最も高い利益を実現できる切り方を見つける必要があります。例えば、入力が prices = [1, 5, 8, 9, 10, 17, 17, 20]、n = 8 の場合、出力は 22 になります。これは、棒を長さ 2 と 6 に切断すると、利益が 5 + 17 = 22 となるためです。解法のアプローチこの問題は動的計画法（DP）を使うことで効率的に

連結リスト（Linked List）が与えられたとき、そのリストを右方向にk回転させることを考えます。ここでkは正の整数とします。 たとえば、リストが [1 → 2 → 3 → 4 → 5 → NULL] で k = 2 の場合、出力は [4 → 5 → 1 → 2 → 3 → NULL] となります。これは末尾の2要素が先頭へ移動した状態を表しています。 アルゴリズムの手順 最も効率的なアプローチは、まずリスト全体を環状（循環リスト）につなぎ変えてから、適切な位置で切断する方法です。手順は以下の通りです。 リストが空の場合は、nullを返す len := 1 と初期化する tail と

各要素が1文字として格納された文字配列(文)が入力として与えられたとき、その文を単語ごとに反転することを考えます。例えば、入力が [t,h,e, ,m,a,n, ,i,s, ,n,i,c,e] の場合、出力は [n,i,c,e, ,i,s, ,m,a,n, ,t,h,e] となります。つまり、各単語内の文字の並びはそのままに、単語の出現順だけが逆になります。この問題を解くために、以下の手順に従います。配列 s 全体を反転するj := 0 とするn := s のサイズとするi := 0 から i < n まで、i を1ずつ増やしながら以下を繰り返すs[i] が空白文字 と等しい場合、以