C#

C#で整数配列内のすべての0（ゼロ）を配列の末尾に移動する方法

C#では、整数型の配列に含まれるすべての0を配列の末尾へ移動したいケースがあります。例えば { 0, 1, 0, 3, 12 } という配列を { 1, 3, 12, 0, 0 } のように並べ替える処理です。本記事では、効率的なアルゴリズムでこの問題を解決する MoveZeros メソッドの実装方法を解説します。アルゴリズムの考え方基本的なアプローチは以下の通りです。まず MoveZeros メソッドを作成し、配列を先頭から順に走査します。走査の過程で0以外の要素を検出したら、それを配列の前方から順番に詰めていきます。次に、非ゼロ要素を格納し終えた位置から配列の末尾までを、すべて0で埋めます

C#で2つの文字列が同型（Isomorphic）かどうかを判定する方法

同型文字列とは？2つの文字列XとYにおいて、X内の各文字の出現箇所をすべて別の文字に置き換えることでYが得られ、その逆も成り立つ場合、XとYは「同型（isomorphic）」であるといいます。例として、文字列「ACAB」と「XCXY」を考えてみましょう。すべての文字の出現箇所は、文字の並び順を保ったまま別の文字へ置き換える必要があります。ここで重要なルールは次のとおりです。各文字は常に同じ文字にのみ対応づけられる異なる2つの文字が同じ文字に対応することはできないただし、ある文字が自分自身に対応することは許される実行例例1：同型の場合入力：s = egg、t = add出力：truee→a、g→

C#で重複文字を含まない最長部分文字列の長さを求める方法【スライディングウィンドウ解説】

与えられた文字列の中から、同じ文字が2回以上現れない最も長い部分文字列の長さを求める問題は、コーディング面接でも頻出の定番アルゴリズム課題です。この記事では、C#を使って「スライディングウィンドウ（Sliding Window）」というテクニックで効率的に解く方法を、具体例と実装コード付きでわかりやすく解説します。 スライディングウィンドウ技法とは スライディングウィンドウでは、i と j という2つのポインタを使用します。最初は両方のポインタが文字列の先頭にある同じ文字を指しています。文字列を走査しながら、以下のルールで処理を進めます。 現在注目している文字 s[j] がリストに存在しない

C#で数値配列の最長連続増加部分列の長さを求める方法

C#で最長連続増加部分列の長さを求めるアルゴリズム longestIncreasingSubsequenceメソッドは、配列内で隣り合う要素が連続して増加している区間（部分列）の中から、最も長いものの長さを整数として返します。仕組みはシンプルで、forループで配列を先頭から順に走査しながら、現在の増加列の長さを変数countで追跡し、その都度最大値resを更新していきます。 計算量 時間計算量：O(N) ― 配列の各要素を一度だけ訪問するため 空間計算量：O(1) ― カウンタ用の変数以外に追加の記憶領域を必要としないため 例 入力：{2, 4, 6, 5, 8}出力：3 この配列では

C#でトップダウン方式（メモ化）を用いてフィボナッチ数列を実装する方法

フィボナッチ数列は、0または1から始まり、その後に1が続き、以降の各数値（フィボナッチ数と呼ばれます）が「直前の2つの数値の合計」というルールに従って生成される数列です。本記事で解説するトップダウン方式は、大きな問題をより小さく理解しやすい単位へ分割して解決していく手法です。フィボナッチ数列の計算においては、再帰呼び出しの結果を配列（メモ化テーブル）にキャッシュすることで、同じ計算を繰り返す無駄を省き、効率的に処理できます。計算量について時間計算量： O(N) — 各フィボナッチ数は一度だけ計算され、以降はメモ化された結果を参照するためです。空間計算量： O(N) — 数値のサイズと同等の追加

C#でボトムアップアプローチを使ってフィボナッチ数列を実装する方法

フィボナッチ数列は、0または1から始まり、その後に1が続き、「各数値（フィボナッチ数）は直前の2つの数値の合計に等しい」という規則に従って進んでいく一連の数列です。具体的には、0, 1, 1, 2, 3, 5, 8, 13, 21, 34… のように数列が展開されます。 ボトムアップ（Bottom-up）アプローチとは、動的計画法（Dynamic Programming）における代表的な手法の一つです。このアプローチでは、まず最も基本的な小さな部分問題から解決していき、それらを段階的に統合しながら、最終的に全体の完全な解を導き出します。フィボナッチ数列の場合、dpArr[1] = 1 という初

C#でトップダウンアプローチにより「1への最小ステップ数」を実装する方法

