「手抜きアルゴリズム」は大企業をターゲットにしており、これがそれだ

[[342088]]

基本的なデータ構造の統合は、大規模システムの基礎となります。たとえば、Redis のスキップリスト、データベースインデックスの B+ ツリーなどです。基本的なデータ構造に十分精通していれば、少し複雑な構造も簡単に理解できます。これは、レベルを突破してモンスターと戦い、最後まで段階的にロックを解除していくのと同じです。本日は、面接でよく聞かれるデータ構造と手動アルゴリズムに関する質問についてご紹介したいと思います。これらのコードは手動で記述する必要があります。質問の70～80％はこれらであると言ってもいいくらいですので、しっかりマスターしておく必要があります。

高頻度ハンドティアリングアルゴリズムコレクション

1 データ構造

リンクリストは、データ構造における線形構造の一種です。まず、データ構造とは何かを見てみましょう。

データ構造は、構造定義 + 構造操作です。

誰もがジグソーパズルで遊んだことがあると思います。ジグソーパズルをする前に、まず説明書を見てパーツがいくつあるかを確認し、それらのパーツを組み立てて、完成するまで組み合わせます。

データ構造における構造定義とは、データ構造がどのように見えるか、どのような特性を持つかということです。構造の操作とは、構造がどのような操作をサポートできるかを意味しますが、どのように操作しても、その構造を破壊することはできません。

2 リンクリストの定義

リンクリストは 1 つ以上のノードで構成され、各ノードには 2 つの情報が含まれます。1 つはデータを格納するために使用されるデータ情報であり、もう 1 つは次のノードのアドレスを格納するために使用されるアドレス情報です。

リンクリストノード

リンクリスト構造はノードで構成されています。構造に変更を加える必要はありません。必要に応じて、リンクリスト構造のデータフィールドを変更するだけです。上図から、データフィールドの型は整数 763 であり、ポインターフィールドは 0x56432 であることがわかります。このアドレスはまさに 2 番目のノードのアドレスであるため、2 つのノードは論理的にポインター関係を持ち、このように 2 つのノードが関連付けられています。

2 番目のノードのポインタフィールドは 0x0 で、これはヌルアドレスと呼ばれる特殊なアドレスです。ヌルアドレスを指すということは、それがこのリンクリスト構造の最後のノードであることを意味します。

これはコードではどのように見えるでしょうか?

構造体ノード{
整数データ;
    構造体 Node *次;
 };

この構造は非常に明確です。データドメインは必要に応じて決定されます。整数を保存したい場合は、整数に変更します。文字列を保存したい場合は、文字列を記述します。ポインターフィールドは、リンクリスト構造全体を維持するために使用されます。一般的には、直接使用できます。メモリ内のリンクリスト構造が必要な場合は、ノード内の次のポインターフィールドに格納されているアドレス値を変更する必要があります。

3 リンクリスト操作

リンクリスト構造に関しては、配列と関連付けることに慣れています。ただ、配列構造はメモリ内で連続していますが、リンクリスト構造にはポインタフィールドがあるため、メモリ内の各ノードの格納場所は連続していない可能性があります。次に、配列と同じ方法でリンクリストに番号を付けます。

単方向リンクリスト

次に、リンクリストにノードを挿入する関数を定義します。

構造体 Node *挿入(構造体 Node *head、 int ind、構造体 Node *a);

最初のパラメータは、操作対象となるリンクリストのヘッドノードアドレス、つまり最初のノードのアドレスです。
2番目のパラメータは挿入位置です
3番目のパラメータは、挿入される新しいノードを指すポインタ変数です。

簡単に言うと、a が指すノードを head が指すリンクリストの ind 位置に挿入し、戻り値は新しいノードが挿入された後のテーブルヘッダーアドレスになります。なぜそれを返す必要があるのでしょうか? 挿入したノードは先頭にある可能性が高いため、リンクリストの構造と先頭ノードのアドレスが変更されるため、それを返す必要があるからです。

次に、要素を挿入すると、リンクリストのノードが明らかに変更されます。操作方法は、リンクリストノードの次のポインターフィールドを変更することです。では、挿入を正常に行うにはどのノードを変更する必要がありますか?

まず、位置 ind - 1 のノードがノード a を指すようにし、次にノード a が元の ind 位置のノードを指すようにします。つまり、2 つのノードの次のポインターフィールドの値を変更します。1 つは位置 ind - 1 のノードで、もう 1 つはノード a 自体です。まず、位置 ind - 1 にあるノードを見つけて、関連する操作を実行します。

