データ構造フレームワークの考え方を理解すると、すべてのアルゴリズムは単なる張り子の虎に過ぎない

1. データ構造の保存方法

データ構造を保存する方法は、配列 (順次ストレージ) とリンク リスト (リンク ストレージ) の 2 つだけです。

この文章をどう理解しますか？ハッシュテーブル、スタック、キュー、ヒープ、ツリー、グラフなど、さまざまなデータ構造があるのではないでしょうか？

問題を分析するときは、上から下へ、抽象から具体的へと再帰的に考える必要があります。冒頭で非常に多くの項目を列挙しましたが、それらはすべて「上部構造」に属し、配列とリンクリストは「構造的基盤」です。なぜなら、それらの多様なデータ構造は、そのソースでは、異なる API を持つリンク リストまたは配列に対する特別な操作だからです。

たとえば、「キュー」と「スタック」という 2 つのデータ構造は、リンク リストまたは配列のいずれかを使用して実装できます。配列を使用して実装する場合は、拡張と縮小の問題に対処する必要があります。リンク リストを使用して実装する場合は、そのような問題は発生しませんが、ノード ポインターを格納するためにより多くのメモリ領域が必要になります。

「グラフ」を表現する方法は2つあります。隣接リストはリンクリストであり、隣接行列は2次元配列です。隣接行列は接続性を素早く判断し、行列演算を実行していくつかの問題を解決できますが、グラフが疎な場合は非常に多くのスペースを消費します。隣接リストはスペースを節約しますが、多くの操作の効率は隣接行列ほど良くありません。

「ハッシュ テーブル」は、ハッシュ関数を通じてキーを大きな配列にマッピングします。また、ハッシュ競合を解決する方法としては、ジッパー方式はリンクリストの特性が必要で操作が簡単ですが、ポインタを格納するための余分なスペースが必要です。リニアプローブ方式は連続アドレス指定のために配列の特性が必要でポインタ格納スペースは必要ありませんが、操作が少し複雑になります。

「ツリー」は、配列で実装された場合は「ヒープ」になります。これは、 「ヒープ」が完全なバイナリ ツリーであり、配列のストレージにノード ポインターが不要で、操作が比較的簡単であるためです。リンク リストで実装された「ツリー」は非常に一般的な「ツリー」ですが、必ずしも完全なバイナリ ツリーではないため、配列のストレージには適していません。このため、さまざまな問題に対処するために、このリンクリストの「ツリー」構造に基づいて、バイナリ検索ツリー、AVL ツリー、赤黒ツリー、間隔ツリー、B ツリーなどのさまざまな独創的な設計が派生してきました。

Redis データベースに詳しい方は、Redis がリスト、文字列、セットなどのいくつかの一般的なデータ構造を提供しているが、各データ構造には少なくとも 2 つの基礎となるストレージ方法があり、保存されたデータの実際の状況に応じて適切なストレージ方法を使用できることもご存知でしょう。

まとめると、データ構造には多くの種類があり、独自のデータ構造を発明することもできますが、基礎となるストレージは配列またはリンク リストにすぎません。2 つの利点と欠点は次のとおりです。

配列はコンパクトで連続したストレージであるため、ランダムにアクセスでき、対応する要素はインデックスを通じてすばやく見つけることができ、比較的ストレージスペースを節約できます。しかし、連続ストレージのため、メモリ空間は一度に割り当てる必要があります。そのため、配列を拡張する必要がある場合は、より大きな空間を再割り当てしてから、すべてのデータをコピーする必要があります。時間の計算量は O(N) です。また、配列の途中で挿入または削除を行う場合は、連続性を維持するために、その後ろにあるすべてのデータをそのたびに移動する必要があります。時間の計算量は O(N) です。