概要「1への最小ステップ数（Minimum Steps to One）」は、動的計画法の代表的な問題の一つです。整数 n を以下の操作を繰り返して 1 に到達させる際、必要な最小の操作回数を求めます。n が 3 で割り切れる場合：n を n / 3 にするn が 2 で割り切れる場合：n を n / 2 にする常に可能：n から 1 を引く（n - 1 にする）本記事では、C# を用いてトップダウン方式（メモ化再帰）でこの問題を実装する方法を解説します。アルゴリズムの手順MinimumStepstoOneTopdownApproach メソッドは、整数 n とメモ化用の整数配列 dp を引数と

C#のボトムアップ方式で「1にする最小ステップ数」を実装する方法

問題の概要：「1にする最小ステップ数」とは 「1への最小ステップ数（Minimum Steps to One）」は、動的計画法（DP）の入門問題としてよく知られています。整数 n が与えられ、次の3種類の操作を繰り返し適用して、n を 1 に到達させるまでの最小回数を求めます。 操作1： n が 3 で割り切れるとき、n を 3 で割る 操作2： n が 2 で割り切れるとき、n を 2 で割る 操作3： 常に実行可能。n から 1 を引く ボトムアップ方式（Tabulation）の考え方 ボトムアップ方式では、再帰呼び出しを行わずに、小さな部分問題から順番に答えを計算し、dp 配列に結

C#でトップダウンアプローチを使ってコイン両替問題を実装する方法

コイン両替問題とはコイン両替問題は、指定された金額を最小枚数のコインで作るという古典的な動的計画法（DP）の問題です。本記事では、C#を用いて「トップダウンアプローチ（メモ化再帰）」でこの問題を解く方法を解説します。アルゴリズムの基本構造CoinChangeTopDownApproach メソッドは、次の4つのパラメータを受け取ります。n：作りたい金額coins：使用できるコインの種類を格納した配列t：コインの総数dp：計算済みの値をキャッシュするための配列処理の流れは以下の通りです。金額が0なら0を返します（これ以上コインは不要なため）。dp配列に既に計算済みの値があれば、それをそのまま返し

C#でボトムアップアプローチを使ってコイン両替問題を実装する方法

コイン両替問題とは コイン両替問題は、指定された金額を、使用できるコインの種類だけで「最小枚数」で支払う方法を求める、動的計画法の代表的な応用例です。貪欲法（常に一番額面の大きいコインから選ぶ方法）では最適解が得られないコイン体系（例：{1, 7, 10}）でも、動的計画法を使えば確実に最小枚数を求められます。 ボトムアップアプローチの考え方 ボトムアップアプローチ（タブレーション）では、金額0のような小さな部分問題から順に解き、その結果を配列に記録しながら目的の金額へと積み上げていきます。トップダウン方式（メモ化再帰）と違い、再帰呼び出しが不要なためスタックオーバーフローを気にせずに済むの

C#の反復処理を使って木（ツリー）が対称かどうかを判定する方法

反復アプローチによる対称木の判定反復（イテレーティブ）なアプローチでは、2つのキューを作成します。1つ目のキューは左側の子ノードを保存し、2つ目のキューは右側の子ノードを保存する役割を担います。木が空である場合、その木は根ノードを通る垂直軸に対して対称であるとみなされ、true を返します。木が空でない場合は、まず両部分木の根ノードの値が一致しているかを確認します。値が一致していれば、さらに左部分木と右部分木が互いに対称（鏡像）であるかを順番に検証していきます。具体的には、キュー1には「左の子→右の子」の順で子ノードを追加し、キュー2には「右の子→左の子」の順で追加することで、左右を反転させた

C#で再帰を使って木構造（ツリー）が対称かどうかを判定する方法

木構造（ツリー）が対称であるかどうかを再帰的に判定する場合、まず対象の木が null かどうかを確認します。木が null であれば、それ自体が対称とみなされるため true を返します。木が null でない場合は、isSymmetricMirror メソッドを呼び出します。このメソッド内では、左の子ノードと右の子ノードの値を比較し、以下のように判定を行います。両方の子ノードが null の場合 → 対称（true）どちらか一方だけが null の場合 → 非対称（false）両ノードの値が異なる場合 → 非対称（false）上記のチェックを通過したら、左の子と右の子を交差させる形で引数に渡

C#で再帰を使って二分探索木を反転（ミラー化）する方法

二分探索木（Binary Search Tree）を反転するとは、木の左右を入れ替えて、木全体を鏡像に変換することです。本記事では、C#の再帰処理を用いて二分探索木を反転する方法を、コード例とともにわかりやすく解説します。反転の基本的な考え方まず、InvertABinarySearchTree メソッドを呼び出し、対象のノードを引数として渡します。このメソッドの処理の流れは以下の通りです。ノードが null の場合は、そのまま null を返します（ベースケース）。ノードが null でない場合は、左の子と右の子それぞれに対して InvertABinarySearchTree を再帰的に呼び出

C#の再帰を使って二分木が有効な二分探索木（BST）かどうかを判定する方法

