アルゴリズムは美しいものです。私がこれらの古典的な Java アルゴリズムについて話すのを聞いた後、あなたはアルゴリズムの虜になるでしょう。

[[393090]]

この記事はWeChatの公開アカウント「Qianyu's IT House」から転載したもので、著者はQianyu Ericです。この記事を転載する場合は、Qianyu’s IT Hut の公開アカウントまでご連絡ください。

みなさんこんにちは、私はXiaoyuです。

プログラミングに関しては、アルゴリズムを習得することによってのみ、プログラミングの真髄を理解できます。アルゴリズムは確かに初心者には少し難しいですが、将来的により良い開発と進歩を望むなら、アルゴリズムの体系的な学習は最も重要です。

Java プログラマーにとって、このバックエンド言語は単なる外部スキルです。私たちは、その構文、フレームワーク、およびいくつかのツールの使用方法を学ぶことに興味があります。アルゴリズムは私たちの本当の内なる力です。アルゴリズムは、システムの設計方法、高性能なコードの書き方に重点を置いており、思考能力を絶えず養成することで、作業効率を向上させます。

今日は、Xiaoyu が、私たちが知っておくべき Java の古典的なアルゴリズムをいくつか紹介します。これらの古典的なアルゴリズムから、アルゴリズムの美しさと独自性を理解し、興味を持ち、キャリア開発に役立つことを願っています。さて、本文に入りましょう。

バイナリ検索

導入

基本的な考え方: バイナリ検索とも呼ばれ、検索するシーケンスを順序付けする必要があります。これは、時間計算量が O(logn) の高速検索アルゴリズムであり、データセットが順序付けされたデータセットである必要があります。

使用

適用シナリオ: 通常は配列要素の検索に使用され、検索前に配列をソートする必要があります (通常は昇順)。

ステップ：

1. 中間位置の値と検索キーワードを比較します。中間位置の値が検索キーワードより大きい場合は、前半の検索処理を繰り返します。

2. 中間位置の値が検索するキーワードより小さい場合は、後半部分で検索処理を繰り返します。

3. 検索が完了するまで、シーケンス内に検索するキーワードはありません。

コード例:

公共 静的  int biSearch( int []配列, int a){
整数0;
 int hi=配列の長さ-1;
整数中間;
    while(lo<=hi){
        mid=(lo+hi)/2;//中間の位置
        if(配列[mid]==a){
 mid+1を返します。
        } else if(array[mid]<a){ //右方向に検索
            lo=mid+1;
        } else { //左に検索
            hi=mid-1;
        }
  }
 -1 を返します。
 }

バブルソートアルゴリズム

導入

基本的な考え方: 隣接する 2 つのデータを比較します。前のデータが後ろのデータより大きい場合は、2 つのデータを交換します。このように、配列を 0 番目のデータから N-1 番目のデータまで走査した後、最大のデータは配列の N-1 番目の位置に「沈みます」。 N=N-1、Nが0でない場合は前の2つの手順を繰り返し、それ以外の場合はソートが完了します。

使用

適用シナリオ: データ量は大きくなく、安定性が求められ、データは基本的に整然としています。

ステップ：

1. シーケンス内のすべての要素を 2 つずつ比較し、最大の要素を最後に配置します。

2. 残りのシーケンスのすべての要素を 2 つずつ比較し、最大のものを最後に配置します。

3. 数字が 1 つだけ残るまで手順 2 を繰り返します。

コード例:

公共 静的voidバブルソート1( int []a, intn ){
整数i, j;
 for (i=0; i<n; i++){//はn回のソート処理を表します。
 (j=1; j<ni; j++)の場合{
            if(a[j-1] > a[j]){//前の数字は後ろの数字より大きいので、
                //a[j-1]とa[j]を入れ替える
整数 温度;
温度= a[j-1];
                a[j-1] = a[j];
                a[j] =一時;
            }
    }
  }
 }

挿入ソートアルゴリズム

導入

基本的な考え方は、順序付けられたシーケンスを構築することです。ソートされていないデータの場合は、ソートされたシーケンスを後ろから前へスキャンし、対応する位置を見つけて挿入します。

