Rapports au nez rouge-js tutoriel-php.cn

Rapports au nez rouge

DDD

Libérer： 2024-12-04 19:47:11

original

201 Les gens l'ont consulté

Red-Nosed Reports

Avènement du Code 2024 Jour 2

Partie 1

Résoudre simplement ou résoudre de manière optimale ? C'est la question

Pour simplement résoudre :

Comparez la liste dans l'ordre original à deux exemplaires, chacun trié, mais dans l'ordre inverse. S'il y a une correspondance, alors succès pour le premier critère
Parcourez chaque élément de la liste, sauf le premier. Suivez la différence entre chaque élément et l'élément précédent. Si des différences sont de 0 ou supérieures à 3, alors ce test échoue.

En termes de performances, cela signifie :
Pour le critère 1 :

Deux copies de liste
Tri de chaque copie
Comparer deux fois la liste originale Pour le critère 2 :
Vérifiez chaque numéro dans chaque liste

Pour résoudre de manière optimale :

Pour le critère 2, j'utiliserai une boucle while pour vérifier les nombres suivants pour des différences valides. De cette façon, dès qu'une différence disqualifiante se produit, le reste des numéros ne sera pas traité
Pour le critère 1, je suivrai les différences, puis vérifierai si toutes sont inférieures ou supérieures à zéro

Je pense que cela fonctionnera. Une seule façon de le savoir.

Écrire un algorithme optimisé

Voici mon code d'identification du critère 2 (différence de 1, 2 ou 3) :

let differFlag = true;
let i = 1;
while (differFlag && i < list.length) {
  let amount = Math.abs(list[i] - list[i - 1]);
  if (![1, 2, 3].includes(amount)) {
    differFlag = false;
  }
  i++;
}

Copier après la connexion

Je ne parcours la liste que jusqu'à ce qu'une différence invalide soit détectée, le cas échéant
Dès que l'on est attrapé, la boucle while se termine
Après la boucle while, je peux vérifier differFlag pour les résultats

Voici mon code d'identification du critère 1 (toutes les différences augmentent ou diminuent) :

let differFlag = true;
let i = 1;
let differences = [];
while (differFlag && i < list.length) {
  let amount = list[i] - list[i - 1];
  differences.push(amount);
  if (![1, 2, 3].includes(Math.abs(amount))) {
    differFlag = false;
  }
  i++;
}

Copier après la connexion

Je crée une liste de chaque différence
J'ai déplacé le calcul de la valeur absolue au conditionnel car je veux en fait capturer le signe de la différence
Après la boucle while, je peux vérifier les différences pour voir si chaque valeur est positive ou négative

Voici la condition finale qui capture un rapport sûr :

if (
     differFlag &&
    (differences.every((el) => el > 0) || 
     differences.every((el) => el < 0))
    ) {
      safeCount++;
    }

Copier après la connexion

Au total, mon algorithme génère la bonne réponse pour l'exemple d'entrée.

Est-ce que cela fera la même chose pour ma saisie de puzzle ??

Ouisssirrrreee !!

Doux !

Partie 2

Eh bien... tire.

Cela complique certainement un peu les choses.

J'aimerais éviter un algorithme qui vérifie toutes les permutations possibles d'un rapport. Cela nécessiterait de générer des millions de rapports.

La première bonne nouvelle est :

Tous les rapports sûrs peuvent toujours être considérés comme sûrs

Pour ma saisie de puzzle, cela fait environ 200 qui ne m'obligent pas à vérifier les permutations.

Néanmoins, 800/1000, c'est encore beaucoup de listes pour explorer pleinement les permutations.

Honnêtement, je ne vois pas de moyen d'éviter d'exécuter mon algorithme à chaque permutation de rapports dangereux.

Déception.

Il est temps d'ajouter une boucle pour parcourir chaque numéro dans les rapports dangereux - le numéro à supprimer, puis de vérifier la liste des mutations pour une note de passage.