J'ai du code de travail, mais je cherche à améliorer la manière dont je comprends et mettez en œuvre différentes techniques de codage dans son ensemble. Je pensais que ce problème a présenté une bonne occasion de recevoir des commentaires sur ce que je fais.
L'idée ici est de prendre deux arguments, un tableau et un entier. Identifiez toutes les paires de la matrice dont la somme pour rendre l'argument entier, puis renvoyer la somme des indices. Vous ne pouvez pas réutiliser un index et vous devez toujours utiliser le plus petit index disponible pour vous. Il y a une explication sur le guide de code FCC ici: https: // www .freecodecamp.org / Apprendre / codage-entretien-prep / algorithmes / paires p>
Donc, voici la question. Y a-t-il un bon moyen de le faire sans utiliser de boucles imbriquées pour les boucles? Je suis de plus en plus conscient des complexités du temps / de l'espace, et je sais que O (n ^ 2) ne me va pas le travail. J'imagine qu'un haschmap de quelque sorte viendrait, mais je n'ai tout simplement pas l'expérience et les connaissances pour savoir comment les utiliser. p>
Voici le code: p>
p>
function pairwise(arr, arg) {
let usedIndex = [];
let output = 0;
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (
arr[i] + arr[j] == arg
&& usedIndex.indexOf(i) == -1
&& usedIndex.indexOf(j) == -1
) {
usedIndex.push(i, j)
output += i + j
}
}
}
return output;
}
pairwise([0, 0, 0, 0, 1, 1], 1) // should return 103 Réponses :
Pour de meilleures performances, vous pouvez enregistrer la longueur d'arrêt dans une variable, alors pour la boucle ne comptera pas chaque boucle.
p>
function pairwise(arr, arg) {
let usedIndex = [];
let output = 0;
let length = arr.length;
for (let i = 0; i < length; i++) {
for (let j = i + 1; j < length; j++) {
if (
arr[i] + arr[j] == arg
&& usedIndex.indexOf(i) == -1
&& usedIndex.indexOf(j) == -1
) {
usedIndex.push(i, j)
output += i + j
}
}
}
return output;
}Ceci peut être fait dans une boucle avec une utilisation intelligente d'un objet et d'une connaissance que les indices ne peuvent être utilisés qu'une fois.
p>
function pairwise(arr, arg) {
let map = {};
let output = 0;
let length = arr.length;
for (let i = 0; i < length; i++) {
let subArr = map[arr[i]];
if(subArr && subArr[0] !== undefined) {
//there is an index waiting to pair, remove it and add to output
output += subArr.pop() + i;
} else {
//add this index to its pair slot
let left = arg - arr[i];
if(!map[left]) map[left] = [];
map[left].unshift(i);
}
}
return output;
}
console.log(pairwise([0, 0, 0, 0, 1, 1], 1), "should be 10");
console.log(pairwise([1, 4, 2, 3, 0, 5], 7), "should be 11");
console.log(pairwise([], 100), "should be 0");
console.log(pairwise([1, 3, 2, 4], 4), "should be 1");Utilisation intelligente des cartes!
Merci pour cette réponse, appréciez vraiment cela. Je dois dire que je n'ai même jamais rencontré de manière [Ar-Arg] d'accéder à un index. J'ai essayé l'imprimer, mais il retourne Nan. Pourriez-vous me faire savoir ce qu'on appelle s'il vous plaît et je ferai des recherches?
@kmars voici un Page MDN dessus. Qu'est-ce que vous imprimez exactement qui obtiennent NAN? La syntaxe est fondamentalement juste Key = Arg - arr [I]; console.log (carte [clé]); - c'est un accès de propriété calculé.
@Klaycon merci pour la réponse du patient. Avait un peu de pète cérébral et pour une raison quelconque, pensait que «-» était une notation d'accès infaimaire comme [] que je n'avais pas rencontrée par opposition à un signe moins régulier. Comme il semble que vous sache, une question séparée peut-elle savoir - pourquoi séparer la variable de longueur dans sa propre chose lorsque vous pouvez simplement utiliser Arr.Longueur?
@kmars Ceci a été fait à la suite des conseils de Sonetlumiere's Réponse . arr.l.length est un getter qui énumère la matrice à chaque appel, le stocker dans une variable est une micro-optimisation pour éviter cela.
L'étape 1 est O (n * logn).
L'étape 2 est O (n) - chaque compteur ira à mi-chemin de la liste, s'arrêtant quand ils se rencontrent.
Cette question pourrait être un meilleur ajustement pour codereview.stackexchange.com .
J'ai marqué pour migration vers Cr par ce méta-post
Thing drôle, c'est que tu fais rarement cela dans la vie réelle. :)
Puisque vous entrez dans chaque tableau dans l'ordre, pourquoi devez-vous vérifier si la combinaison a déjà été utilisée?