C#

C#で文字列を扱う際、「This is my book」のような文章の単語の順序だけを逆にしたいケースがあります。単純に文字を反転すると「koob ym si siht」になってしまいますが、ここでは単語単位で反転させ「book my is This」を得る方法を解説します。アルゴリズムの考え方この問題は、以下の2段階の処理で解決できます。reverseWordsメソッドを作成し、char型の配列を引数として受け取ります。文字列を先頭から走査し、空白（スペース）に到達するたびに、その直前までの単語を反転します。最後のステップとして、文字列全体をインデックス0からn-1まで反転します。処理の流れ

概要文字列の中で最初に一度だけ出現する文字（一意な文字）のインデックスを、C#の組み込み関数に頼らずに求める方法を解説します。アルゴリズムの考え方まず、長さ256の空の配列を新しく作成します。次に、文字列全体を1文字ずつ走査しながら、各文字の出現回数をこの配列に記録していきます。すべての文字を数え終えたら、もう一度文字列を先頭から走査し、カウントが「1」になっている最初の文字を見つけて、そのインデックスを返します。該当する文字が存在しない場合は -1 を返します。例1aabccd → 各文字の出現回数は a:2、b:1、c:2、d:1 → カウントが1の最初の文字は「b」です。したがって、b

文字列の中で一度だけ出現する文字（一意の文字）のうち、最も早く現れるものを探すアルゴリズムは、面接やコーディングテストでよく出題される定番問題です。ここでは、C#の組み込みメソッド（IndexOf や Count など）に頼らず、基本的な配列操作だけで実装する方法を紹介します。アルゴリズムの考え方まず、長さ256の新しい空の配列を作成します。これは英数字などの文字コード（ASCII値）をインデックスとして扱うためです。次に、対象の文字列を先頭から1文字ずつ走査し、各文字に対応する配列の要素の値をインクリメントしていくことで、それぞれの文字の出現回数を記録します。すべての文字のカウントが完了した

C#では、組み込み関数に頼らなくても、いくつかのアルゴリズム的なアプローチによってソート済み配列の中から欠落している数値を効率的に特定できます。本記事では、代表的な3つの方法を具体的なコード例とともに解説します。 方法1：等差数列の和の公式を利用する 0からnまでの連続する整数の合計は、有名な公式「n(n+1)/2」で求めることができます。まず配列の要素数からこの公式で理論上の合計値を算出し、次に実際に配列内の全要素を足し合わせた値を求めます。この2つの差分こそが、欠落している数値です。 計算量：O(n) 追加メモリ：不要（O(1)） 方法2：ブール型の補助配列を使用する 元の配列の要素数

欠損している数を見つける方法まず、元の配列よりも1つ大きいサイズのbool型配列を新しく作成します。次に、元の配列全体を走査し、各数値が出現したら新しく作成した配列の対応するインデックスを true に設定していきます。すべての走査が完了した後、この配列を先頭から再度走査し、最初に false となっているインデックスが欠損している数となります。重複している数を見つける方法同様に、int型のカウント用配列を別途用意します。各数値の出現状況を記録し、同じ数が2回目に出現した時点でその位置の値を2に更新します。走査後、最初に値が2になっているインデックスが、重複している数を示します。サンプルコード

この問題は、配列の先頭要素からスタートし、そこから到達可能なすべての要素に対して再帰的に同じ処理を呼び出すことで解くことができます。先頭から配列の末尾に到達するまでの最小ジャンプ回数は、「先頭から到達可能な各要素から末尾へ到達するのに必要な最小ジャンプ回数」をもとにして計算できます。例として、次の配列を考えてみましょう。Array == {1, 3, 6, 3, 2, 3, 6, 8, 9, 5};この場合、末尾に到達するために必要なジャンプ回数は 4 回 です。アルゴリズムの考え方現在位置にある値が「その位置から何歩先までジャンプできるか」を表しています。そこで、ジャンプ可能な範囲内の各候補