構造体Node *挿入(構造体Node *head、 int ind、構造体Node *a) {
    構造体 Node ret、*p = &ret;
    ret.next = ヘッド;
    // 仮想ヘッドノードから開始し、indステップずつ後方に進みます
    p = p->next;  
    //ノード挿入操作を完了する
    a->次= p->次;
    p->次へ= a;
    // 実際のリンクリストのヘッドノードアドレスを返す
ret.nextを返します。
 }

ここで大きな懸念事項であり、重要なのが仮想ノードです。なぜ仮想ノードを導入するのでしょうか。挿入操作を統一するためでしょうか。統一とは何でしょうか。たとえば、5 番目の位置に要素を挿入するとします。当然、先頭から 4 番目のノードまでトラバースする必要があります。4 番目のノードを決定した後、関連する次のポインターフィールドを変更します。つまり、nid の位置に挿入する場合は、先頭ノードから ind-1 ステップ後方に移動する必要があります。挿入位置が 0 の場合はどうでしょうか。-1 ステップを取ることはできないため、この時点では ind=0 の場合について別途判断する必要がありますが、これは明らかに完璧ではありません。そこで、ind が 0 の場合と 0 と等しくない場合を統一するために、仮想ノードを導入します。

わかりました。便利かどうか見てみましょう。仮想ノードが追加されます。5 番目の位置に挿入する場合は、5 桁後退するだけで済みます。0 番目の位置に挿入する場合は、0 ステップ後退するだけで済みます。つまり、p ポインターは仮想ノードを指しています。わかりません。仮想ヘッドノードの後ろに新しいノードを挿入するだけです。

仮想ノード

さて、ここで最初の重要なトリックを紹介します。リンクリストノードを挿入する場合、ダミーノードを追加するのは実用的な手法です。

それでは、挿入と削除のダイナミクスと、それを実装する方法を見てみましょう。

3つの例

ケース1

質問を見てみましょう。幸せな数を定義してください。幸せな数とは何ですか? 幸せな数とは、有限回の変換後に 1 に等しくなる数です。どのように変換するのでしょうか? 1 以外の数値を指定してから、数字を削除し、各数字の二乗の合計を計算して数値 A を取得します。A が正確に 1 ではないと仮定して、要素 A の各数字を二乗して合計し、数値 B を取得します。。。。最終的にはできることを知ってください = 1

たとえば、最初の数字は 19 です。変換ルールの後、数字は 82 になります。1 ではないため、変換を続行します。つまり、もう一度実行します。最後の変換の後、1 を取得して停止します。

この問題の難しさは、ある数字が幸せな数字かどうかを判断することではなく、ある数字が幸せな数字ではないかどうかを判断することです。幸せな数字でない場合は、有限の回数で数字 1 に到達する方法がないことを意味します。では、何回かかりますか? 1k 回、100,000 回? 上限を決定することは困難です。この問題について話す前に、高頻度リンクリストの演習をいくつか見てみましょう。

例1: 配列を使用してリンクリストにループがあるかどうかを判断する

上記では、最後のノードが null を指していることを紹介しましたが、リンクリストの最後のノードが null アドレスではなく、リンクリスト内のノードを指している場合、これはループではないと考えたことはありますか?

リンクリスト

上図に示すように、ノード 8 は 3 を指しているため、3、4、5、6、7、8 のリング構造が形成されます。このとき、ポインタを使用してリンクリストをトラバースすることは決して終わりません。では、サイクルがあるかどうかをどのように判断するのでしょうか?

配列表記法を使用する方法。出現したノード情報を記録し、新しいノードをトラバースするたびに配列内のレコードを確認します。この時間計算量は良くありません。最初のノードの後、配列を 0 回検索し、2 番目のノードでは配列を 1 回検索し、i 番目のノードでは配列を i-1 回検索し、n+1 番目のノードを通過するまで、検索の合計回数は (n + 1) * n / 2 なので、時間の計算量は O(n^2) です。遅すぎるので最適化してください
高速ポインター法と低速ポインター法

2 人の生徒 A と B が走っています。生徒 A は速く、生徒 B は遅いです。彼らはトラックが円形であることを知りません。もし円形であれば、速いランナーはやがて十分な時間内に遅い生徒 B を追い越し、お互いに出会うでしょう。円形でない場合は、速い方が先にポイントに到達し、出会うことはありません---高速ポインターと低速ポインター方式。

高速ポインターと低速ポインター