二分探索木（Binary Search Tree：BST）とは、すべての左の子ノードが親ノードの値より小さく、すべての右の子ノードが親ノードの値より大きくなるという性質を満たす二分木のことです。この記事では、C#の再帰処理を利用して、与えられた二分木が有効な二分探索木であるかどうかを判定する方法を解説します。判定アルゴリズムの考え方判定は以下の手順で行います。まず、ノードに値が存在するかどうかを確認します。ノードがnullの場合は空の木も有効な二分探索木とみなせるため、trueを返します。次に、ノード・最小値・最大値を引数として渡し、再帰メソッドisValidBSTを呼び出します。各ノードには

C#で二分木に指定した合計値となるパスが存在するか判定する方法

二分木において、ルートから葉までの経路（パス）上のノード値の合計が、指定された値と一致するかどうかを判定する問題は、木構造のアルゴリズム学習における定番テーマの一つです。この記事では、C#を使ってこの問題を再帰的に解く方法を解説します。 アルゴリズムの考え方 HasPathSum メソッドは、2つの引数を受け取ります。1つ目は木のノード、2つ目は目標となる合計値です。 処理の流れは以下のとおりです。 最初にノードが null かどうかをチェックします。ノードが null の場合は false を返します。 ノードが null でなければ、再帰メソッド helperHasPathSum を呼び

C#で余分な領域を使わずに配列内の0・1・2をソートする方法（オランダ国旗問題）

「オランダ国旗問題」は、0・1・2 のみで構成された配列を、追加のメモリ領域を使わずに一括でソートする古典的なアルゴリズム問題です。この記事では、C# を使って3ポインタ方式でこの問題を解く方法を解説します。アルゴリズムの考え方この手法では、low、mid、high という3つのポインタを使用します。low と mid は配列の先頭（インデックス0）から開始します。high は配列の末尾（最後の要素）を指します。そのうえで、mid が指す要素の値に応じて以下のように処理を振り分けます。処理のルールarr[mid] == 0 の場合：arr[mid] と arr[low] を交換し、low と

C#で余分なメモリ領域を使わずに配列内の0と1を並べ替える方法

はじめに0と1だけで構成された配列を、追加のメモリ領域を使わずに並べ替えたいケースはよくあります。本記事では、「2つのポインタ（low と high）」を使ったインプレース（in-place）手法により、時間計算量 O(N) で効率的にソートする方法を解説します。アルゴリズムの考え方まず、low ポインタを配列の先頭に、high ポインタを配列の末尾にそれぞれ配置します。そのうえで、以下のルールに従って処理を進めます。array[low] = 0 の場合： 要素はすでに正しい位置にあるため、交換は不要です。low を1つ先に進めます。array[low] = 1 の場合： この要素は後方へ移動

C#で配列をk回回転させる方法｜反転アルゴリズムによる実装を解説

配列と整数 k が与えられたとき、その配列を k 回回転させるのが本記事のテーマです。例えば k = 3 が指定された場合、配列は3回分だけ回転します。 ここで紹介するのは「反転アルゴリズム（Reversal Algorithm）」と呼ばれる定番手法です。配列全体を一度反転し、その後それぞれの区間を再度反転するだけで、追加メモリほぼゼロで効率的に回転を実現できます。 アルゴリズムの基本手順 まず、配列・開始インデックス・終了インデックスを引数として受け取る Reverse メソッドを作成します。このメソッドを活用し、次の3ステップで回転を行います。 ステップ1： 配列全体（インデックス0 ～

C#でソート済み配列から重複を削除し、新しい長さを返す方法

アルゴリズムの考え方：ツーポインタ（二つのポインタ）を使う配列がすでにソートされている場合、ツーポインタ手法が非常に有効です。2つのインデックス i と j を用意し、i を「遅いランナー（スローランナー）」、j を「速いランナー（ファストランナー）」として扱います。nums[i] と nums[j] が等しい間は、j を進めることで重複要素をスキップしていきます。nums[j] != nums[i] となった時点で、重複の連続が終わったことを意味します。このとき、その値を nums[i + 1] にコピーし、i をインクリメントします。あとは j が配列の末尾に到達するまで、同じ処理を繰り返

C#でソート済み配列から重複を削除し、重複のない配列を返す方法

配列がすでにソートされている場合、重複する要素は必ず隣接しています。この性質を利用すると、2つのポインタ（i と j）を使った効率的なアルゴリズムで重複を削除できます。ここで i はゆっくり進む「スローポインタ」、j は速く進む「ファストポインタ」として機能します。 アルゴリズムの手順 nums[i] == nums[j] の間は重複が続いているため、j を1つずつ進めて重複をスキップしていきます。 nums[j] != nums[i] となった時点で、連続した重複が終わったことを意味します。そこで、その値を nums[i + 1] にコピーし、i をインクリメントしてから同じ処理を繰り返しま