Au cours de l'entretien ou du test écrit, j'ai rencontré les 4 algorithmes d'épaissement à la main suivants sur la disposition et la combinaison plusieurs fois. Prenez une note ici et vérifiez la méthode à l'avenir:
1. Un tableau sans éléments en double, trouvez la disposition complète;
2. Réalités avec des éléments répétés, trouvez la disposition complète;
3. Pour un tableau sans éléments en double, trouvez la combinaison [sous-ensemble];
4. Un tableau avec des éléments répétés, trouvez la combinaison;
Les quatre types de questions ci-dessus peuvent être mis en œuvre à l'aide d'un modèle unifié, comme indiqué ci-dessous:
/ * * [Combinaison et arrangement] * Répertoriez toutes les combinaisons dans un tableau, telles que 1 et 2 As 1, 2, 12, 21. * Cette question peut être étendue en quatre: * 1. TABLEAUX SANS NUMÉROS DE DUPLIPATIONs, recherchez les combinaisons * 2. Tableaux avec des nombres en double, recherchez les combinaisons * 3. TABLEAUX SANS NUMÉROS DUPLIQUES, trouvez une disposition complète * 4. Arrays avec des nombres en double, recherchez une arrangement complet * [IDEA GÉNÉRALE (Recursion)]: * Définissez une fonction: Sélectionnez un préfixe combiné dans le jeu de candidats Candicate * Supprimez un numéro du candidat candidate Candicate à chaque fois et ajoutez le préfixe pour imprimer le préfixe; * Supprimez récursivement le numéro suivant du nouveau candidat et ajoutez le préfixe * [Control for Recursion] * Utilisez HashSet pour enregistrer le préfixe. Avant d'imprimer, déterminez si le Hashset contient le préfixe actuellement généré. * S'il n'y a pas, imprimez-le et ajoutez HashSet; S'il y a, ne l'imprimez pas * [combinaison--》 arrangement] * Ajoutez simplement un jugement avant d'imprimer: si le candidat candidat est vide, cela signifie que la traversée est terminée une fois et qu'un arrangement est généré, et vous pouvez imprimer * / package xh.offer.practice; import java.util.array java.util.list; Importer java.util.list; classe publique ListallGroup {public static void main (String [] args) {String [] array = {"1", "2"}; String [] répéter = {"1", "2", "1"}; ListallGroup test = new ListallGroup (); System.out.println ("********* Pas de liste de répétition *********"); test.ListAllNorepeate (arrays.aslist (array), ""); // initialize prefix = "" System.out.println ("********* Répéter List ******"); HashSet <string> norepeateSet = new HashSet <string> (); test.ListallRepeate (arrays.aslist (répéter), "", norepeateSet); System.out.println ("*************** Pas de prémutation de répétition ******************************"); test.premutationNorepeate (arrays.aslist (array), ""); System.out.println ("*************************** Prémutation répétée ***************************"); HashSet <string> répétitif = new hashSet <string> (); test.premutationRepeate (arrays.aslist (répéter), "", set set); } // combinaison sans duplication publique void listAllNorepeate (list <string> canditate, string prefix) {if (prefix.length ()! = 0) System.out.println (préfixe); // la longueur de résultat n'est pas 0, puis imprimez la combinaison pour (int i = 0; i <size list>; i ++) { templist = new LinkedList <string> (Candicate); // Templist réduit un nombre et enregistre temporairement le nombre supprimé dans Templist String tempsstring = (String) templist.Remove (i); // Récursive ListallNorePeate (Templist, Prefix + Tempstring); }} // Il existe une combinaison en double, ajouter le candidat de hashset public void ListallRepeate (list <string> candidate, string prefix, hashset <string> res) {if (prefix.length ()! = 0 &&! Res.contains (prefix)) {system.out.println (prefix); res.add (préfixe); } pour (int i = 0; i <candidate.size (); i ++) {list <string> templist = new LinkedList <string> (candate); String tempsstring = templist.Remove (i); ListallRepeate (Templist, Prefix + TEMPSTRING, RES); // Recursive}} // Tous les arrangements sans duplication, ajoutent un jugement Candicate.Size () == 0 Public Void PremutationNorepeate (List <String> Candicate, String Prefix) {if (canddicate.size () == 0) {System.out.out.PrintLn (prefix); } pour (int i = 0; i <canddicate.size (); i ++) {list <string> templist = new LinkedList <string> (candate); String tempsstring = templist.Remove (i); PremutationNorePeate (Templist, Prefix + Tempstring); }} // Il y a un arrangement complet répété, ajouter un hashset pour aider à jugement et à sortir public void PremutationRepeate (list <string> cantate, préfixe de chaîne, hashset <string> res) {if (candate.size () == 0 &&! Res.Contains (prefix)) {System.out.println (prefix); res.add (préfixe); } pour (int i = 0; i <candidate.size (); i ++) {list <string> templist = new LinkedList <string> (candate); String tempsstring = templist.Remove (i); PremutationRepeate (Templist, Prefix + Tempstring, Res); }}} Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.