使用

適用シナリオ: データ量が大きくなく、アルゴリズムの安定性が求められ、データが部分的または全体的に順序付けられている。

ステップ：

1. ソートする最初のシーケンスの最初の要素を順序付きシーケンスとして扱い、2 番目の要素から最後の要素までをソートされていないシーケンスとして扱います。

2. ソートされていないシーケンスを最初から最後までスキャンし、スキャンした各要素を順序付けられたシーケンスの適切な位置に挿入します。 (挿入する要素が順序付けられたシーケンス内の要素と等しい場合、挿入する要素は等しい要素の後に挿入されます。)

コード例:

パブリッククラス InsertSort は IArraySort を実装します { 
 
    @オーバーライド
公共  int [] sort( int [] sourceArray) 例外をスローします {
        //パラメータの内容を変更せずにarrをコピーする
int [] arr = Arrays.copyOf(sourceArray, sourceArray.length); 
 
        // インデックス 1 の要素から開始し、挿入する適切な位置を選択します。インデックス 0 の要素は 1 つしかなく、デフォルトで順序付けされているためです。
 ( int i = 1; i < arr.length; i++) { 
 
            //挿入するデータを記録する
tmp = arr[i]; 
 
            // ソートされたシーケンスの右端から始めて、それより小さい数を見つけます
整数j = i;
            (j > 0 && tmp < arr[j - 1]) の場合 {
                arr[j] = arr[j - 1];
                j --;  
            } 
 
            // より小さい数字がある場合は、挿入します
            もし (j != i) {
                arr[j] = tmp;
            } 
 
        }
 arrを返します。
    }
 }
クイックソートアルゴリズム

クイックソートアルゴリズム

導入

基本的な考え方: ベンチマーク値としてキー値を選択します。ベンチマーク値より小さいものは左側のシーケンス（通常は順序なし）にあり、ベンチマーク値より大きいものは右側のシーケンス（通常は順序なし）にあります。通常、シーケンスの最初の要素が選択されます。

使用

適用シナリオ: 値の範囲が大きく、同じ値の確率が小さく、データ量が多く、安定性が考慮されていない場合、値がデータ量よりはるかに大きいときに検出力が大きくなります。

ステップ：

1. 1 回のループで、後ろから前に向かって比較し、参照値を最後の値と比較します。参照値より小さい場合は、位置を交換します。そうでない場合は、参照値より小さい最初の値が見つかるまで次の値を比較し続け、その後交換します。

2. この値を見つけたら、前から後ろに向かって比較を開始します。ベンチマーク値より大きい値がある場合は、位置を入れ替えます。そうでない場合は、ベンチマーク値より大きい最初の値が見つかるまで、次の値を比較し続けます。

3. 前から後ろへの比較インデックスが後ろから前への比較インデックスより大きくなるまで、最初のループは終了します。このとき、基準値は、左側と右側の順序が揃っています。

コード例:

パブリックvoidソート( int []a, intlow , inthigh ){
 int開始 = 低い;
整数 終了= 高;
整数 キー= a[低];
        while(終了>開始){
            //後ろから前へ比較する
            while(終了>開始&&a[終了]>=キー)
                //キー値より小さい値がない場合、キー値より小さいスワップ位置があるまで次の値を比較し、前方から後方に比較します
終わり- ;  
            if(a[終了]<=キー){
整数  temp = a[終了];
                a[終了] = a[開始];
                a[開始] = temp ;
            }
            //前から後ろまで比較する
            while(終了> 開始&&a[開始]<=キー)
                //キー値より大きい値がない場合、キー値より大きい値を持つスワップ位置が現れるまで次の値を比較します
                開始++;
            if(a[開始]>=キー){
整数  temp = a[開始];
                a[開始] = a[終了];
                a[終了] = temp ;
            }
        //この時点で、最初のループ比較が終了し、キー値の位置が決定されます。左側の値はすべてキー値より小さく、右側の値はすべてキー値より大きいですが、両側の順序は異なる場合があります。次の再帰呼び出しを行います
        }
        //再帰
        if(start>low) sort(a,low,start-1);//左のシーケンス。キー値インデックスの最初のインデックス位置 - 1
        if( end <high) sort(a, end +1,high); // 正しいシーケンス。キー値インデックス+1から最後まで
    }
 }