n×nの行列には、合計で n/2 個の「正方形（リング）」が存在し、ネストされたループを使って各リングを1つずつ処理することで回転を実現できます。各リング内では、要素が4つ1組のサイクルで移動するため、そのサイクルごとに要素を反時計回りに入れ替えていきます。要素の移動ルール各サイクルにおける要素の移動先は以下の通りです。位置 (n-1-j, i) の要素は、位置 (i, j) へ移動位置 (i, j) の要素は、位置 (j, n-1-i) へ移動位置 (j, n-1-i) の要素は、位置 (n-1-i, n-1-j) へ移動位置 (n-1-i, n-1-j) の要素は、位置 (n-1-j, i

n×n の正方行列全体を、指定された回数（k 回）だけ 90 度ずつ回転させるアルゴリズムを解説します。アルゴリズムの考え方n×n の行列には、外周から内周へ向かって同心円状の「層」が合計 n/2 個存在します。入れ子になったループを使えば、これらの層を 1 つずつ順番に処理できます。各層の中では、要素が 4 個ずつのグループで循環しながら移動します。そこで、サイクルごとに関係する 4 つの要素をまとめて入れ替えることで、行列全体の回転を実現します。具体的な要素の移動ルールは次のとおりです。(n-1-j, i) の位置にある要素は (i, j) へ移動する(i, j) の位置にある要素は (j

行列をスパイラル（渦巻き）順に出力するには、外側のリングから順に「最上行 → 最右列 → 最下行 → 最左列」の順で要素を処理し、これをすべての内側の行列がカバーされるまで繰り返します。スパイラル順に出力する手順ステップ1 − 最上行の要素を左から右へ出力するステップ2 − 最右列の要素を上から下へ出力するステップ3 − 最下行の要素を右から左へ出力するステップ4 − 最左列の要素を下から上へ出力するステップ5 − 内側の行列が存在する限り、上記の手順を内側のリングに対して繰り返すコード例using System;namespace ConsoleApplication{  

C#を使用して、2次元グリッド（マトリックス）内に存在する島の数を求める方法を解説します。この問題は「Number of Islands」として知られる定番のアルゴリズム問題で、深さ優先探索（DFS）を活用することで効率的に解くことができます。 アルゴリズムの基本的な考え方 この問題は、以下の手順で解決できます。 グリッドの線形走査： 2次元グリッドマップを左上から順番に走査していきます。 陸の検出： ノードに「1」が含まれている場合、そのノードはDFS（深さ優先探索）を開始するルートノードとなります。 訪問済みマーク： DFSの実行中、訪問したすべてのノードを「0」に設定して訪問済みとして

この記事では、C#を使用して再帰呼び出し（バックトラッキング）によって任意の数の累乗を計算する方法を解説します。アルゴリズムの考え方まず、基数 x と指数 n を引数に取る FindPower 関数を作成します。ここでは x = 2、n = 累乗する回数とします。処理の流れは以下の通りです。n が 0 になったら 1 を返す（再帰の終了条件）n を半分にして再帰的に自分自身を呼び出すn が偶数の場合：result × result を返すn が奇数の場合：x × result × result を返すこの手法では、毎回 x を掛ける代わりに結果を二乗しながら再帰を進めるため、通常のループによる

バックトラッキング（backtracking）は、すべての候補を体系的に試しながら、行き詰まったら直前の状態に戻って別の選択肢を探索するアルゴリズム手法です。文字列の順列生成にも効果的に活用できます。バックトラッキングによる順列生成の考え方まず、先頭の位置に置く文字を選び、残りの文字を先頭の文字と入れ替えます。たとえば「ABC」という文字列の場合、1回目の反復で A を A・B・C のそれぞれと入れ替えることにより、「ABC」「BAC」「CBA」の3つの文字列が生成されます。続いて、2番目の文字 B を固定するように、残りの文字についても同じ手順を繰り返します。その後、元の並びに戻すためにもう

電話番号のキーパッド（2〜9）に対応する文字の組み合わせをすべて求める問題は、より小さく単純な「部分問題」に分割して考えることができます。各数字を1つずつ順番に処理し、それぞれの数字から到達可能な文字をマップ（Dictionary）に格納しておきます。そして、組み合わせの長さが入力された桁数に達した時点で、その結果をカウント・記録していきます。アプローチのポイントこの種の問題は「バックトラッキング（探索の巻き戻し）」と呼ばれる手法で効率的に解くことができます。具体的な流れは以下の通りです。各数字に対応する文字のマッピングをDictionaryで定義する先頭の数字から順に、対応する各文字を現在の

目標合計問題（Target Sum Problem）とは 目標合計問題とは、与えられた配列の中から要素を組み合わせて選んだとき、その要素の合計が指定した数値（目標値）と一致するような組み合わせを見つける問題です。 バックトラッキング（バックトラック法）によるアプローチでは、最悪の場合すべての組み合わせを探索することになりますが、それでも一般には部分和問題に対する単純な再帰アプローチよりも効率的に動作します。途中で合計が目標値を超えた時点でその経路を打ち切る「枝刈り」ができるためです。 ここでは、n個の正整数からなる配列と目標値 sum が与えられたとき、配列の要素は何度でも繰り返し使用できるも

個別のサブセット問題とは「個別のサブセット問題」では、与えられた配列から重複しない組み合わせをすべて抽出します。目標とする要素数（ターゲット）が2であれば、配列の中から2つの要素を選ぶすべての組み合わせを、ターゲットが3であれば3つの要素を選ぶすべての組み合わせを求めます。例えば、配列が [1, 2, 3] でターゲットが 2 の場合、取得できる組み合わせは「1,2」「2,3」「1,3」の3つになります。C#での実装例（バックトラッキング）以下のコードでは、バックトラッキング（探索の途中で条件を満たさなくなったら一つ前の状態に戻る手法）を使って、指定したサイズの組み合わせを効率的に生成していま

アルゴリズムの考え方 この問題は、バックトラッキング（探索と巻き戻し）を用いて解くことができます。まず、最終的な答えを格納するための出力リストと、再帰木をたどる過程で現在使用中の数値列を一時的に保持する現在のリストを用意します。 次に、再帰処理を行うバックトラッキング関数を定義します。この関数は、合計値が目標値に達するまで再帰的に探索を進めます。もし合計値が目標値を超えてしまった場合は、それ以上探索を続けても意味がないため、直前の状態へ戻り（バックトラックし）、別の候補を試します。 探索の途中で合計値がちょうど目標値と一致した場合は、選択中の数値の個数がk個に達しているかどうかを確認します。

C#ではバックトラッキング（Backtracking）の手法を用いることで、指定した数値の合計になる一意な数字の組み合わせを効率的に求めることができます。この記事では、その考え方と具体的な実装例をわかりやすく解説します。 アルゴリズムの基本的な考え方 まず、有効な組み合わせを格納するための出力リストと、再帰探索の途中経路で見つかった現在の組み合わせを保持する現在リストを用意します。そして、目標値に達するまで再帰的に探索を進めるバックトラック関数を実装します。合計が目標値を超えた時点で、それ以上探索を続けても有効な解は得られないため、直前の状態に戻る（バックトラックする）のがポイントです。 具体

C#でバックトラッキング（バックトラック法）を利用すると、指定された個数の開き括弧「{」と閉じ括弧「}」からなるすべての有効な組み合わせを効率的に生成できます。 アルゴリズムの基本的な考え方 バックトラック用の再帰関数を作成し、次のルールに従って現在の文字列を更新していきます。 開き括弧を追加できる条件： まだ配置していない開き括弧が残っている場合（開き括弧の数がN未満） 閉じ括弧を追加できる条件： 閉じ括弧の数が開き括弧の数を上回らない場合（閉じ括弧の数が開き括弧の数より少ない） 終了条件： 現在の文字列の長さが2×Nに達した時点で、その文字列を1つの完成した組み合わせとして結果に出力する

本記事では、チェスのナイト（騎士）が盤上のすべてのマスを訪れ、かつ同じマスは一度しか通れないという条件で移動する「ナイト・ツアー」の考え方と、始点から目的地までの最小ステップ数をC#で求める方法について解説します。 ナイト・ツアーの種類 ナイトの移動には、完了時の形によって2つのタイプがあります。 閉路ツアー（Closed Tour）：最後にスタート地点からナイトの1手で戻れる位置に到達し、閉じたループを形成するツアー。 開放ツアー（Open Tour）：スタート地点に戻らず、盤上の任意の場所で終了するツアー。 有効な移動とは、移動先が盤面の内側にあり、かつそのマスがまだ訪問されていな

概要回転されたソート済み配列（ローテート・ソート配列）から特定の値を検索するには、通常の二分探索を少し改良した再帰的なアプローチが有効です。ポイントは、中央の要素（最小要素）のインデックスを基準に配列を2つの部分に分け、どちら側に目的の値が存在するかを判定しながら探索範囲を絞り込んでいくことです。アルゴリズムの手順中央要素（最小要素）のインデックスを見つける。以下の条件に基づいて、該当する部分配列に対して二分探索を適用する。検索対象の値が開始要素から mid-1 番目の要素の間に存在する場合、start ～ mid-1 の範囲で二分探索を再帰的に実行する。それ以外で、値が mid ～ 末尾の要