ここで、リンクリストを、滑走路上に 2 つのポインタがある滑走路と見なします。ポインタ A は毎回 2 ステップ進み、ポインタ B は毎回 2 ステップ進みます。より速いポインタが最初にゴールラインに到達した場合、ループは発生しません。2 つのポインタが出会うと、ループが発生します。

 int hasCycle(構造体Node *head) {
    head == NULLの場合は0 を返します。
    // p は低速ポインタ、q は高速ポインタ
    構造体 Node *p = ヘッド、*q = ヘッド;
    // ループを繰り返すたびに、p は 1 ステップ、q は 2 ステップ実行します。
    する {
            p = p->次へ;
            q = q->次へ;
            q == NULLの場合は0 を返します。
            q = q->次へ;
        } while (p != q && q);
 p == qを返します。
 }

3. 二分探索に関する予備的研究

バイナリ検索といえば、ジョークがあります。

学生の孫さんは図書館に本を借りに行きました。一度に40冊の本を借りました。図書館を出るときに警察に電話しました。どの本が消磁されていないのか分からなかったため、本を地面に置き、1冊ずつ試してみることにしました。

少女の手術は、隣にいた叔母に見られていました。叔母は「あなたって、すごく遅いわね。教えてあげましょう」と言いました。そこで彼女は木を2つの山に分けて、最初の山を取り出してセキュリティチェックに通しました。セキュリティマシンは考えたので、叔母は本の山を2つに分けて、1つを取り出して試行を続けました。このようにして、叔母は毎回本の数を半分ずつ減らし、数回で磁気が消えていない本を見つけました。叔母は誇らしげにこう言った。「お嬢さん、これは本に載っている二分探索アルゴリズムよ。よく勉強しなさい。」翌日、図書館で 39 冊の本が紛失していることが発覚した。ハハハハ

4 二分探索の基礎

最も単純な二分探索アルゴリズムは、順序付けられた配列内に数値 X が存在するかどうかを調べることです。秩序に注意してください。配列内の数字を見つけるにはどうすればよいでしょうか?

最初から最後まで一つずつ検索し、見つかったらその番号xになります

バイナリ検索アルゴリズムは、間隔を決定し、間隔の半分を見つけて x と比較します。間隔が x より大きい場合は、x の最初の半分を検索します。 x より小さい場合は、後半で検索し、結果を決定するのに log2n 回の比較のみが必要になります。

二進法の除算に関する予備的研究

図では、数字 17 の検索を例に挙げています。L と R で囲まれた領域が現在の検索間隔です。最初は、L = 0、R = 6 で、mid は配列の中央の位置を指しています。L と R に基づいて計算された mid の値は 3 です。配列の 3 番目の位置の値は 12 で、検索する値 17 より小さいです。つまり、17 がこの順序付き配列にある場合、mid が指す位置の後にあるはずです。mid が指す数字自体は 17 ではありません。したがって、次回は、mid + 1 から R までの検索間隔を特定できます。つまり、L を mid + 1 (つまり、配列の 4 番目の位置) に調整します。

位置）。

1 初心者のための最初の書き方

int BinarySerach(ベクトル< int >& 数値, int n, intターゲット) {
整数 左= 0、右= n-1;
    （左<=右）{
 int中央 = (左+右)/2;
        if (nums[mid] == target) はmidを返します。
そうでない場合、nums[mid] < target) left = mid + 1;
それ以外 右= 中央 1;
    }
 -1 を返します。
 }

インタビュアーは話した

[[342095]]

方法2 最適化バージョン

右と左を比較すると、2 つの合計がオーバーフローする可能性があります。すると、改善された方法は mid=left+(right-left)/2 になります。さらに最適化を続け、2 で割る演算をビット演算 mid=left+((right-left)>>1) に変換します。

それはそれほど単純ではありません。ほとんどの筆記試験や面接では、次のような状況が発生する可能性があります。

4. 二進除算のさまざまなバリエーション

ここでは主に、元の配列に重複した数字がある状況を見ていきます。

バイナリ

1 指定された値と等しい最初の値を見つける（要素7を見つける）

アイデア

まず、7を中間値a[4]と比較し、7より小さいことがわかったので、5から9まで検索を続けます。中間値a[7]=7ですが、この数字7は初めて現れるわけではありません。次に、この値の前の値が 7 に等しいかどうかを確認します。 7 に等しい場合は、現在の値が 7 の最初の出現ではないことを意味します。このとき、rihgt=mid-1 を更新します。さて、コードを見てみましょう