シェルソートアルゴリズム

導入

基本的な考え方は、まずソートするレコードのシーケンス全体をいくつかのサブシーケンスに分割し、それらを個別に直接挿入してソートすることです。シーケンス全体のレコードが「基本的に順序付けられている」場合、すべてのレコードが 1 つずつ直接挿入され、ソートされます。

使用

適用シナリオ: データ量が多く、安定性が求められません。

ステップ：

1. 増分シーケンス t1、t2、...、tk を選択します。ここで、ti>tj、tk=1 です。

2. 増分シーケンスの数 k に従ってシーケンスを k 回ソートします。

3. 各ソートラウンドでは、対応する増分tiに従って、ソート対象のシーケンスが長さmの複数のサブシーケンスに分割され、各サブシーケンスが直接挿入されてソートされます。増分係数が 1 の場合のみ、シーケンス全体がテーブルとして扱われ、テーブルの長さがシーケンス全体の長さになります。

コード例:

プライベートvoid shellSort( int []a){
整数dk = a.length/2;
    dk >= 1 の間{
        ShellInsertSort(a, dk);
        dk = dk/2;
    }
 } 
 
プライベートvoid ShellInsertSort( int [] a, int dk) {
    //挿入ソートに似ていますが、挿入ソートの増分は 1 です。ここでの増分は dk です。1 を dk に置き換えるだけです。
 ( int i=dk;i<a.length;i++) {
        a[i]<a[i-dk])の場合{
整数j;
 int x=a[i]; //xは挿入する要素
            a[i] = a[i-dk];
 (j=i-dk; j>=0 && x<a[j];j=j-dk)の場合{
                //ループを通じて、一度に 1 つずつ位置を戻り、挿入する位置を見つけます。
                a[j+dk]=a[j];
            }
            a[j+dk]=x;//挿入
        }
  }
 }
マージソートアルゴリズム

マージソートアルゴリズム

導入

基本的な考え方: マージソート法は、2 つ (またはそれ以上) の順序付きリストを新しい順序付きリストにマージします。つまり、ソートするシーケンスを、それぞれが順序付けされた複数のサブシーケンスに分割します。次に、順序付けられたサブシーケンスを全体の順序付けられたシーケンスにマージします。

シーンの使用

適用シナリオ: メモリが少なく、並列計算が可能な場合に使用します。

ステップ：

1. 隣接する 2 つの数字を選択して、順序付けられたシーケンスを形成します。

2. 隣接する 2 つの順序付きシーケンスを選択して、順序付きシーケンスを形成します。

3. すべてが順序付けられたシーケンスを形成するまで、2 番目の手順を繰り返します。

コード例:

パブリッククラス MergeSortTest {
公共 静的void main(String[] args) {
 int [] データ = 新しいint [] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
        印刷(データ);
        データをマージソートします。
        System.out.println ( "ソートされた配列:" ) ;
        印刷(データ);
    } 
 
公共 静的void mergeSort( int []データ){
        ソート(データ、0、データの長さ - 1);
    } 
 
公共 静的voidソート( int []データ, int  左、 int  右） {
        (左>=右)の場合
戻る;
        // 中間のインデックスを見つける
int中心 = (左+右) / 2;
        // 左の配列を再帰的に返す
        sort(データ、左、中央);
        // 右の配列を再帰的に処理する
        sort(データ、中央 + 1、右);
        // マージ
        マージ(データ、左、中央、右);
        印刷(データ);
    } 
 
    /**
    * 2 つの配列をマージします。2 つの配列はマージ前にすでに順序付けられており、マージ後も順序付けられたままです。
    * @param データ
    * 配列オブジェクト
    * @param左  
    * 左の配列の最初の要素のインデックス
    * @param 中心
    * 左の配列の最後の要素のインデックス、center+1 は右の配列の最初の要素のインデックスです
    * @param右  
    * 右配列の最後の要素のインデックス
    */
公共 静的voidマージ( int []データ、 int  左、 int中央、 int  右） {
        // 一時配列
int [] tmpArr = 新しいint [データの長さ];
        // 右の配列の最初の要素のインデックス
int中央 = 中心 + 1;
        // 3番目は一時配列のインデックスを記録します
int 3番目 =左;
        // 左の配列の最初の要素のインデックスをキャッシュします
int tmp =左;
        while (左<= 中央 && 中央 <=右) {
            // 2つの配列から小さい方を取って一時配列に格納します
            if (データ[左] <= データ[中央]) {
                tmpArr[third++] = data[ left ++];
            }それ以外{
                tmpArr[third++] = data[mid++];
            }
        }
        // 残りの部分は順番に一時配列に格納されます (実際には、2 つの while ステートメントのうち 1 つだけが実行されます)
        （中央 <=右）の間 {
            tmpArr[third++] = data[mid++];
        }
        while (左<= 中央 ) {
            tmpArr[third++] = data[ left ++];
        }
        //一時配列の内容を元の配列にコピーします
        // (元の左から右の範囲の内容が元の配列にコピーされます)
        (tmp <=右) の間 {
            データ[tmp] = tmpArr[tmp++];
        }
    } 
 
公共 静的void print( int []データ){
 ( int i = 0; i < データ長; i++) {
            システム.out.print (data[i] + "\t" );
        }
        System.out.println( ) ;
    }
 }

バケットソートアルゴリズム

導入

基本的な考え方: 配列 arr を同じサイズの n 個のサブ間隔 (バケット) に分割し、各サブ間隔を個別にソートし、最後にそれらを結合します。カウンティングソートはバケットソートの特殊なケースであり、カウンティングソートは各バケットに要素が 1 つだけあるケースと見なすことができます。

使用

適用シナリオ: データ量が非常に大きく、スペースが比較的豊富な場合に非常に実用的であり、アルゴリズム計算の桁数を大幅に削減できます。

ステップ：

1. ソートする配列の最大値maxと最小値minを見つける

2. 動的配列 ArrayList をバケットとして使用し、バケット内の要素も ArrayList に格納されます。バケットの数は（maxmin）/arr.length+1です。

3. 配列arrを走査し、各要素arr[i]が配置されているバケットを計算する。

4. 各バケツを別々に分類する

コード例:

公共 静的voidバケットソート( int []arr){
整数 最大値= Integer.MIN_VALUE ;
整数 最小値= Integer.MAX_VALUE ;
 ( int i = 0; i < arr.length; i++) {
 max = Math.max ( max 、 arr[i] )。
 min = Math.min ( min 、 arr[i] )。
    }
    //バケットを作成する
intバケット数 = (最大-最小) / arr.length + 1;
    ArrayList<ArrayList< Integer >> bucketArr = new ArrayList<>(bucketNum);
 ( int i = 0; i < バケット番号; i++) {
        bucketArr.add (新しいArrayList<Integer> ( ));
    }
    //各要素をバケットに入れる
( int i = 0; i < arr.length; i++) {
 int num = (arr[i] - min ) / (arr.length);
        バケットArr.get(num) .add (arr[i]);
    }
    // 各バケットをソートする
( int i = 0; i < bucketArr.size ( ); i++) {
        コレクションをソートします(bucketArr.get(i));
    }
 }

基数ソートアルゴリズム

導入

基本的な考え方: 比較するすべての値 (正の整数) を同じ桁の長さに統一し、短い桁の先頭のゼロを埋めます。次に、最下位ビットから始めて、1 つずつ並べ替えます。このように、最下位ビットから最上位ビットまでソートすると、シーケンスは順序付けられたシーケンスになります。

使用

適用シナリオ: 大きな数値または非常に長い数値をソートするために使用されます。

ステップ：

1. すべての数字の 1 桁目を取り出し、1 桁目に従って並べ替えてシーケンスを作成します。

2. 新しく形成されたすべての数字の 10 の位を取り出し、10 の位に従って並べ替えて、シーケンスを形成します。

コード例:

パブリッククラスradixSort {
    inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,25,53,51}; 
 
パブリックradixSort(){
        ソート(a);
 (int i = 0; i < a.length; i++)の場合{
            System.out.println (a[i]) ;
        }
  } 
 
パブリックvoidソート( int []配列){
        //まずソートパスの数を決定します。
整数 最大=配列[0];
 ( int i = 1; i < 配列の長さ; i++) {
            if(配列[i]>最大){
最大値=配列[i];
            }
    }
整数 時間=0;
        //桁数を判定します。
        while(最大>0){
最大/=10;
時間++;
        }
        // 10 個のキューを作成します。
        リスト<ArrayList> キュー = newArrayList<ArrayList>();
 ( int i=0;i<10;i++)の場合{
            ArrayList< Integer >queue1 = 新しいArrayList< Integer >();
            キューに追加(キュー1);
        }
        //時間の割り当てと収集を実行します。
 ( int i=0;i<時間;i++) {
            // 配列要素を割り当てます。
 (intj=0;j<array.length;j++) {
                //時刻+ 数字の 1 桁目を取得します。
 int x =配列[j]%( int )Math.pow(10,i+1)/( int )Math.pow(10, i);
                ArrayList<整数>queue2=queue.get(x);
                キュー2.add (配列[j]);
                キューを設定します(x,キュー2);
            }
整数  count =0; //要素カウンター;
            //キュー要素を収集します。
 ( int k=0;k<10;k++)の場合{
                while(queue.get(k) .size ()>0){
                    ArrayList<整数>queue3=queue.get(k);
                    配列[ count ] = queue3.get(0);
                    キュー3.削除(0);
カウント++;
                }
      }
    }
  }
 }

剪定アルゴリズム

導入

基本的な考え方: 検索アルゴリズムの最適化において、剪定とは、特定の判断によって不要なトラバースプロセスを回避することです。比喩的に言えば、検索ツリー内のいくつかの「枝」を切り落とすことなので、剪定と呼ばれます。剪定最適化を適用する際の中心的な問題は、剪定判断方法、つまりどの枝を破棄し、どの枝を保持すべきかを決定する方法を設計することです。

使用

適用シナリオ: 通常、DFS および BFS 検索アルゴリズムで使用され、フィルタリング条件を見つけて、不要な検索パスを事前に削減します。

ステップ：

1. トレーニングデータセットに基づいて決定木を生成します。生成される決定木はできるだけ大きくする必要があります。

2. 検証データセットの最も多く生成されたツリーを使用して、最適なサブツリーを剪定して選択します。このとき、最小損失関数が剪定基準として使用されます。

コード例:

クラスソリューション{
パブリックList<List< Integer >> combinationSum( int [] candidates, int target) {
        配列.sort(候補);
        LinkedList< Integer > トラック = 新しい LinkedList<>();
        combinationSum(候補、0、ターゲット、トラック);
結果を返します。
    } 
 
    プライベートList<List< Integer >> 結果 = 新しいArrayList<>(); 
 
    プライベート void combinationSum( int [] 候補, int開始, intターゲット, LinkedList< Integer > トラック) {
        （ターゲット<0）の場合{
戻る;
        }それ以外の場合 (ターゲット == 0) {
            結果に新しいLinkedList<>(track)を追加します。
戻る;
        }
 ( int i = start; i < candidates.length; i++) {
            （ターゲット<候補[i]）の場合{
                壊す;
            }
            トラックを追加します(候補[i]);
            combinationSum(候補, i, ターゲット - 候補[i], トラック);
            トラックを削除します。
        } 
 
    }
 }

バックトラッキングアルゴリズム

導入

基本的な考え方: バックトラッキングアルゴリズムは、実際には列挙に似た検索と試行のプロセスです。主に、検索と試行のプロセス中に問題の解決策を探します。解決条件が満たされなくなったことが判明すると、「バックトラック」して戻って他のパスを試します。

使用

適用シナリオ: 再帰関数を設定します。関数パラメータは、現在の可能な解決策に関する情報を保持します。これらのパラメータに基づいて、可能な解決策または不可能な解決策が取得され、バックトラックされます。よく見られるケースには、N クイーン、数独、セットなどがあります。

ステップ：

1. 問題の解決策を含むソリューション空間を定義します。

2. 検索に適した方法を使用してソリューション空間を整理します。

3. 深さ優先法を使用して解空間を検索します。

4. 境界関数を使用して、解が不可能なサブスペースへの移動を回避します。

コード例:

関数バックトラック(n, 使用済み) {
    // 入力またはステータスが不正かどうかを判定する
    if (入力/状態が無効) {
戻る;
      }
    // 再帰を終了するかどうかを判断し、終了条件が満たされた場合は結果を返します
    if (一致条件) {
戻る 何らかの価値;
      }
    // 考えられるすべての状況を調べ、それぞれを試します
(すべての可能なケース) {
        // 前回の試行が次の試行に影響する場合は、ステータスを書き込む必要があります
        used.push(ケース)
        // 次のステップを再帰的に試し、サブツリーを検索します
        結果 = バックトラック(n + 1、使用済み)
        // この場合、試行は完了しており、次のバックトラック試行を容易にするためにステータスがリセットされます
        used.pop(ケース)
    }
 }

最短経路アルゴリズム

導入

基本的な考え方: 頂点から始まり、グラフのエッジに沿って別の頂点に到達するときに、各エッジの重みの合計が最小となるパスを最短パスと呼びます。最短経路問題を解決するアルゴリズムには、ダイクストラアルゴリズム、ベルマンフォードアルゴリズム、フロイドアルゴリズム、SPFA アルゴリズムなどがあります。

使用

アプリケーションシナリオ: アプリケーションには、コンピュータネットワークルーティングアルゴリズム、ロボットの経路探索、交通ルートのナビゲーション、人工知能、ゲームデザインなどが含まれます。

手順: (ダイクストラアルゴリズムの例)

1. 道路網の中で出発点に一番近く、まだ点検されていない地点を訪問し、その地点を OPEN グループに入れて点検を待ちます。

2. OPEN テーブルから開始点に最も近いポイントを見つけ、この点のすべての子ノードを見つけて、この点を CLOSE テーブルに格納します。

3. この点の子ノードをトラバースして調べます。これらの子ノードと開始点間の距離を計算し、子ノードを OPEN テーブルに格納します。

4. 手順2、3を繰り返します。 OPEN テーブルが空になるか、ターゲットポイントが見つかるまで。

コード例:

 //ダイクストラアルゴリズム
静的  int [] pathSrc = 新しいint [9];
静的  int [] shortPath = 新しいint [9];
静的void shortestPath_DijkStra(MGraph m, int v0) {
    // finalPath[w] = 1は頂点V0からVwへの最短経路が得られたことを示す
int [] finalPath = 新しいint [9];
 ( int i = 0; i < m.numVertexes; i++) {
        最終パス[i] = 0;
        shortPath[i] = m.arc[v0][i];
        パスSrc[i] = 0;
    }
    // v0からv0へのパスは0です
    ショートパス[v0] = 0;
    // vo から v0 へのパスを見つける必要はありません
    最終パス[v0] = 1;
 ( int i = 1; i < m.numVertexes; i++) {
        // 現在わかっているV0への最も近い距離
整数 最小= 無限大;
整数k = 0;
 ( int w = 0; w < m.numVertexes; w++) {
            ショートパス[w] < min && ファイナルパス[w] == 0) {
 min = shortPath[w];
                k = w;
            }
        }
        finalPath[k] = 1; // finalPathの値を変更し、最短パスを見つけたものとしてマークします
( int w = 0; w < m.numVertexes; w++) {
            // 頂点 V を通るパスが元のパスよりも短い場合（V を通らない場合）
            finalPath[w] == 0 && ( min + m.arc[k][w]) < shortPath[w]) の場合 {
                // より短いパスが見つかったことを示します。変更
                shortPath[w] = min + m.arc[k][w]; // パスの長さを変更する
                pathSrc[w] = k; // 頂点添え字Wの前の頂点を変更する
            }
        }
    }
 }

