毎日1題のLeetCode+アルゴリズム

2394 ワード
Python アルゴリズム github データ構造 lettecode
まずgithubのreademeで完了し、定期的にblogに更新します.
LeetCode
リンクはleetcodeアドレスです.
  • 1. Two Sum辞書
  • 171. Excel Sheet Column Number asciiコード、26進
  • 617. Merge Two Binary Trees再帰
    • アルゴリズムとデータ構造
    8大ソート、/sort/basic_sort.py、ここでも1つの文章を推薦して、視覚的にソートアルゴリズムを感じることができますが、図を見るといいです.アルゴリズムはあまり説明していません.アルゴリズムの内容が詳しいのはやはり「アルゴリズム導論」を見て、システムを比較しなければなりません.
  • [x][バブルbubble]で、バブルソートは元の配列で直接操作されるため、スペースリソースが少なく、データ量が少ない場合には良いです.しかしアルゴリズムは二重ループに関与するため,データ量が大きい場合,プログラムの実行時間はかなり長く,一度にデータを遍歴するためである.
  • [x]はソートを挿入し、ソートを挿入する基本的な操作は、1つのデータを並べ替えられた秩序データに挿入し、それによって新しい、個数に1を加えた秩序データを得ることであり、アルゴリズムは少量のデータのソートに適用され、時間複雑度はO(n^2)である.安定したソート方法です.挿入アルゴリズムは、ソートする配列を2つの部分に分けます.第1の部分には、この配列のすべての要素が含まれていますが、最後の要素を除いて(配列の複数の空間に挿入された位置があるようにします)、第2の部分には、この要素(すなわち、挿入される要素)しか含まれていません.最初の部分のソートが完了したら、最後の要素をソートされた最初の部分に挿入します.
  • [x]ヒルソート,ヒルソート(Shell Sort)は挿入ソートの一種である.インクリメンタルソートの縮小とも呼ばれ、ソートアルゴリズムを直接挿入するより効率的な改良バージョンです.ヒルソートは非安定ソートアルゴリズムである.この方法はDL.Shellが1959年に提案したことから名付けられた.ヒルソートは、レコードを下付きの一定の増分でグループ化し、各グループに対して直接挿入ソートアルゴリズムを使用してソートする.増分が減少するにつれて、各グループに含まれるキーワードはますます多くなり、増分が1に減少すると、ファイル全体がグループに分けられ、アルゴリズムは終了する.比較挿入ソート:1.挿入ソートは毎回1つのデータしか移動できず、一般的には非効率です.2.しかし、ソートを挿入することは、ほとんどソートされたデータを操作する場合に効率的であり、すなわち増分がある程度減少する場合に効率的である.
  • [x]クイックソートでは、ソートするデータを1回のソートで独立した2つの部分に分割し、一部のすべてのデータが他の部分のすべてのデータよりも小さくなった後、この方法で2つの部分のデータをそれぞれクイックソートし、ソートプロセス全体を再帰的に行い、データ全体が秩序化シーケンスになるようにすることができます.データ量が大きいとヒルより倍近く速い.
  • [x]直接選択並べ替え、基本思想:1回目は、並べ替え待ち記録r 1~r[n]の中から最小の記録を選択し、r 1と交換する.2回目は、ソート対象レコードr 2~r[n]の中から最小のレコードを選択し、r 2と交換する.このように,i回目はソート対象レコードr[i]~r[n]の中で最小のレコードを選択し,r[i]と交換し,すべてのソートが完了するまで秩序シーケンスを成長させる.データが大きいとパフォーマンスが低下します.
  • [x]スタックソート、スタックソート(Heapsort)とは、スタックツリー(スタック)というデータ構造を用いて設計されたソートアルゴリズムであり、ソートを選択するものである.配列の特徴を使用して、指定したインデックスの要素をすばやく配置できます.山は大根の山と小根の山に分かれていて、完全に二叉木です.ルートスタックの要件は、各ノードの値が親ノードの値より大きくないことです.すなわち、A[PROD[i]>=A[i]です.配列の非降順ソートでは、大きなスタックが使用される必要があります.大きなスタックの要求によって、最大の値は必ずスタックの頂上にあることがわかります.
  • [x]基数ソート、基数ソート(radix sort)は「分配式ソート」(distribution sort)に属し、「バケツ法」(bucket sort)またはbin sortとも呼ばれる.その時間的複雑度はO(nlog(r)m)であり,rは取られた基数であり,mはスタック数であり,場合によっては他の安定性ソート法よりも基数ソート法の効率が高い.

    • これはplot_data.pyで描かれた各ソートアルゴリズムを異なるレベルで比較したもので、遅すぎると私はブロックしました.
  • [x]Hash,/Hashディレクトリを参照.

    • 安定ソートと不安定ソート
    リファレンス
    簡単に言えば、同じ数が2つある場合、ソート前後の相対位置関係は変わらない.
  • 安定ソート:バブル、挿入、集計、基数ソート
  • 不安定ソート:選択、高速、ヒル、スタックソート
    • 時間の複雑さ
    JPA処理条件inのページングクエリ
    SpringBoot Jpa複雑な動的sqlクエリを実現