LeetCode の優れたソリューション
1.0.0
このドキュメントでは、アルゴリズムとデータ構造の問題に対する初心者向けのチュートリアルとビデオ ソリューションを提供するリソースである LeetCode-Solutions-in-Good-Style の包括的な概要を説明します。これは、明確なコードと詳細な説明による構造化されたアプローチを特徴とし、構築に重点を置いています。競合コーディングではなく、基本的な概念をしっかりと理解する必要があります。
LeetCode-Good-Style ソリューション
説明: ほとんどのクラスメートと同じように、私も勉強と要約を同時に行っています。これからも皆様に役立つ知識を提供していきたいと思いますので、今後ともよろしくお願いいたします。
皆さんこんにちは。これは「アルゴリズムとデータ構造」に関する入門レベルのチュートリアルです。アルゴリズムの基礎がまったくない学生や、キャリアを変えた学生に適しています。アルゴリズム コンテストの準備には適していません。私が伝えたいのは、明確なロジックでコードを書くということです。そのため、私が書くコードは非常に標準的な形式であり、個人的なスタイルはなく、削減のために空行やコメントは書きません。コードの行数。ここにあります：
ウェイウェイと呼んでください。私の能力と時間の許す限り、私の知っている質問に全力でお答えします。時間内に回答できない質問がある場合は、サイト上の通知が表示されなかった可能性がありますので、[email protected] までメールをお送りください。
録画したビデオソリューション
2019 年 9 月にビデオ ソリューションの録画を開始しました。最初は話したい内容を何度か録音していました。知識ポイントを説明するときは、そのまま草案を書きましょう。たくさんのビデオが蓄積されていますが、実際には小さな体系的なコースですので、皆さんのお役に立てれば幸いです。
0. アルゴリズムの初心者はどのように LeetCode を使用できますか? 【有益な情報の共有】
1. 時間計算量と空間計算量
このビデオでは、時間計算量は漸近的な概念であり、動的な観点から理解する必要があると述べています。そして、時間計算量の厳密な定義（極限形式）を説明し、誰もが時間計算量の計算規則を理解できるようにします。また、時間計算量はプログラムの実行時間ではなく、「時間のためのスペース」を使用する必要があり、「時間計算量」の最適化にもっと注意を払う必要があると指摘しています。
2.二分探索
このビデオでは、二分探索アルゴリズムの作成方法を紹介します。二分探索については詳細がたくさんありますが、正しい問題解決のアイデアを習得し、より練習し、熱心に考え、より多くの要約を作成する限り、二分探索の問題は解決されません。長くは困難があります。
次のビデオでは、二分探索のいくつかの質問例を説明しています。質問の意味を分析し、質問に指定された条件を使用して徐々に検索範囲を絞り込む方法に焦点を当てています。
「リコウ」の質問 4 (2 つの正の次数の配列の中央値を求める) の分析を通じて、このテクニックを紹介しました。探しているターゲット要素のプロパティがより複雑な場合は、このプロパティを反転できます。 、そして問題の範囲を簡単に減らすことができる論理ステートメントを作成します。
3. 仕分けに関する問題
「マージソート」と「クイックソート」は、「再帰的」関数の動作メカニズムを理解する上で非常に重要なソートアルゴリズムであると同時に、「分割統治」思考の典型的な応用例でもあります。 」。 「逆順ペア」や「オランダ国旗問題（色分類）」も非常に古典的なアルゴリズム問題です。
「逆順ペア」の計算は完全に「マージソート」の考え方に基づいています。
「色の分類」問題の説明で「ループ不変式」を皆さんに紹介しましたが、コードを書く過程では、「プログラムの実行前」と「実行中」に使用される変数のセマンティクスを常に遵守する必要があります。 「実行終了」後も変更されません。 「ループ不変式」の独自の定義に従うことは、正しいコードを書くための重要な方法です。
「最初に欠けている正の数」は、古典的なアルゴリズムの問題であり、使用されるアイデアは「インプレース ハッシュ」です。これは、「バケツ ソート」アルゴリズムの特別な応用として理解できます。つまり、ニンジン 1 つ、種 1 つ、バケツ 1 つです。要素を保存します。これを実行できるという事実は、入力配列の要素の値と密接に関係していることを強調したいと思います。
4. 引き違い窓
「スライディング ウィンドウ」問題は、「ループ不変条件」を適用することで解決される典型的な問題であり、コーディングとデバッグの能力がテストされます。
5. スタック関連の問題
「スタック」を使用して問題を解決するには、特定の例を使用して、問題の解決が「後入れ先出し」ルールと一致することを確認する必要があります。
次の 2 つの質問をマスターするには、具体的な例を学習し、一般的なルールを要約することが不可欠です。
「スタック」の最も広く使用されているアプリケーションの 1 つは、「再帰」、「深さ優先トラバーサル」、および「分割統治アルゴリズム」のデータ構造サポートとしてです。
6. 複合検索
データ構造「Union Search Set」は、現在、面接で使用されることはほとんどありません。アルゴリズム面接の準備をしている場合は、スキップしても問題ありません。
7. 木
ツリーの問題の多くは、「深さ優先トラバーサル」または「幅優先トラバーサル」を使用して解決できます。
8. バックトラッキングアルゴリズム
「バックトラッキング アルゴリズム」は、実際には、質問に含まれる「ツリー構造」の深さ優先のトラバースです。この種の問題を解くときは、メモ用紙にツリー構造図を描くことが重要です。
9. 動的プログラミング
10. 幅優先トラバーサルとトポロジカルソート
11. ハッシュテーブル
12. ビット演算関連
私の個人的なウェブサイトとアルゴリズムの勉強メモ
WeChatグループとQQグループ
一緒に質問に取り組む友達が必要な場合は、WeChat グループや QQ グループに参加できます。
マイリートブック
これは私自身への宣伝です。私は最近、「LeetBook」で独自の LeetBook を立ち上げました。これは、主に転職した友人向けです。アルゴリズムとデータ構造の基礎知識を説明します。
例証します:
LeetBook の最初の 2 章 (時間計算量、二分探索) は無料で読めます。次の章は有料です。非会員価格は 99 元です。現在ご覧のホームページ ディレクトリは次のとおりです。 LeetBook と同じ、追加部分のみ。
LeetBook のコース タイトル、サンプル、演習、およびサポート コード リポジトリ (現在表示されているリポジトリ) は完全に公開されており、LeetBook で設計されたコンテンツ (演習を含む) をすでに習得している場合は、購入することはお勧めできません。
投資するエネルギーは通常のソリューションを作成する場合と同じですが、LeetBook ではチャートの作成がより詳細になります。有料コンテンツは、チュートリアルの作成に時間と労力を費やし、「Likko」のスタッフや専門家が制作とレビューに参加することで、より良い読書体験を提供します。私が通常、LeetBook よりも多くの問題解決に関する知識ポイントを書いている可能性は否定できません。
中級者および上級者は注意して購入してください。
「Likou」サイトや私の他のソーシャルアカウントでコースの内容について相談したり、このウェアハウスに問題を送信したりできます。コースを購入するかどうかに関係なく、私が知っている質問には（時間の許す限り、私の能力の範囲内で）全力で答えるつもりです。皆様、これからも私を応援していただきありがとうございます。提案や意見がある場合は、どなたでも私とコミュニケーションを取ることを歓迎します。
私が説明する知識は、私がみんなに勧めた書籍、私が書いたブログ、問題解決策、メモに含まれており、公開された問題解決策、ブログ、メモは、時間とエネルギーがある限り常に共有されます。今後も共有と Q&A を行っていきます。
講座受講の機会を与えていただき、小さな願いを叶えてくれた「リコウ」さんにとても感謝しています。
「Le Kou」の分類と問題解決ディレクトリ (LeetBook の章に従って配置されており、第 16 章以降は現在 LeetBook に収録されていない章です)
注: 質問のカテゴリは、私の LeetBook の章に対応しています。
第 1 章 時間計算量
このパートでは、時間計算量の概念を紹介します。[ビデオ解説]を完全に無料で視聴できます。 この章には演習はありません。
第 2 章 二分探索
質問タイプ 1: 2 つの点の添字を求めます
例証します:
練習する：
質問タイプ 2: 2 点による範囲の整数を求めます (2 点回答)
アルゴリズム的思考: 削減と克服。質問が整数を見つける必要があり、その整数が特定の範囲を持っている場合、二分探索によって範囲を徐々に狭め、最終的に数値に近づけることができます。
問題種類3：複素判別関数（最大化問題）
注：このタイプの問題は基本的に「質問タイプ 2」（2 点回答）ですが、初めて学習する場合は少し混乱するかもしれません。このタイプの質問も同様に質問されます。キーワードは「連続」と「正の整数」です。このような重要な情報を質問に含めるように注意してください。
第 3 章 基本的な並べ替えアルゴリズム
この部分には、選択ソート、挿入ソート、ヒル ソート、バブル ソートの 4 つの基本的なソート アルゴリズムが含まれています。
「リコウ」問題 912: ソート配列の解答: ソート問題の重要なポイントと学習教材をまとめています。ソート問題からアルゴリズムの学習を始めることができます。
配列問題は、プログラミング言語の基礎知識を習得するだけで完成できるため、アルゴリズムの「初心者分野」として活用できます。関連するデータ構造やアルゴリズムの知識を学んでいなくても、次の問題の解決策を考えるのは簡単です。
知識ポイント: ループの不変条件
第 4 章 高度な並べ替えアルゴリズム (重要)
この部分では、マージ ソート、クイック ソート、ヒープ ソートという 3 つの高度なソート アルゴリズムを習得することに重点を置く必要があります。
例証します:
第 5 章 非比較ソート (オプション)
この部分には、カウント ソート、基数ソート、バケット ソートの 3 種類の非比較ソートが含まれています。これらの問題を解決するには、インプレース ハッシュの概念を理解する必要があります。
第 6 章 スライディング ウィンドウとデュアル ポインタ
1. 引き違い窓
スライディング ウィンドウの参考記述方法 (テンプレートではありません。そのままコピーしないでください。参考用です。アルゴリズムの設計思想を理解することがより重要です):
注意: 質問 3 と 76 は、必ず解けなければならない基本的な質問です。上記の質問を完全に理解すると、次の質問に簡単に答えることができます。
主な質問:
例証します:
練習する：
例証します:
質問 209: 質問で与えられた重要な情報: 配列内のすべての要素は正の整数です。方法は以下の合計3通りあります。
方法 1: 暴力的な解決策
方法 2: スライディング ウィンドウ (スライディング ウィンドウが使用できる理由を分析する)
方法 3: プレフィックスと配列を構築し、二分検索を使用する
質問 438: 質問 76 と同じ。
問題 567: 修飾文のコレクションが異なることを除いて、問題 76 と同じです。
2. ダブルポインター
「ダブル ポインタ」問題は、実際には問題の意味を満たさない多くの解決策を最適化したものです。これは「スライディング ウィンドウ」手法にも当てはまります。ダブル ポインターが使用できる理由を分析することがさらに重要です。
添え字を見つけるために使用される二分探索アルゴリズムは、ダブル ポインター ソリューションと考えることもできます。
第7章 リンクリスト
連結リストの問題を解決するための非常に実用的なテクニックは「描画」です。他のアルゴリズム問題の分析と説明（面接官への説明）も同様です。
デバッグを容易にするために、リンク リストのテスト関数を作成できます。推奨される実装方法は次のとおりです: ① 配列を通じて単一リンク リストを作成する; ② 現在のノードと、現在のノードに基づいて後続のノードを出力します。これら 2 つの方法は、リンク リストに関連するプログラムをデバッグするのに非常に便利です。
質問タイプ 1: 基本的なリンク リスト ポインタの指示問題
注: 一部の問題では、リンク リストの最初のノードに対する複雑な分類ディスカッション ロジックを回避するために、「仮想ヘッド ノード」の使用が必要になります。このアイデアは、「センチネル」と呼ばれる配列で見られました。
再帰関数を使用すると、ポインター変数を変更する複雑な操作が回避され、問題の解決が簡単になります。
例証します:
質問タイプ 2: 速いポインター スキルと遅いポインター スキル
正確には「同期ポインタ」と言った方が良いかもしれません。
2 つのポインター変数を使用すると、それらは両方とも先頭のリンク リストの最初のノードに配置されます。一方は常に一度に 1 つのステップのみを実行し、もう一方は常に一度に 2 つのステップのみを実行します (1 つは前に、もう 1 つは後ろにあります)。同時に戻ります。このようにして、高速ポインタが歩き終わると、低速ポインタはリンクされたリストの中央の位置に到達します。
これらの問題を解決する共通の機能は、2 つのポインター変数を使用して同期的に移動することです。速いポインタと遅いポインタは同じ方向に移動し、それらのステップ間の「差」は一定です。この確実性に基づいて、リンクされたリストのいくつかの問題を解決できます。このアイデアを使用すると、リンク リストの次の問題も解決できます。
例証します:
質問タイプ 3: データ構造の設計
第 8 章 スタックとキュー
1.スタック
質問タイプ 1: スタックを使用して解決される基本的な問題
次の質問は非常に基本的なものなので、マスターする必要があります。
練習する：
質問タイプ 2: 単調なスタック
単調スタックは通常のスタックであり、使用中に偶然「後入れ先出し」の原則に準拠し、スタック内の要素は単調です。 「モノトーン スタック」と「モノトーン キュー」の問題は通常、非常に特殊です。例題と演習をマスターするだけです。
経験: 添字は通常、単調スタックに格納されます。
例証します:
練習する：
2. キュー
質問タイプ 1: キューを使用して解決される基本的な問題
すべての問題は、幅優先トラバーサル使用キューを使用して解決されます。
質問タイプ 2: 単調なキュー
単調キューは単なる通常のキューです。この問題は現在、「Likou」の単調キューで見つかっています。重要なのは、設計されたアルゴリズムがなぜキューを単調にしてしまうのかを明確に分析することです。さらに、「ナップザック問題」には単調キューを使用した最適化の例があり、興味のある人はそれについて学ぶことができます。これは競争上の知識です。
経験: 添字は通常、単調なキューに保存されます。
第9章 プライオリティキュー
注: ヒープをより効果的に使用するためには、remove() と replace() のコーディングの詳細を理解するのに役立ちます。
アプリケーション: 「動的」の意味を理解することに重点を置き、現在のキュー内で最も優先度の高い要素を動的に選択します。
第 10 章: 結合検索
そして、問題990の動画解答で知識ポイントの【動画解説】を確認してください。基本的でよくある質問には次のようなものがあります。
オプションの質問:
第11章 木（二分木と二分探索木）
第 12 章 バックトラッキングアルゴリズム
質問タイプ 1: 基本的なバックトラッキング問題
これらの質問を通じて、バックトラッキング アルゴリズムの考え方を理解することができます。バックトラッキング アルゴリズムの知識ポイントは、「リコウ」の質問 46 のビデオ解答とテキスト解答で説明されています。
バックトラッキングとは、深さ優先トラバーサルを使用してツリー (グラフ) のすべての解を検索することです。深さ優先トラバーサルには明らかな再帰構造があります。
次の問題を解決するためのヒント: ① 描画、描画、② 深さ優先トラバースと再帰を理解する、③ もっとデバッグする、もっとデバッグする。
質問タイプ 2: 文字列のバックトラッキング問題
理解すべき重要なポイント: 文字列は毎回新しい文字を生成するため、状態をリセットする必要はありません。
質問タイプ 3: フラッド フィル
質問タイプ 4: ゲームに関する質問
例証します:
第 13 章 動的プログラミング (パート 1)
動的プログラミングの 2 つの重要な考え方:
動的プログラミングにおける 2 つの考え方:
動的プログラミングを使用して問題を解決するには、次の 3 つの条件を満たす必要があります。
動的プログラミングの 2 つの重要な概念:
質問分類の参照:
※以下の代表的な質問を追加します（2020年12月2日）。
1. はじめに
「トップダウン」メモリ再帰と「ボトムアップ」再帰という 2 つの動的プログラミング手法を理解します。
2. 繰り返されるサブ問題
この部分では、「歩数カウント乗算原理」と「カテゴリカルカウント加算原理」を使用する必要があります。
質問 70: これはフィボナッチ数と同じ質問です。計数の問題では、分類計数の原則と歩数計数の原則が使用されます。
3. 最適な下部構造
例証します:
質問 377: スクリーニングはバックパックの問題ではないことに注意してください。
4. 後遺症がない
練習する：
以下に、古典的な「動的プログラミング」の問題をいくつか示します。これらの問題は非常に重要であるため、別のカテゴリに含まれています。
5. 最大サブセグメント合計
練習する：
6. 最長の上昇サブシーケンス
注: 質問 300 は、非常に古典的な動的計画法の問題です。 $O(N log N)$ の解は、問題自体の特性に従って状態を定義し、状態配列が順序付けられた配列であることを証明するため、時間の複雑さが軽減されます。
練習する：
7. 最長の共通部分文字列
8. インターバル DP とパーティション DP
インターバルDP:
パーティション分割された DP:
9. ツリーDP
第 14 章 動的プログラミング (パート 2)
1. バックパックの問題
バックパックに関する 9 つの講義: https://github.com/tianyicui/pack
（「ゲームタイプDP」「ステート圧縮DP」「デジタルDP」等が追加されます。）
その他の質問
第15章 貪欲なアルゴリズム
第 17 章 ハッシュテーブル
第 18 章 プレフィックスの合計とハッシュ テーブル
第 19 章 幅優先トラバーサル
ツリーの幅優先トラバースに関するいくつかの問題と、LeetBook におけるいくつかの問題。
第20章 グラフ理論アルゴリズム（最小スパニングツリー）
第21章 グラフ理論アルゴリズム（単一ソース最短パス）
第 22 章 分割統治アルゴリズム
分割統治 (分割統治) の考え方は、より大きな問題を同じタイプのいくつかの小さなサブ問題に分割し、各サブ問題が完了した後でこれらのサブ問題を再帰的に解決します。本来の問題が得られます。
分割統治アルゴリズムは並列実行できますが、基本アルゴリズムの分野では、分割統治アルゴリズムは深さ優先のトラバーサル方式で実行されます。
分割統治の考え方を適用する典型的なアルゴリズム: マージ ソート、クイック ソート。
分割統治思考の典型的な問題: 「剣の質問 51 はオファーを指します」: 「剣の質問 51 はオファーを指します」 51. 配列内のペアを逆順に並べます (ビデオ説明)。
その他のよくある質問（追加予定）
今後も更新され続けますので、お友達からの貴重なフィードバックをお待ちしております。