最大サブ配列アルゴリズム

導入

基本的な考え方: 整数配列 nums が与えられた場合、最大の合計を持つ連続したサブ配列 (サブ配列には少なくとも 1 つの要素が含まれます) を見つけ、その最大の合計を返します。

使用

応用シナリオ：実生活では、1週間以内の株式の成長状況を確認し、最も適切な売買タイミングを得るために使用できます。

ステップ：

1. 合計が負の部分文字列を破棄し、合計が正の部分文字列のみを保持します。

2. nums に正の数がある場合は、nums を左から右に走査し、変数 cur を使用して各ステップの累積合計を記録します。正の数 cur に走査する場合は、それを増やし、負の数 cur に走査する場合は、それを減らします。

3. cur>=0 の場合、各累積は最大累積合計になる可能性があるため、別の変数 max を使用して、プロセス全体を通じて cur の最大値を追跡および記録します。

コード例:

クラスソリューション{
公共：
    /*
     * @param nums:整数のリスト
     * @return :合計を示す整数 の 最大サブ配列
     */
 int maxSubArray(ベクトル< int > 数値) {
        if( nums.size ()<=0){
 0を返します。
        }
整数  max =INT_MIN,cur=0; //c++ 最小値
( int i=0; i<nums.size ( ) ); i++)の場合
        {
            もし(現在値 < 0)
                cur = nums[i]; // 前のものの合計が0未満の場合、前のものを破棄します
それ以外 
                cur+=数値[i]; 
 
            現在の値 >最大値の場合
最大値= 現在の値;
        }
戻る 最大; 
 
    }
 };

