Durante la entrevista o la prueba escrita, encontré los siguientes 4 algoritmos de matriz sobre disposición y combinación muchas veces. Tome una nota aquí y consulte el método en el futuro:
1. Una matriz sin elementos duplicados, encuentre la disposición completa;
2. Matrices con elementos repetidos, encuentre la disposición completa;
3. Para una matriz sin elementos duplicados, encuentre la combinación [subconjunto];
4. Una matriz con elementos repetidos, encuentre la combinación;
Los cuatro tipos de preguntas anteriores se pueden implementar utilizando una plantilla unificada, como se muestra a continuación:
/ * *[Combinación && Arreglo] *Enumere todas las combinaciones de números en una matriz, como 1 y 2 como 1, 2, 12, 21. *Esta pregunta se puede ampliar en cuatro: *1. Matrices sin números duplicados, encuentre combinaciones*2. Matrices con números duplicados, encontrar combinaciones*3. Matrices sin números duplicados, encuentre la disposición completa*4. Matrices con números duplicados, encuentre la disposición completa *[Idea general (recursión)]: *Defina una función: seleccione un prefijo de combinación del candidato candidato *cada vez que elimine un número del candidato candidato y agregue prefijo para imprimir prefijo; *Elimine recursivamente el siguiente número del nuevo candidato y agregue prefijo *[Control para la recursión] *Use hashset para guardar el prefijo. Antes de imprimir, determine si el hashset contiene el prefijo generado actualmente. *Si no hay, imprima y agregue hashset; Si lo hay, no lo imprima *[Combinación--》》》》 Acuerdo] *Simplemente agregue un juicio antes de imprimir: si el Candidato Conjunto de Candicate está vacío, significa que el recorrido se completa una vez y se genera una disposición, y puede imprimir */paquete xh.offer.pracTice; import java.util.arrays; import java.util.hashset; import java.utililia. java.util.list; import java.util.list; public class ListAllgroup {public static void main (string [] args) {string [] array = {"1", "2"}; Cadena [] repetir = {"1", "2", "1"}; listAllGroup test = new ListAllGroup (); System.out.println ("********* Sin lista de repetición ***********"); test.listallnorepeate (arrays.aslist (array), ""); // inicialize prefix = "" System.out.println ("*********** Lista de repeticiones ******"); Hashset <String> norepeateSet = new Hashset <String> (); test.listallRepeate (arrays.aslist (repete), "", norepeateset); System.out.println ("*************** No se repita premutación ****************************"); test.premutationNorepeate (arrays.aslist (matriz), ""); System.out.println ("************************************************ Hashset <String> RepetSet = new Hashset <String> (); test.premutationRepeate (arrays.aslist (repetición), "", repite); } // combinación sin duplicación public void listAllnorepeate (list <string> candicate, string prefix) {if (prefix.length ()! = 0) system.out.println (prefix); // La longitud de los resultados no es 0, luego imprima la combinación para (int i = 0; i <nandicate.size (); i ++) List <String> TEMPLIST = new LinkedList <String> (Candicate); // Templist reduce un número y guarda temporalmente el número eliminado en la cadena TempList tempstring = (string) Tempplist.remove (i); // recursivo listAllnorepeate (Templist, prefijo + tempttring); }} // Hay una combinación duplicada, agregar hashset public void listallRepeate (list <string> candidato, string prefix, hashset <string> res) {if (prefix.length ()! = 0 &&! Res.contains (prefix)) {system.out.println (prefix); res.add (prefijo); } for (int i = 0; i <candidate.size (); i ++) {list <string> TempList = new LinkedList <String> (Candicate); Cadena temptring = tempplist.remove (i); ListAllRepeate (TempList, Prefix+TempString, Res); // recursivo}} // Todos los disposiciones sin duplicación, agregue el juicio candicate.size () == 0 public void premutationnorepeate (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); Cadena temptring = tempplist.remove (i); premutationnorepeate (Templist, prefijo+tempttring); }} // Hay una disposición completa repetida, agregue hashset para ayudar en el juicio y la salida pública void premutationRepeate (list <string> candicate, string prefix, hashset <string> res) {if (candicate.size () == 0 &&! Res.contains (prefix)) {System.out.println (prefix); res.add (prefijo); } for (int i = 0; i <candidate.size (); i ++) {list <string> TempList = new LinkedList <String> (Candicate); Cadena temptring = tempplist.remove (i); PremutationRepeate (Templist, Prefijo+TempTring, Res); }}} Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.