リンクリストの要素は連続しておらず、次の要素の位置を指すポインタに依存しているため、配列の拡張の問題はありません。要素の前後の要素がわかっている場合は、ポインタを操作して要素を削除したり、新しい要素を挿入したりすることができ、時間の計算量は O(1) です。ただし、記憶領域が連続していないため、インデックスに基づいて対応する要素のアドレスを計算することができず、ランダムアクセスが不可能になります。また、各要素には前後の要素の位置へのポインターを格納する必要があるため、比較的多くの記憶領域を消費します。

2. データ構造の基本操作

どのデータ構造でも、基本的な操作はトラバーサル + アクセス、より具体的には追加、削除、クエリ、変更のみです。

データ構造には多くの種類がありますが、その目的は、さまざまなアプリケーション シナリオで可能な限り効率的にデータを追加、削除、照会、変更することです。これがデータ構造の使命ではないでしょうか?

どのようにトラバース + 訪問するのでしょうか? 依然として最高レベルから見ていきます。さまざまなデータ構造のトラバース + 訪問は、線形と非線形の 2 つの形式にすぎません。

線形性は for/while 反復によって表され、非線形性は再帰によって表されます。具体的には、フレームワークはいくつかあります。

配列トラバーサル フレームワーク、典型的な線形反復構造:

 void traverse( int [] arr) { for ( int i = 0; i < arr.length; i++) { // arr[i] を反復処理する }}

反復構造と再帰構造の両方を備えたリンク リスト トラバーサル フレームワーク:

 /* 基本的な単一リンクリストノード */ class ListNode { int val; ListNode next ;}
 void traverse(ListNode head) { for (ListNode p = head; p != null ; p = p.next ) { // p.val を反復処理する }}
 void traverse(ListNode head) { // 再帰アクセス head.val traverse(head. next );}

バイナリ ツリー トラバーサル フレームワーク、典型的な非線形再帰トラバーサル構造:

 /* 基本的なバイナリツリーノード */ class TreeNode { int val; TreeNode left , right ;}
 void traverse(TreeNode ルート) { traverse( root.left ); traverse( root.right );}

二分木と連結リストの再帰的トラバーサル方法を見てみましょう。それらは似ていますか? 二分木の構造と単一連結リストの構造を見てみましょう。それらは似ていますか? フォークがさらにある場合、N 項木をトラバースできますか?

バイナリ ツリー フレームワークは、N 項ツリー トラバーサル フレームワークに拡張できます。

 /* 基本的な N 項ツリーノード */ class TreeNode { int val; TreeNode[] children;}
 void traverse(TreeNode root) { for (TreeNode child : root.children) traverse(child);}

グラフは複数の N 進木の組み合わせであるため、N 進木の走査はグラフの走査に拡張できます。グラフにサイクルが存在する可能性があるとおっしゃいましたね。これは簡単にできます。マークするには、ブール配列の visits を使用するだけです。ここではコードは書きません。

いわゆるフレームワークとはルーチンのことです。これらのコードは、追加、削除、チェック、変更にかかわらず、絶対に逸脱できない構造です。この構造をアウトラインとして使用し、特定の問題に基づいてフレームワークにコードを追加することができます。具体的な例を以下に示します。

3. アルゴリズム問題練習ガイド

まず明確にしておきたいのは、データ構造はツールであり、アルゴリズムは適切なツールを使用して特定の問題を解決する方法であるということです。つまり、アルゴリズムを学ぶ前に、少なくともよく使われるデータ構造を理解し、その特徴や欠陥を理解しておく必要があります。

では、LeetCode でどのように質問を練習するのでしょうか? アルゴリズムの学習への道に関する以前の記事で、タグや永続化による練習などについて少し書きました。この記事からほぼ1年が経過した今、私はそのような些細な言葉を言うのではなく、具体的な提案を直接述べたいと思います。

• まずバイナリ ツリーをブラッシングします。まずバイナリ ツリーをブラッシングします。まずバイナリ ツリーをブラッシングします。

これは、1 年間問題を練習した後の私の個人的な経験です。次の画像は、昨年 10 月に私が提出した問題のスクリーンショットです。

公開アカウント記事のデータを読むと、ほとんどの人がデータ構造に関連するアルゴリズムの記事には興味がなく、むしろ動的ルール、バックトラッキング、分割統治法などのテクニックに興味を持っていることがわかります。なぜ最初にバイナリ ツリーをブラウズする必要があるのでしょうか。バイナリ ツリーはフレームワーク思考を養うのが最も簡単で、ほとんどのアルゴリズム手法は本質的にツリー トラバーサルの問題であるためです。

バイナリ ツリーの問題を解決する方法がわかりませんか? 多くの読者からの質問によると、誰もがわからないわけではなく、「フレームワーク」の意味を理解していないだけだそうです。これらの数行の壊れたコードを過小評価しないでください。ほとんどすべてのバイナリ ツリーの問題は、このフレームワークで解決できます。

 void traverse(TreeNode root) { // 先順トラバーサル traverse(root.left ) // 順順トラバーサル traverse(root.right ) // 後順トラバーサル}

たとえば、いくつかの問題に対する解決策をランダムに選びます。具体的なコード ロジックについて心配する必要はなく、フレームワークがその中でどのような役割を果たしているかだけを見てください。

LeetCode 124、難易度 Hard では、バイナリ ツリーの最大パスの合計を求めます。メイン コードは次のとおりです。

 int ans = INT_MIN; int oneSideMax(TreeNode* root) { if (root ==
 nullptr) 0を返す; int  左=最大(0、oneSideMax(ルート->左));
整数  right = max (0, oneSideMax(root-> right )); ans = max (ans, left   
 +右+ ルート->val);戻り  max (左、右) + ルート->val;}

ご存知のとおり、これは後順トラバーサルです。

LeetCode 105 (中程度の難易度) では、先行順トラバーサルと順序順トラバーサルの結果に基づいてバイナリ ツリーを復元することが求められます。これは古典的な問題です。メイン コードは次のとおりです。

 TreeNode buildTree( int [] preorder, int preStart, int preEnd, int [] inorder, int inStart, int inEnd, Map< Integer , Integer > inMap) {
    if(preStart > preEnd || inStart > inEnd)戻り値 ヌル;
    TreeNode ルート = new TreeNode(preorder[preStart]); int inRoot = inMap.get(root.val); int numsLeft = inRoot - inStart;
    root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, inorder, inStart, inRoot - 1, inMap); root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, inorder, inRoot + 1, inEnd, inMap); return root;}

この関数には多くのパラメータがありますが、それに惑わされないでください。それらは配列のインデックスを制御するためだけのものです。本質的には、このアルゴリズムは事前順序走査です。

LeetCode 99、難易度 Hard、BST を復元します。主なコードは次のとおりです。

 void traverse(TreeNode* node) { if (!node) return ;
 traverse(node-> left ); if (node->val < prev->val) { s = (s
 == NULL ) ? prev : s; t = ノード; } prev = ノード;
トラバース(ノード->右);}

これは単なる順序通りのトラバーサルではないでしょうか? BST にとって順序通りのトラバーサルが何を意味するのかを説明する必要はないでしょう。

ほら、ハードレベルの質問はまさにこれと同じで、とても規則的です。フレームワークを書き出して、対応する位置に物事を追加するだけです。それがアイデアではないですか?

二分木を理解している人にとって、二分木の問題を解決するのにそれほど時間はかかりません。さて、どこから始めたらよいかわからない場合や、質問するのが怖い場合は、バイナリ ツリーから始めるのがよいでしょう。最初の 10 問は少し難しいかもしれませんが、フレームワークを使用してさらに 20 問を解くと、ある程度理解できるようになります。トピック全体を終えて、バックトラッキングの動的分割統治トピックを実行すると、問題に再帰が含まれる限り、すべてツリーの問題であることがわかります。

以前の記事で取り上げた例と質問をいくつか挙げてみましょう。

動的プログラミングの詳細な説明: 小銭を補う問題の場合、力ずくの解決法は N 項ツリーをトラバースすることです。

 def coinChange(コイン: List[ int ], 量: int ):
    def dp(n): n == 0 の場合: 0を返すn < 0 の場合: -1を返す
        res = float ( 'INF' ) for coin in coins: subproblem = dp(n - coin) # サブ問題に解がないのでスキップ、subproblem == -1 の場合は続行res = min (res, 1 + subproblem) resを返す、 res != float ( 'INF' )の場合は続行、 else -1
 dp(金額)を返す

理解できないコードが多すぎる場合はどうすればいいでしょうか? フレームワークを抽出するだけで、コアとなるアイデアがわかります。

 # これは単に N 項木の走査問題です。 def dp(n): for coin in coins: dp(n - coin)

実際、多くの動的プログラミングの問題はツリーのトラバースに関するものです。ツリーのトラバース操作に精通していれば、少なくともアイデアをコードに変換する方法を知っていることになりますし、他の人のソリューションの核となるアイデアを抽出する方法も知っていることになります。

バックトラッキング アルゴリズムを見てみましょう。バックトラッキング アルゴリズムのこれまでの詳細な説明では、バックトラッキング アルゴリズムは例外なく N 項ツリーの前方および後方のトラバーサルの問題であると簡単に述べました。

たとえば、N クイーン問題の場合、メイン コードは次のようになります。

 void バックトラック( int [] nums, LinkedList< Integer > track) {
  トラックサイズ() == 数値の長さ)の場合{
    res.add (新しいLinkedList(トラック));
戻る;
  }
 for ( int i = 0; i < nums.length; i++) { if (track. contains (nums[i])) continue ; track. add (nums[i]); // 決定木の次の層に入る backtrack(nums, track); track.removeLast(); }
 /* N 項木トラバーサル フレームワークを抽出します */ void backtrack( int [] nums, LinkedList< Integer > track) { for ( int i = 0; i < nums.length; i++) { backtrack(nums, track);}

N分木の走査フレームワークが見つかりました。木構造は重要だと思いますか?

要約すると、アルゴリズムを恐れている人は、まずツリー関連の質問を練習し、詳細にこだわるのではなく、フレームワークの観点から問題を検討してみるとよいでしょう。

i を n に追加するか n - 1 に追加するか、配列のサイズを n にするか n + 1 にするかなど、細かい点が気になりますか?

フレームワークの観点から問題を見るということは、私たちが行うようにフレームワークに基づいて抽出および拡張することを意味します。これは、他の人のソリューションを見るときにコアロジックをすばやく理解するのに役立つだけでなく、独自のソリューションを作成するときに思考の方向性を見つけるのにも役立ちます。

もちろん、詳細が間違っていれば正しい答えは得られませんが、枠組みさえあれば方向性は正しいので、大きく間違えることはありません。

しかし、フレームワークを念頭に置いていないと、問題をまったく解決できません。答えが与えられたとしても、これがツリートラバーサルの問題であることに気付かないでしょう。

こういった考え方はとても重要です。動的計画法の詳しい説明では、状態遷移方程式を求めるためのいくつかのステップがまとめられています。そのプロセスに沿って解を書き出すこともあります。正直、なぜそれが正しいのかはわかりませんが、とにかく正しいのです。 。 。

これがフレームワークの力であり、これにより、眠りに落ちそうになっても正しいプログラムを記述できることが保証されます。何も知らなくても、他の人よりも 1 レベル高いレベルに到達できます。

4. 結論

データ構造の基本的な保存方法は、チェーンとシーケンシャルです。基本的な操作は、追加、削除、クエリ、変更です。トラバーサル方法は、反復と再帰です。

アルゴリズムの問​​題を練習するときは、「ツリー」カテゴリから始めて、フレームワークの思考を組み合わせて、これらの数十の問題を終えることをお勧めします。ツリー構造をよく理解する必要があります。この時点で、バックトラッキング、動的ルール、分割統治などのアルゴリズムのトピックを読んで、アイデアをより深く理解することができます。