最長共通部分列アルゴリズム

導入

基本的な考え方: 最長共通部分列は、一連のシーケンス内のすべてのシーケンスの中で最も長い部分列を見つけるために使用される問題です。これは、部分列が元の列内で連続した位置を占める必要がないという点で、最長共通部分文字列を見つける問題とは異なります。

使用

応用シナリオ: 最長共通部分列問題は古典的なコンピュータサイエンスの問題であり、Diff ツールなどのデータ比較プログラムやバイオインフォマティクスアプリケーションの基礎でもあります。また、ファイル間の変更を調整するために、Git などのバージョン管理でも広く使用されています。

ステップ：

1. 再帰を使用して解決できますが、すべての可能性を走査する必要があり、非常に時間がかかります。

2. 一般的な LCS 問題はすべて NP 問題です。

3. 級数の量が一定の場合、動的計画法を使用して解くことができます。

コード例:

クラスソリューション{
公共  int最長共通サブシーケンス(文字列テキスト1、文字列テキスト2) {
長さ1 = テキスト1.長さ();
長さ2 = テキスト2.長さ();
 int [][] a = new int [length1 + 1][length2 + 1]; //0行0列が予約されています
( int i = 1; i <= length1; i++) {
 ( int j = 1; j <= length2; j++) {
                （テキスト1.charAt(i - 1) == テキスト2.charAt(j - 1)）の場合{
                    a[i][j] = a[i - 1][j - 1] + 1;
                }それ以外{
                    もし(a[i][j - 1] > a[i-1][j])であれば{
                        関数 式 a[i][j] = a[i][j - 1];
                    }それ以外{
                        関数 式 a[i][j] = a[i - 1][j];
                    }
                }
            }
        }
 [長さ1][長さ2]を返します。
    }
 }

