Durante a entrevista ou teste por escrito, encontrei os 4 algoritmos a seguir sobre o arranjo e a combinação muitas vezes. Tome uma nota aqui e verifique o método no futuro:
1. Uma matriz sem elementos duplicados, encontre o arranjo completo;
2. Matrizes com elementos repetidos, encontre o arranjo completo;
3. Para uma matriz sem elementos duplicados, encontre a combinação [subconjunto];
4. Uma matriz com elementos repetidos, encontre a combinação;
Os quatro tipos de perguntas acima podem ser implementados usando um modelo unificado, como mostrado abaixo:
/ * *[Combinação && arranjo] *Liste todas as combinações de números em uma matriz, como 1 e 2 como 1, 2, 12, 21. *Esta pergunta pode ser expandida para quatro: *1. Matrizes sem números duplicados, encontre combinações*2. Matrizes com números duplicados, encontre combinações*3. Matrizes sem números duplicados, encontre arranjo completo*4. Matrizes com números duplicados, encontre arranjo completo *[IDEA GERAL (RECURSION)]: *Defina uma função: selecione um prefixo combinado do candidato Candicate *sempre que remova um número do candidato Candicate e adicione prefixo para imprimir prefixo; *Remova recursivamente o próximo número do novo candidato e adicione prefixo *[controle para recursão] *Use o hashset para salvar o prefixo. Antes de imprimir, determine se o hashset contém o prefixo atualmente gerado. *Se não houver, imprima e adicione hashset; Se houver, não imprimi-lo *[combinação-》 arranjo] *Basta adicionar um julgamento antes de imprimir: se o candidato definido candicate estiver vazio, significa que a travessia é concluída uma vez e um arranjo é gerado, e você pode imprimir */package xh.offer.practice; import java.util.arrays; java.util.list; importar java.util.list; public class listallGroup {public static void main (string [] args) {string [] array = {"1", "2"}; String [] repetir = {"1", "2", "1"}; listallGroup test = new listallgroup (); System.out.println ("********* sem repetir lista *********"); test.listallnorePeate (Arrays.asList (Array), ""); // Initialize prefix = "" System.out.println ("*********** Lista de repetição ******"); HashSet <String> norePeateset = new HashSet <String> (); test.ListallRepeate (Arrays.asList (Repeate), "", norepeateset); System.out.println ("************* test.premutaçãoNorePeate (Arrays.asList (Array), ""); System.out.println ("************************* HashSet <String> repetição = new HashSet <String> (); test.premutaçãoRepeate (Arrays.asList (Repeato), "", repetição); } // combinação sem duplicação public void listallnorePeate (list <string> candicate, string prefix) {if (prefix.length ()! = 0) system.out.println (prefixo); // o comprimento do resultado não é 0, então imprima a combinação para (int i = 0; i <candicate.size () i+mais)) (). Templista = new LinkedList <String> (Candicate); // Templista reduz um número e salva temporariamente o número removido na string templista tempstring = (string) templist.remove (i); // recursivo listallnorepeate (templista, prefixo + tempstring); }} // Há uma combinação duplicada, adicione hashset public void listallRepeate (list <string> candidato, string prefixo, hashset <string> res) {if (prefix.Length ()! res.add (prefixo); } para (int i = 0; i <candidato.size (); i ++) {list <string> templist = new LinkedList <String> (Candicate); String tempstring = templist.remove (i); ListAllRepeate (Templista, Prefixo+TempString, Res); // Recursive}} // Todo o arranjo sem duplicação, adicione julgamento candicate.size () == 0 public void premuturenorePeate (list <string> candicate, string prefix) {if (candnic.size () == 0) {System..ticate, string, ling. } para (int i = 0; i <Candicate.size (); i ++) {list <string> templist = new LinkedList <String> (Candicate); String tempstring = templist.remove (i); premutationNoreEpeate (Templista, Prefixo+TempString); }} // Existe um acordo total repetido, adicione hashset para ajudar no julgamento e produção de prematutação pública void (list <string> candicate, string prefixo, hashset <string> res) {if (Candicate.size () == 0 &&! Res.contains (prefix)) {System.out.printlnnnnnnn (prefix); res.add (prefixo); } para (int i = 0; i <candidato.size (); i ++) {list <string> templist = new LinkedList <String> (Candicate); String tempstring = templist.remove (i); premutuationRepeate (Templista, Prefixo+TempString, res); }}} O exposto acima é todo o conteúdo deste artigo. Espero que seja útil para o aprendizado de todos e espero que todos apoiem mais o wulin.com.