int BinarySerach(ベクトル< int >& 数値, int n, intターゲット) {
整数 左= 0、右= n-1;
    （左<=右）{
 int中央 =左+ ((右-左)>>1);
        if (nums[mid]>値)
        {
右= 中央 1;
        }そうでなければ (nums[mid]<value)
        {
左= 中央 + 1;
        }それ以外 
        {
            if((mid==0)||(nums[mid-1]!=値))
            {
ミッドに戻ります。
            }それ以外 
            {
左= 中央 1;
            }
        }
 -1 を返します。
 }

2 指定された値に等しい最後の値を見つける

nums[mid]の値がすでに最後の要素であると仮定すると、最後の値を見つける必要があります。 nums[mid] の次の値が value と等しくない場合は、nums[mid] が指定された値と等しい最後の値であることを意味します。

 int BinarySerach(ベクトル< int >& 数値, int n, intターゲット) {
整数 左= 0、右= n-1;
    （左<=右）{
 int中央 =左+ ((右-左)>>1);
        if (nums[mid]>値)
        {
右= 中央 1;
        }そうでなければ (nums[mid]<value)
        {
左= 中央 + 1;
        }それ以外 
        {
            if((mid==n-1)||(nums[mid+1]!=値))
            {
ミッドに戻ります。
            }それ以外 
            {
左= 中央 + 1;
            }
        }
 -1 を返します。
 }

3 指定された値以上となる最初のケースを見つける

nums[mid]が検索する値より小さい場合は、[mid+1,right]の間で検索する必要があるため、left=mid+1に更新します。
nums[mid] が指定された値より大きい場合、nums[mid] が指定された値以上である最初の要素であるかどうかを確認する必要があります。nums[mid] の前に要素がない場合、または前の要素が検索値より小さい場合は、nums[mid] が検索する必要がある値です。それどころか
nums[mid-1]も検索値以上である場合、検索された要素は[left, mid-1]の間にあることを意味するので、rightをmid-1に更新する必要があります。

 int BinarySerach(ベクトル< int >& 数値, int n, intターゲット) {
整数 左= 0、右= n-1;
    （左<=右）{
 int中央 =左+ ((右-左)>>1);
        if (nums[mid]>値)
        {
右= 中央 1;
        }そうでなければ (nums[mid]<value)
        {
左= 中央 + 1;
        }それ以外 
        {
            if((mid==n-1)||(nums[mid+1]!=値))
            {
ミッドに戻ります。
            }それ以外 
            {
左= 中央 + 1;
            }
        }
 -1 を返します。
 }

4 指定された値以上となる最初のケースを見つける

nums[mid]が検索する値より小さい場合は、[mid+1,right]の間で検索する必要があるため、left=mid+1に更新します。
nums[mid] が指定された値より大きい場合、nums[mid] が指定された値以上である最初の要素であるかどうかを確認する必要があります。nums[mid] の前に要素がない場合、または前の要素が検索値より小さい場合は、nums[mid] が検索する必要がある値です。それどころか
nums[mid-1]も検索値以上である場合、検索された要素は[left, mid-1]の間にあることを意味するので、rightをmid-1に更新する必要があります。

 int BinarySerach(ベクトル< int >& 数値, int n, intターゲット) {
整数 左= 0、右= n-1;
    （左<=右）{
 int中央 =左+ ((右-左)>>1);
        if (nums[mid]>=値)
        {
            if(mid==0||nums[mid-1]<値)
            {
ミッドに戻ります。
            }それ以外 
            {
右= 中央 1;
            }
        }それ以外 
        {
左= 中央 + 1;
        }
 -1 を返します。
 }

5 指定された値以下の最後のケースを見つける

nums[mid]が検索する値より小さい場合、検索する値は[mid+1, right]の間にある必要があるため、left=mid+1に更新する必要があります。
nums[mid]が指定された値以上である場合、nums[mid]が指定された値以上である最初の要素であるかどうかを確認します。

 int BinarySerach(ベクトル< int >& 数値, int n, intターゲット) {
整数 左= 0、右= n-1;
    （左<=右）{
 int中央 =左+ ((右-左)>>1);
        if (nums[mid]>値)
        {
右= 中央 1;
        }それ以外 
        {
            if(mid==n-1||(nums[mid+1]>値))
            {
ミッドに戻ります。
            }それ以外 
            {
左= 中央 + 1;
            }
        }
 -1 を返します。
 }

4 キュー

例: スライディングウィンドウの最大値

キューのリコール:

駅で切符を買った経験があると思います。窓口の女性は必ず列の先頭の人に対応します。切符を購入すると、女性は先頭から立ち去ります。後ろの人が前に進み出て、立ち去った人を引き継いで切符を買い続けます。これが典型的な待ち行列の構造です。

コンピュータ内のキューもこれに似ており、先着順、先入先出で、各要素は最後からキューに入り、先頭から処理されてからキューから出ていきます。

キューの定義

単調なキュー

生徒が上級生から下級生へと並んでいると仮定します。時間が経つにつれて、上級生は列の先頭から卒業し、下級生は最後尾から入学します。ほとんどの学校には学校チームがあります。シャオリンが4年生、私が2年生、シャオチーが1年生だとします。シャオリンが卒業したら、私が後継者になります。私が卒業したら、シャオチーが引き継ぐ可能性が非常に高くなります。そして、私がチームに入ると、シャオチーは早く参加したにもかかわらず、彼の戦闘力は私ほど高くないので、シャオチーが選ばれる可能性はありません。したがって、チーム全体を見ると、キューの特性だけでなく、単調性の特性も備えているため、単調なキューです。

なぜ単調なキューが必要なのでしょうか?

より明白な役割は、キューの処理順序における間隔の最大値を維持することです。

頻繁な面接の質問 - スライディングウィンドウの最大値

スライディングウィンドウが 1 つ戻るたびに、キューの先頭から要素が削除され、キューの後ろに要素が追加されます。この質問では、間隔の最大値が必要です。つまり、キューの処理順序における間隔の最大値を維持する必要があるということです。コードとコメントを直接添付してください。

 #定義 MAX_N 1000
 int q[MAX_N + 5]、ヘッド、テール;
 void 間隔最大数( int *a, int n, int m) {
    頭 = 尾 = 0;
 ( int i = 0; i < n; i++)の場合{
        // a[i] がキューに追加され、単調性に違反するものはキュー q から追い出される
        (head < tail && a[q[tail - 1]] < a[i]) の場合、末尾は--;  
        q[tail++] = i; // i がキューに参加します
        // キューの先頭要素がウィンドウ範囲外かどうかを判定する
        i - m == q[head]の場合、head++;
        // 範囲内の最大値を出力する
        (i + 1 >= m)の場合{
            printf( "interval(%d, %d)" , i - m + 1, i);
            printf( " = %d\n" , a[q[head]]);
        }
    }
戻る;
 }

5 スタックとモノトーンスタック

スタック構造はキューに対応しています。スタックは、出口が 1 つしかないバドミントンのチューブとして考えることができます。バドミントンは、1 つの入口からのみ出し入れできます。ボールバケツに 1、2、3 の 3 つのボールを入れたとします。取り出すと、数字は 3、2、1 になります。その性質は非常に明白で、先入後出構造である

スタック構造自体は、完全に包含された関係を維持します。この包含関係は関数間の動作に完全に反映され、つまり包含関係となります。メイン関数が関数 B を呼び出す場合、関数 B はメイン関数が終了する前に必ず終了します。

モノトーンスタック

ここまででスタックとキューについて理解できたと思いますが、スタックとキューの最大の違いは何だと思いますか?

スタックは先入れ後出しで、キューは先入れ先出しであると、ためらうことなく答えることができます。さて、もう一度お聞きしますが、出口がブロックされた単調なキューとスタックの違いは何でしょうか? 違いはないのでしょうか? 単調なキューは、単調性を維持するために、キューに入るときに単調性に違反する要素をポップアウトします。これは、スタックの同じセクションの出入りに相当します。はい、出口がブロックされた単調なキューが、今話していることです。ここでは、単調に減少するスタックを例に挙げます。

モノトーンスタック

シーケンス内の要素番号 12 をスタックにプッシュすると、モノトーンスタックには下から上に 23、18、15、9 の 4 つの要素が含まれるようになり、元のシーケンスに従って 2 5 9 12 になります。この時点では、要素 12 と要素 9 の関係に焦点を当てます。要素 12 がスタックにプッシュされると、スタックの単調減少の性質を保証するために、最終的に要素 9 の上に配置されます。この時点では、10 番目と 11 番目の要素の値はわかりませんが、これら 2 つの要素の値は要素 9 よりも小さくなければなりません。これが単調スタックの特性です。したがって、モノトニックキューはゾーン内の最大値を維持するために使用される効率的な構造であり、モノトニックスタックは最新のより大きい値またはより小さい値を維持するために使用される効率的な構造です。例を見てみましょう

タイトル: 括弧の順序が正当かどうかを判断する

法律上の例

（{}） 
 
 {()}

例は違法です

（[)]
 （（（）{}

パブリックブール値isValid(文字列s) {
        Stack<文字> stack = new Stack<>();
        Map<文字,文字> map = new HashMap<>();
 char [] 文字 = s.toCharArray();
        map.put( ')' , '(' );
        map.put( '}' , '{' );
        map.put( ']' , '[' );
 ( int i=0;i < s.length();i++) {
            if(!map.containsKey(chars[i])) {
                //左括弧の場合はスタックに直接プッシュします
                スタックにスタックをプッシュします。
            }それ以外{
                //右括弧の場合、スタックが空かスタックの先頭が括弧の種類と一致しない場合はfalseを返します 
                if(stack.empty() || map.get(chars[i]) != stack.pop()){
戻る 間違い;
                }
            }
        }
        //文字列の走査が完了したら、スタックが空の場合はtrueを返し、そうでない場合はfalseを返します。  
スタックを空のままにします。
    }

6 再帰ルーチン

再帰についてお話しする前に、まずは密接に関係する数学の原理である包含と排除の原理についてお話ししたいと思います。

数え上げ問題では、数え上げの正確さを保証するために、通常、2 つの点が保証されます。1 つ目の点は重複がないこと、2 つ目の点は省略がないこと、です。比較的言えば、2 番目のポイントは達成しやすいです。例えば、ある地域に爆撃を行うとすれば、その範囲を確保するためには十分な数の爆弾があれば十分ですが、ある土地を一度しか爆撃できないようにすることは困難です。包含排除原則はこの問題を解決します。

包含排除原則とは何ですか?

重複状況を考慮せずに、まずすべてのオブジェクトの数を計算し、重複するものを除外します。はい、計算結果は省略または重複されません。簡単に言うと、計算の過程で、足しすぎた場合は余分な部分を減算し、減らしすぎた場合は、多すぎず少なすぎない程度になるまでいくらか足し戻します。

ウサギの繁殖問題を見てみましょう。

草原に突然現れた異星人のウサギがいたとします。この異星人のウサギは、生後1ヶ月目は赤ちゃんで、2ヶ月目には大人になり、3ヶ月目からは毎月クローンの赤ちゃんウサギを産みます。しかも、この種類のウサギは年を取らず、大人になると出産を続けます。この状況に応じて、

ウサギが少ない？

過去6か月間の状況を見てみましょう

生後6ヶ月のウサギ

上の図から、1 か月目から 6 か月目まで、草原にいるウサギの数はそれぞれ 1 匹、1 匹、2 匹、3 匹、5 匹、8 匹であることがわかります。

6 か月目には、大人のウサギが 5 匹、子ウサギが 3 匹、合計 8 匹のウサギがいます。なぜ大人のウサギが 5 匹いるのでしょうか。6 か月目のウサギの数は 5 か月目のウサギの総数と等しく、6 か月目の子ウサギ 3 匹は 4 か月目のウサギの数と等しいからです。

過去3か月

結論はより明確です。3 か月目から始めて、n か月目のウサギの数は、その月の大人のウサギの数と若いウサギの数の合計に等しくなります。つまり、n-1 か月目のウサギの数と n-2 か月目のウサギの数の合計に等しくなります。前の数字を使用して次の数字を推測するこの状況は、再帰と呼ばれます。では、再帰アルゴリズムルーチンは通常どのようなものなのでしょうか?

再帰の状態を決定し、最初の数ステップの図をさらに描きます。
再帰式の導出
プログラミング

ウサギ問題の解決方法を3つのステップで説明します。

f(n)はnヶ月間のウサギの数を表す
再帰式（1 か月目と 2 か月目のウサギの数は 1 で、3 か月目は前の 2 か月の合計に等しくなります）

再帰式

ケース2: 集金問題

1元、2元、5元、10元、20元、50元、100元をご利用ください

1000元を稼ぐ方法は何通りありますか？

再帰状態を決定するには、独立変数と従属変数を分析する必要があります。2 つの独立変数は、通貨の種類と組み合わせるコインの数であり、従属変数は計画の合計数です。したがって、状態は、j 元のお金を i 種類のコインで組み合わせる計画の合計数である f(i,j) として定義されます。例えば、f[3][10]は3種類の硬貨を使って10元を作る方法の総数です。
3番目の種類のコインを使用しないと仮定すると、これは最初の2種類のコインを使用して10元を作る方法の総数、つまりf[2][10]に相当します。少なくとも1枚の5ドル札が使用される場合、これらの解から1枚の5ドル札が除去され、残る解の数はf[3][5]になります。したがって、再帰式はf[3][10] = f[2][10] + f[3][5]です。これは一般的なケースです。i 番目のコインは使用しないと仮定します。j 元を構成する方法の数は f(i-1,j) であり、これは最初の i-1 枚のコインを使用する方法の総数を表します。残りは i 番目のコインを使用します。各コインには i 番目のコインが 1 つ含まれているため、i 番目のコインの額面を val[i] と仮定すると、最初の i 個のコインを使用して金額 j-val[i] を構成します。解の総数は f(i,j-val[i]) であるため、式は f(i,j)=f(i-1,j)+f(i,j-val[i]) となります。

推論

7 動的プログラミング

動的計画法は通常DP（ダイナミックプログラミング）と呼ばれます。問題の種類に応じて分類すると、線形DP、区間DP、デジタルDPなどに分けられます。動的計画法について話すときはいつでも、最適なサブ構造、重複するサブ問題などを考えます。これらの言葉は苦くて理解しにくいものです。慌てないでください。問題がどんなに難しいものであっても、基本的な問題に基づいて構築され、徐々に分解されます。これも動的計画法の考え方です。次の4つのステップの動的計画法のアプローチと演習の実践を通じて、動的計画法に対する新しい理解が得られると信じています。

4つのステップは、状態定義、状態遷移方程式、正しさの証明、実装に分かれています。

ステータスの定義

実際、上で再帰について話しているとき、すでに状態定義が関わっています。通常、導出のプロセスで、これ以上進めないと感じる場合は、状態定義に問題がある可能性が非常に高くなります。

最初の状態: dp[i][j]は、開始点から(I, j)までの経路の最大値を表します。

2番目の状態: dp[i][j]は、下端の点から(i, j)までの経路の最大値を表します。

状態伝達方程式

上記の 2 つの状態定義は、ここでの 2 つの転送方向に対応します。

州移転プロセス

上図に示すように、dp[i][j]を取得するには、dp|[i-1]|[j-1]とdp[i-1][j]の値を知る必要があります。なぜなら、(i, j)に到達できるのは(i - 1, j - 1)と(i - 1, j)の2点だけであるからである。このときの状態伝達方程式は

最初の状態遷移方程式 dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + val[i][j]

第2巻の状態伝達方程式はdp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + val[i][j]である。

このことから、状態の定義が異なり、伝達方程式も大きく異なることがわかります。

正しさの証明

数学的帰納法では通常 3 段階のアプローチが採用され、正しさを証明するためによく使用される方法が数学的帰納法です。

最初のステップは、最初の段階ですべてのdp値を簡単に取得することです。つまり、dp[1][1]を初期化します。これはval[1][1]に等しいです。

2番目のステップでは、i-1番目のステージのすべての状態値が正しく取得されたと仮定すると、状態方程式dp[i][j]=max(dp[i - 1][j], dp[i - 1][j + 1]) + val[i][j]に従って、i番目のステージのすべての状態値を計算できます。

ステップ3：すべての状態値が正しく計算されていると結論付ける

動的計画法問題における 0/1 ナップサック問題の分析を続けます。動的計画法問題は通常、0/1 ナップサック問題、完全ナップサック問題、多重ナップサック問題の 3 つのカテゴリに分類されます。

0/1 ナップザック問題は、他の 2 つのナップザック問題の基礎です。簡単に説明しましょう。最大荷重が W のナップザックがあるとします。ナップザックには n 個のアイテムがあります。i 番目のアイテムの重量は wi で、値は vi です。ナップザックの重量制限を超えずに取得できるアイテムの合計値の最大値はいくらでしょうか。ここでも、4 段階のアプローチを使用します。

ステータスの定義

まず、バックパック問題における独立変数と従属変数を分析します。従属変数は比較的簡単に決定でき、最大合計値です。独立変数については、ここではアイテムの種類とバックパックの積載量の上限です。この2つは合計値の最大値に影響を与えるため、2次元の状態を設定します。 dp[i][j]は、最初のi個のアイテムが使用され、バックパックの最大負荷がjの場合の最大合計値を表します。

状態方程式

簡単に言えば、dp[i][j]の式であるマッピング関数を見つけることです。 dp[i][j]を2つのカテゴリに分けます。最初のカテゴリはi番目の項目の最大値とを選択しないことであり、2番目のカテゴリはi番目の項目の最大値とを選択することです。次に、2 つの値のうち最大値を選択します。

i番目の項目が選択された場合、このときの最大値はdp[i-1][j-wi]+viです。i番目の項目が選択されているため、位置を確保する必要があります。このとき、残りのi-1個の項目を運ぶスペースはj-wiのみ残っています。このとき、選択されたi-1個の項目の最大値の合計はdp[i-1][j-wi]であり、viを加えると現在の最大値の合計になります。伝達方程式は

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

正しさの証明

まず、dp[0][j]=0は、アイテムがない場合、バックパックの重量がいくらであっても得られる最大値は0であるため、k0は

次に、i-1個の項目の最大値とすべてのdp[i-1]の値を取得したと仮定すると、状態方程式に従って、すべてのdp[i]の値を知ることができます。

最後の2つのステップを組み合わせると、全体のソリューションは任意のdp[i][j]に対して有効になります。

成し遂げる

#定義 MAX_V 10000
 #define max_n 100
 int v [max_n + 5]、w [max_n + 5];
 int dp [max_n + 5] [max_v + 5];
 int get_dp（ int n、 int w）{
    // DP [0]ステージを初期化します
for （ int i = 0; i <= w; i ++）dp [0] [i] = 0;
    // dp [i -1]を保持していると仮定して、dp [i]を計算します
    //状態転送プロセス、私はアイテムを表し、jはバックパックの重量制限を表します
for （ int i = 1; i <= n; i ++）{
 for （ int j = 0; j <= w; j ++）{
        //最大値Ithアイテムを選択しない場合
        dp [i] [j] = dp [i -1] [j];
        // i番目のアイテムの最大値と比較し、更新
        if（j> = w [i] && dp [i] [j] <dp [i -1] [j -w [i]] + v [i]）{
            dp [i] [j] = dp [i -1] [j -w [i]] + v [i];
            }
        }
    }
 dp [n] [w]を返します。
 }

8貪欲

実際、私たちが大学で調査したいくつかのアプリケーションはすべて、ハフマンコーディング、プライム最小スパニングツリーなど、貪欲なアルゴリズムを使用しています。

まず、Meituanからの以前の書面によるテストの質問を見てみましょう - ジャンプ

nのボックスは、右に右にジャンプできることを示しています。

アイデア：自然なアイデアは、最終的に到達できるかどうかを確認して、右から渡された各ボックスから継続的に更新できるかどうかを確認することです。では、通常は貪欲なアルゴリズムの思考プロセスはどのようなものですか？

動的なプログラミングと同様に、大きなものは小さなものに縮小され、小さなものは排除されます。いわゆる大きなものを小さいものに減らすことは、大きな問題や亜精傷の繰り返し部分を見つけ、複雑な問題を小さな問題に分割することを意味します。小さなものを小さなものに変え、小さなものを磨くことでより多くのコア戦略を見つけます。上記の例

キャンディ共有の問題

キャンディーとNの子供がいます。私たちはこれらの子供たちとキャンディーを共有しますが、キャンディーはほとんどなく、多くの子供がいます。

私の質問は、可能な限り多くの子供を満足させるためにキャンディを配布するにはどうすればよいですか？

子供の場合、小さなキャンディーで十分な場合は、大きなキャンディーを使用する必要はありません。
キャンディーのニーズが異なる子供は満足する可能性が高いため、ニーズが小さい子供からキャンディーを配布し始めることができます。
大きなニーズを持つ子供を満足させることは、小さなニーズを持つ子供を満足させるのと同じくらい私たちの期待に貢献するからです。
残りの子供たちからのキャンディーの需要が最も少ない子供を見つけるたびに、彼を満足させることができる最小のキャンディーが彼に与えます。

 #include <iostream>
 #include <vector>
 #include <アルゴリズム>
名前空間 std を使用します。 
 
 
 /*
解決：
双方を横断します。
これにより、要件が一方向に満たされることが保証されます。左ポイントが右のポイントよりも高い場合、右から左に2回目ですが、
左側のキャンディーの数が右側のキャンディーの数にすぎない場合、左側のキャンディーの数は右側 + 1のキャンディーの数に等しく、要件が反対方向に満たされることを保証します。 
 
最後に、各位置にキャンディーの数を合計するだけです。
 */ 
 
 
 int candycount（vector <int> ＆ rating）{ 
 
 int res = 0;
    //子供の総数
int n = rating.size （ ）; 
 
    //キャンディコレクション
    Vector <int>キャンディ（n、1）;
    //左から右にトラバース
( int i = 0; i < n - 1; i++) {
        if（rating [i + 1]> rating [i]）candy [i + 1] = candy [i] + 1;
    }
    //右から左に
for （ int i = n -1; i> 0; i -）{  
        if（rating [i -1]> rating [i] && candy [i -1] <= candy [i]）
            キャンディ[i -1] =キャンディ[i] + 1;
    } 
 
    //結果を蓄積します
for （auto a：キャンディ）{
        res += a;
    } 
 
 resを返します。
 }
 //テスト関数
int main（）{ 
 
    Vector <int> rating {1,3,2,1,4,5,2};
    cout << candycount（rating）<< endl;
 0を返します。
 }