最小全域木アルゴリズム

導入

基本的な考え方は、n 個の頂点を持つ重み付き無向接続グラフで n-1 個のエッジを選択して最小の接続サブグラフを形成し、接続サブグラフ内の n-1 個のエッジの重みの合計を最小化することです。これは、接続ネットワークの最小全域木と呼ばれます (必ずしも一意ではありません)。

一般的に、最小全域木問題を解決するには、プリムのアルゴリズムとクラスカルのアルゴリズムという 2 つのアルゴリズムが通常使用されます。

使用

適用シナリオ: 一般的にコスト最小化を計算するために使用されます。

手順: (プリムのアルゴリズムの例)

1. ある点から開始し、現在の点からアクセスできるすべてのエッジを見つけます。

2. 見つかったエッジの中で最小のエッジを見つけます。このエッジには、まだ訪問されていないポイントがあるはずです。訪問されていないポイントをセットに追加し、追加されたエッジを記録します。

3. 現在のセットがアクセスできるすべてのエッジを見つけ、追加する新しいポイントがなくなるまで 2 のプロセスを繰り返します。

4. このとき、すべての辺によって形成される木が最小全域木となります。

コード例:

 /** プリムアルゴリズム
    * @param first最小全域木の開始点の識別子
    * @return最小全域木の辺を返す
    */
