プログラミング
 Computer >> コンピューター >  >> プログラミング >> プログラミング

分割統治アルゴリズムの概要

分割統治法は、異なるアルゴリズムパラダイムの1つです。主に3つの異なるステップがあります-

分割 −このフェーズでは、問題は同じタイプのいくつかの小さなサブ問題に分割されます。

征服 −サブ問題を再帰的に解決します。

組み合わせる −サブ問題の回答を組み合わせて、最終的な回答を取得します。

このセクションでは、これから説明します

  • 最も近いペアポイントの問題
  • 2D配列からピーク要素を選択
  • 配列内の反転をカウントする
  • 2つのソートされた配列の中央値

  1. リバランスアルゴリズム

    リバランスアルゴリズムは、次の方法で実行できます- Day-Stout-Warrenアルゴリズム Day-Stout-Warrenアルゴリズムを使用して、実際にリバランス方法を実装できます。ノード数は線形です。 以下は、擬似コードでの基本的なDSWアルゴリズムのプレゼンテーションです。 「疑似ルート」と呼ばれるノードが割り当てられ、ツリーの実際のルートが疑似ルートの正しい子になります。 引数として疑似ルートを使用してツリーをソートされたリンクリストに変換するために、tree-to-vine関数を呼び出します。 vine-to-tree関数を呼び出して、ソートされたリンクリストをツリーに

  2. Pythonで配列を増加するシーケンスに分割する

    numsと呼ばれる正の整数と整数Kの非減少配列があるとすると、この配列を少なくともKの長さの1つ以上の互いに素な増加部分列に分割できるかどうかを調べる必要があります。 したがって、入力がnums =[1,2,2,3,3,4,4]、K =3のような場合、この配列は[1、 2,3,4]および[2,3,4]、それぞれ少なくとも3つの長さ。 これを解決するには、次の手順に従います- d：=新しいマップ req：=0 numsの各iについて、実行します dにないiがゼロ以外の場合、 d [i]：=1 それ以外の場合 d [i]：=d [i] + 1