Il s'agit d'une série d'articles que j'ai compilés dans mon étude et mon mémo. La septième balle. Cliquez ici pour les articles précédents.
Dans cet article
Je vais étudier sur. Des dictionnaires et des combinaisons apparaissent souvent, alors profitons de l'occasion pour les maîtriser. Il semble que cela soit parfois appelé une recherche de séquence complète.
Je comprends déjà l'ordre mathématique du dictionnaire, la permutation et l'explication de la combinaison ~~ c'est ennuyeux ~~, alors omettons-le.
Cette fois, je réfléchirai à diverses choses tout en résolvant le problème. Je vais chercher les questions du passé et résoudre des problèmes comme celui-là.
Exemple: AtCoder --abc150-c "Count Order"
(Début de section) 【Énoncé du problème】 Il existe des colonnes d'ordre de grandeur N (nombre de colonnes créées en réorganisant (1, 2, ..., N)) P, Q. L'ordre de taille N est N!Je peux y penser. Parmi ceux-ci, en supposant que P est le plus petit dans l'ordre lexical et Q est le bième plus petit dans l'ordre lexical.|a−b|Veuillez demander.
[Remarque] Pour deux séquences X, Y, si un entier k existe et Xi = Yi (1 ≤ i <k) et Xk <Yk est vrai, alors X est défini comme étant inférieur à Y dans l'ordre lexical.
[Restrictions]
【contribution】 L'entrée est donnée à partir de l'entrée standard dans le format suivant.
N
P1 P2 ... PN
Q1 Q2 ... QN
【production】 |a−b|Production.
(Fin de la section)
Il y avait un tel problème. Le ・ C'est un problème tel que l'ordre du dictionnaire. C'est un problème C, et il n'y a pas beaucoup de restrictions, donc si vous y allez simplement, vous ne pourrez peut-être pas le résoudre sans y penser, mais réfléchissons-y.
Jetons un coup d'œil à un exemple d'entrée et à un exemple de sortie.
Exemple d'entrée
3
1 3 2
3 1 2
Exemple de sortie
3
Si vous lisez quelque chose comme un commentaire,
L'ordre de la taille 3 est(1, 2, 3)、(1, 3, 2)、(2, 1, 3)、(2, 3, 1)、(3, 1, 2)、(3, 2, 1)Il y en a 6. cette maison(1, 3, 2)Est deuxième dans l'ordre lexical,(3, 1, 2)Est le cinquième dans l'ordre lexical, donc la réponse est|2−5|=C'est 3.
Était écrit. Ce serait bien si la taille (nombre) dans la commande était requise. Dans le langage c ++, il y a une fonction comme next_permutation, mais en java, il n'y a pas d'élément suivant de la séquence, donc c'est un peu déroutant à implémenter. Dans un tel cas, je me référerai à la réponse sans hésitation. Veuillez patienter un peu car je ferai référence à l'explication et aux exemples de réponses d'autres personnes. ..
... Bon sang. .. .. Il semble que tous les joueurs C ++ font next_permutation. Au fait, il semble que même DFS puisse énumérer l'ordre, alors j'ai pensé que ce serait bien de l'essayer une fois après avoir étudié DFS. J'ai réussi à trouver le lien ici. Le lien collé à la destination du lien semble être l'original, mais il semble que java gère tous les éléments de la séquence dans la liste. Utilisons ceci.
Devis lié
public static void permutation(String q, String ans){
// Base Case
if(q.length() <= 1) {
System.out.println(ans + q);
}
// General Case
else {
for (int i = 0; i < q.length(); i++) {
permutation(q.substring(0, i) + q.substring(i + 1),
ans + q.charAt(i));
}
}
}
Cela peut être un peu difficile à comprendre, mais il semble que si vous entrez la première chaîne de caractères de la séquence, elle sera sortie dans l'ordre lexical de cette chaîne de caractères.
permutation("abc","");
Lorsque vous exécutez
abc
acb
bac
bca
cab
cba
A été affiché. C'est incroyable. J'utiliserai ceci pour résoudre ce problème.
[Exemple de réponse]
Main.java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static ArrayList<String> list;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//nombre de mots
int n = sc.nextInt();
//Une variable qui stocke une liste de séquences
list = new ArrayList<>();
// p,Recevoir l'entrée de q
String p = "";
String q = "";
String[] p_sort = new String[n]; //Je souhaite stocker le premier élément d'une séquence
for (int i = 0; i < n; i++) {
String tmp = sc.next();
p += tmp;
p_sort[i] = tmp;
}
for (int i = 0; i < n; i++) {
q += sc.next();
}
Arrays.parallelSort(p_sort); // p_fait trier le premier élément de la séquence
String p_sort_str = "";
for (String p_sort_tmp : p_sort) {
p_sort_str += p_sort_tmp;
}
//Remplissez la liste avec des valeurs
permutation(p_sort_str, "");
//Sortie valeur absolue de l'indice
System.out.println(Math.abs(list.indexOf(q) - list.indexOf(p)));
}
public static void permutation(String q, String ans) {
// Base Case
if (q.length() <= 1) {
list.add(ans + q);
}
// General Case
else {
for (int i = 0; i < q.length(); i++) {
permutation(q.substring(0, i) + q.substring(i + 1),
ans + q.charAt(i));
}
}
}
}
Pourriez-vous l'écrire relativement simplement? C'est incroyable de pouvoir calculer la séquence de commandes comme ça.
Il semble que cela puisse être appliqué, alors utilisons-le pour résoudre de nombreux autres problèmes. Ce serait bien d'avoir une classe ou une bibliothèque comme c ++ ou python. ..
Je veux résoudre d'autres problèmes, donc cet article est la partie 1, résolvons donc d'autres problèmes d'ordre et de combinaison de dictionnaires.
À la prochaine!
Recommended Posts