パブリックリスト<Edge> generateMinTreePrim(T first ){
    //最小全域木の辺を格納する
    List<Edge> 結果 = 新しい LinkedList<>();
    //まずマップを作成します。キーは頂点、値はエッジです
    HashMap<Vertex<T>, Edge> map=new HashMap<>();
    イテレータ<Vertex<T>> vertexIterator=getVertexIterator();
    頂点<T> 頂点;
    エッジ エッジ;
    while(vertexIterator.hasNext()){
        // 最初は、エッジの両端の値はそれ自体で、weight=maxDouble です。
        頂点 = vertexIterator.next ( );
        edge = new Edge(vertex, vertex, Double .MAX_VALUE);
        map.put(頂点、辺);
    }
    //最初は最小全域木の開始点の識別子です
    頂点 = vertexMap.get(最初);
    頂点がnullの場合
        System.out.println ( "ノードなし:" + first );
結果を返します。
    }
    // スパニング ツリーにないすべてのノードはマップのキーです。マップが空の場合は、すべてのノードがツリー内にあることを意味します。
    while(!map.isEmpty()){
        //このループでスパニングツリーに追加されるノードは頂点であり、エッジは頂点に対応するエッジ（つまり、最小のエッジ）です。
        エッジ=map.get(頂点);
        //ノードjがツリーAに追加されるたびに、まずマップからノードを削除します
        map.remove(頂点);
        結果にエッジを追加します。
        System.out.println ( "エッジと頂点を追加するためのツリーを生成します:" + vertex.getLabel()+
 " 、エッジの終点は: " +edge.getEndVertex().getLabel()+ " 、エッジの重みは: " +edge.getWeight());;
        //最初のノードの場合、対応するエッジはそれ自身へのものなので、それを削除します
        if (vertex.getLabel().equals( first )){
            結果.削除(エッジ);
        }
        //次に、マップ内の残りのノードからノード j までの距離を確認します。このエッジの距離が前のエッジの距離よりも短い場合は、そのエッジをノード j までのこのエッジに置き換えます。
        //トラバーサル置換では、同時に最短のエッジminEdgeを見つける
        エッジ minEdge = new Edge(vertex, vertex, Double .MAX_VALUE);
 (Vertex<T> now:map.keySet())の場合{
            エッジ=map.get(now);
            //newEdgeは現在からノードjまでのエッジです
            エッジ newEdge = now.hasNeighbourVertex(vertex);
            if(newEdge!= null &&newEdge.getWeight()<edge.getWeight()){
                //このエッジの距離が前のエッジの距離より短い場合は、ノード j へのエッジをこのエッジに置き換えます。
                エッジ=新しいエッジ;
                map.put(now, edge);
            }
            if(edge.getWeight()<minEdge.getWeight()){
                //minEdgeを更新
                minEdge=エッジ;
            }
        }
        //ここで、エッジの方向は、ツリー上にないv（開始点）からツリー上のuに設定されます。
        //このエッジの開始点はツリー上ではなく、スパニングツリーに参加する次のノードです
        頂点=minEdge.getBeginVertex();
    }
結果を返します。
 }