TypeScript中級

中級 TypeScriptで学ぶアルゴリズム｜練習問題編

 

導入

アルゴリズムは実務において重要な役割を果たします。特に、データ処理や検索を効率的に行うための手法は、プログラムのパフォーマンスに大きな影響を与えます。ここでは、TypeScriptを使って特定のシチュエーションにおけるアルゴリズムの実装を通じて、実務で役立つスキルを磨いていきます。

教科書レベルの解説（アルゴリズム）

重要な概念の整理

アルゴリズムの選択は、問題の特性に応じて最適なものを選ぶことが求められます。例えば、データの挿入や削除が頻繁に行われる場合、リスト構造を利用したアルゴリズムが有効です。一方で、データの検索が主な目的であれば、ハッシュテーブルやバイナリツリーが適しています。これらの選択肢を理解することで、より効率的なプログラムを構築できます。

コード例（TypeScript）


function mergeSort(arr: number[]): number[] {
    if (arr.length <= 1) {
        return arr;
    }
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

function merge(left: number[], right: number[]): number[] {
    const result: number[] = [];
    let i = 0, j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }

    return result.concat(left.slice(i)).concat(right.slice(j));
}

コードの行ごとの解説

  1. mergeSort関数: 配列が1つ以下の要素を持つ場合、その配列をそのまま返します。これは再帰の基底条件です。
  2. midの計算: 配列の中央のインデックスを求め、配列を2つの部分に分割します。
  3. 再帰呼び出し: 左右の部分配列に対して再帰的にmergeSortを適用し、ソートされた配列を取得します。
  4. merge関数: 2つのソートされた配列を1つのソートされた配列に統合します。配列の要素を比較し、小さい方を結果に追加します。
  5. concat: 残りの要素を結果配列に追加して、最終的なソート済み配列を返します。

練習問題編

以下の練習問題に取り組むことで、アルゴリズムの理解を深めましょう。

  1. 問題1: 与えられた整数の配列を反転させる関数を作成してください。

    模範解答:

    
function reverseArray(arr: number[]): number[] {
    return arr.reverse();
}
  2. 問題2: 与えられた文字列が回文かどうかを判定する関数を作成してください。

    模範解答:

    
function isPalindrome(str: string): boolean {
    const reversed = str.split('').reverse().join('');
    return str === reversed;
}
  3. 問題3: 2つのソートされた配列をマージする関数を作成してください。

    模範解答:

    
function mergeSortedArrays(arr1: number[], arr2: number[]): number[] {
    let result: number[] = [];
    let i = 0, j = 0;

    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            result.push(arr1[i]);
            i++;
        } else {
            result.push(arr2[j]);
            j++;
        }
    }
    return result.concat(arr1.slice(i)).concat(arr2.slice(j));
}
  4. 問題4: 与えられた配列の最大値を見つける関数を作成してください。

    模範解答:

    
function findMax(arr: number[]): number {
    return Math.max(...arr);
}
  5. 問題5: 与えられた数が素数かどうかを判定する関数を作成してください。

    模範解答:

    
function isPrime(num: number): boolean {
    if (num <= 1) return false;
    for (let i = 2; i <= Math.sqrt(num); i++) {
        if (num % i === 0) return false;
    }
    return true;
}

まとめ

  • アルゴリズムの選択は、問題に応じて最適なものを見極めることが重要です。
  • 実務においては、効率的なデータ処理が求められます。今回の練習を通じて、基本的なアルゴリズムを実装する力を養いましょう。
RELATED POST