インタビューまたは筆記試験で、私は何度も配置と組み合わせに関する次の4つの手張りアルゴリズムに遭遇しました。ここでメモを取り、将来の方法を確認してください。
1.要素を重複していない配列は、完全な配置を見つけます。
2。繰り返し要素を備えた配列、完全な配置を見つけます。
3。要素を重複していない配列の場合、組み合わせ[サブセット]を見つけます。
4.繰り返し要素を備えた配列、組み合わせを見つけます。
上記の4種類の質問は、以下に示すように、統一されたテンプレートを使用して実装できます。
/ * *[コンビネーション&&アレンジメント] *1、2、12、21などの1および2など、アレイ内のすべての数値の組み合わせをリストします。 *この質問は4つに拡張できます。数字を重複していない配列、組み合わせ*2を見つけます。数字が重複している配列、組み合わせを見つけます*3。数字を重複していない配列、完全な配置*4を見つけます。複製番号を備えたアレイ、完全な配置を見つけます *[一般的なアイデア（再帰）]： *関数を定義します：候補セットからコンビネーションのプレフィックスを選択します *候補セットから数字を削除するたびに、候補セットから数字を削除し、プレフィックスを印刷プレフィックスに追加します。 *新しい候補から次の番号を再帰的に削除し、プレフィックスを追加 *[再帰のコントロール] *ハッシュセットを使用してプレフィックスを保存します。印刷する前に、ハッシュセットに現在生成されているプレフィックスが含まれているかどうかを判断します。 *noがある場合は、印刷してハッシュセットを追加します。ある場合は、印刷しないでください *[組み合わせ - 》アレンジメント] *印刷前に判断を追加するだけです。候補セットのcandicateが空の場合、トラバーサルが一度完了し、アレンジメントが生成され、Xh.offer.practiceを印刷できます。 java.util.list; public class listallgroup {public static void main（string [] args）{string [] array = {"1"、 "2"}; string [] Repeat = {"1"、 "2"、 "1"}; listallgroup test = new listallgroup（）; System.out.println（ "*********繰り返しリストなし*********"）; test.listallnorepeate（arrays.aslist（array）、 ""）; // initialize prefix = "" system.out.println（ "********* repeate list ******"）; Hashset <string> norepeateset = new Hashset <String>（）; test.listallrepeate（arrays.aslist（Repeate）、 ""、norepeateset）; System.out.println（ "************* No Repeat Premutation ****************************"）; test.premutationnorepeate（arrays.aslist（array）、 ""）; System.out.println（ "*************************繰り返し前行*************************"）; Hashset <string> Repeatset = new Hashset <String>（）; test.premetationRepeate（arrays.aslist（Repeate）、 ""、Repeatset）; } //重複なしの組み合わせpublic void listallnorepeate（list <string> candicate、string prefix）{if（prefix.length（）！= 0）system.out.println（prefix）; //結果の長さは0ではありません。 new LinkedList <String>（Candicate）; // Templistは数値を減らし、Templist String TempString =（String）Templist.Remove（i）で削除された数を一時的に保存します。 //再帰listallnorepeate（Templist、prefix + Tempstring）; }} //重複した組み合わせがあります、ハッシュセットpublic void listallrepeate（list <string> condation、string freix、hashset <string> res）{if（prefix.length（）！= 0 &&！res.contains（freix））{system.out.out.println（prefix）; Res.Add（プレフィックス）; } for（int i = 0; i <condation.size（）; i ++）{list <string> templist = new linkedlist <string>（candicate）; string tempstring = templist.remove（i）; listallrepeate（Templist、prefix+Tempstring、res）; // Recursive}} //重複なしですべての配置、Judgement Candicate.size（）== 0 public void premtationnorepeate（list <string> Candicate、string prefix）{if（candicate.size（）= 0）{system.out.println（prefix）; } for（int i = 0; i <candicate.size（）; i ++）{list <string> templist = new LinkedList <String>（Candicate）; string tempstring = templist.remove（i）; prematuteNorepeate（Templist、prefix+Tempstring）; }} //フルアレンジメントが繰り返されます。ハッシュセットを追加して、判断を支援し、パブリックボイドのprematuationRepeate（list <string> candicate、string prefix、hashset <string> res）{if（candicate.size（）= 0 &&！res.contains（prefix））{system.out.out）; Res.Add（プレフィックス）; } for（int i = 0; i <condation.size（）; i ++）{list <string> templist = new linkedlist <string>（candicate）; string tempstring = templist.remove（i）; PremateTRepeate（Templist、Prefix+TempString、res）; }}}上記はこの記事のすべての内容です。みんなの学習に役立つことを願っています。誰もがwulin.comをもっとサポートすることを願っています。