J'essaye le défi du poisson Codility qui est décrit comme suit:
On vous donne deux tableaux A et B non vides composés de N entiers. Les tableaux A et B représentent N poissons voraces dans une rivière, ordonnés en aval le long du débit de la rivière.
Les poissons sont numérotés de 0 à N - 1. Si P et Q sont deux poissons et P <Q, alors le poisson P est initialement en amont du poisson Q. Initialement, chaque poisson a une position unique.
Le nombre de poissons P est représenté par A [P] et B [P]. Le tableau A contient les tailles des poissons. Tous ses éléments sont uniques. Le tableau B contient les directions du poisson. Il ne contient que des 0 et / ou des 1, où:
0 représente un poisson qui coule en amont, 1 représente un poisson qui coule en aval. Si deux poissons se déplacent dans des directions opposées et qu'il n'y a pas d'autre poisson (vivant) entre eux, ils finiront par se rencontrer. Alors un seul poisson peut rester en vie - le plus gros poisson mange le plus petit. Plus précisément, on dit que deux poissons P et Q se rencontrent lorsque P <Q, B [P] = 1 et B [Q] = 0, et qu'il n'y a pas de poisson vivant entre eux. Après leur rencontre:
Si A [P]> A [Q] alors P mange Q, et P s'écoulera toujours en aval, Si A [Q]> A [P] alors Q mange P, et Q s'écoulera toujours en amont. Nous supposons que tous les poissons coulent à la même vitesse. Autrement dit, les poissons qui se déplacent dans la même direction ne se rencontrent jamais. Le but est de calculer le nombre de poissons qui resteront en vie.
Par exemple, considérons les tableaux A et B tels que:
A [0] = 4 B [0] = 0 A 1 = 3 B 1 = 1 A 2 = 2 B 2 = 0
A [3] = 1 B [3] = 0 A [4] = 5 B [4] = 0 Au départ, tous les poissons sont vivants et tous, sauf le poisson numéro 1, se déplacent vers l'amont. Le poisson numéro 1 rencontre le poisson numéro 2 et le mange, puis il rencontre le poisson numéro 3 et le mange aussi. Enfin, il rencontre le poisson numéro 4 et est mangé par lui. Les deux poissons restants, les numéros 0 et 4, ne se rencontrent jamais et restent donc en vie.Ecrire une fonction:
solution int (vecteur & A, vecteur & B);
cela, étant donné deux tableaux non vides A et B composés de N entiers, renvoie le nombre de poissons qui resteront vivants.
Par exemple, étant donné les tableaux ci-dessus, la fonction doit renvoyer 2, comme expliqué ci-dessus.
Écrivez un algorithme efficace pour les hypothèses suivantes:
N est un entier compris dans la plage [1..100 000]; chaque élément du tableau A est un entier compris dans la plage [0..1,000,000,000]; chaque élément du tableau B est un entier qui peut avoir l'une des valeurs suivantes: 0, 1; les éléments de A sont tous distincts.
Ma solution est la suivante:
// you can use includes, for example:
// #include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
std::queue<int> downStreamers;
int deadFish = 0;
for(int i = 0; i < (int)B.size(); i++)
{
int direction = B[i];
int size = A[i];
if(direction == 1)
downStreamers.push(size);
else
{
while(!downStreamers.empty())
{
deadFish += 1;
if(size > downStreamers.front())
{
downStreamers.pop();
}
else
break;
}
}
}
return A.size()-deadFish;
}
Voici comment j'ai conçu ce code (dans ma tête):
La structure de file d'attente appelée downStreamers contiendra des poissons allant vers l'aval (1)
deadFish contiendra un compteur de décès dus à une collision de direction
La boucle:
Pour chaque poisson je
À la fin de la boucle, le résultat devrait être le nombre de poissons (A.size ()) - deadFishes. Cela fonctionne pour les cas de test simples. Cependant, il échoue les cachés et la codilité ne fournit pas beaucoup de commentaires sur ce qui n'a pas fonctionné.
Voici mes résultats de test.
J'apprécierais que quelqu'un me donne un aperçu de la façon d'aborder ces problèmes d'une manière infaillible.
4 Réponses :
Je vais publier quelques réflexions et idées d'algorithmes pour vous. J'espère que cela vous aidera à visualiser le problème.
Quelques observations initiales - tous les poissons nageant en amont au début du tableau ne peuvent jamais manger ou être mangés. Idem pour les poissons au fond du tableau nageant en aval. L'action se produit lors de la numérisation d'avant en arrière lorsqu'un aval rencontre un amont.
Tout d'abord, marchez de l'avant vers l'arrière jusqu'à ce que vous trouviez un poisson nageant en duvet.
Ensuite, continuez à parcourir votre baie descendante / montante jusqu'à ce qu'elle bascule de bas en haut.
Résolvez le combat et incrémentez un marqueur de combat.
Si down gagne, continuez à descendre. Si up gagne, enregistrez l'index de votre emplacement dans le (s) tableau (s), puis remontez le tableau jusqu'à ce qu'il soit mangé ou que vous frappiez un poisson nageant dans la même direction.
S'il trouve un poisson nageant dans sa direction, il vivra, retournera à l'endroit où il a commencé à balayer à nouveau vers le bas.
S'il est mangé, prenez ce poisson et commencez à comparer là où vous vous êtes arrêté dans le tableau du bas.
Répétez jusqu'à ce que vous atteigniez la fin de la liste. Retournez le (nombre de poissons de départ - nombre de combats)
La partie intéressante est que c'est en place. Pas de déplacement de mémoire, pas besoin de marquer les poissons morts, etc. Il fonctionnera en temps linéaire - au plus près de 2x linéaire.
C'est le pseudo code que j'utiliserais pour résoudre ce problème.
Salut, c'est une manière intuitive d'aborder ce problème, mais lorsque j'ai essayé de l'implémenter, il était difficile de garder une trace des boucles imbriquées et des instructions if.
Je soupçonne que le problème avec votre code utilise une file d'attente. Je pense que cela fonctionnera, si vous le remplacez par une pile à la place. Prenons cet exemple:
vector<int> A = { 4,2,1,3 };
vector<int> B = { 1,0,1,0 };
Avec une pile: 0 mange 1, 3 mange 2 puis 0 mange 3.
Avec votre file d'attente: 0 mange 1, 0 mange 3 et 2 ne peuvent plus être mangés.
Remarque: une file d'attente fonctionne en premier, premier sorti. D'un autre côté, un tapis est le dernier entré, premier sorti. Et c'est ce que vous voulez ici.
Voici une solution (certes modérément alambiquée):
int main()
{
vector<int> A = {4,3,2,1,5};
vector<int> B = {0,1,0,0,0};
int sol = solution(A, B);
cout << "A = {4,3,2,1,5}, B = {0,1,0,0,0}? 2: " << sol << endl;
A = {1,0};
B = {1,0};
sol = solution(A, B);
cout << "A = {1,0}, B = {1,0}? 1: " << sol << endl;
A = {0,1};
B = {0,0};
sol = solution(A, B);
cout << "A = {0,1}, B = {0,0}? 2: " << sol << endl;
A = {0};
B = {1};
sol = solution(A, B);
cout << "A = {0}, B = {1}? 1: " << sol << endl;
A = {1};
B = {0};
sol = solution(A, B);
cout << "A = {1}, B = {0}? 1: " << sol << endl;
A = {7,4,3,2,5,6};
B = {0,1,1,1,0,1};
sol = solution(A, B);
cout << "A = {7,4,3,2,5,6}, B = {0,1,1,1,0,1}? 3: " << sol << endl;
A = {3,4,2,1,5};
B = {1,0,0,0,0};
sol = solution(A, B);
cout << "A = {3,4,2,1,5}, B = {1,0,0,0,0}? 4: " << sol << endl;
A = {1,2};
B = {0,1};
sol = solution(A, B);
cout << "A = {1,2}, B = {0,1}? 2: " << sol << endl;
A = {4,2,1,3};
B = {1,0,1,0};
sol = solution(A, B);
cout << "A = {4,2,1,3}, B = {1,0,1,0}? 1: " << sol << endl;
A = {4,3,2,5,6};
B = {1,0,1,0,1};
sol = solution(A, B);
cout << "A = {4,3,2,5,6}, B = {1,0,1,0,1}? 2: " << sol << endl;
return 0;
}
Algorithme:
A est traversé.ii nage en aval ( B[ii] = 0 ), il est comparé aux poissons de la pile en upstream .ii dans la solution de liste (que j'ai nommé fish sans imagination), mais il ne sort pas de la pile en upstream .Cela passe le test proposé par @xeed et obtient globalement 100% sur Codility. Pour un MWE complet, voici un programme de test principal du pilote:
// you can use includes, for example:
// #include <algorithm>
#include <list>
#include <stack>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
int solution(vector<int> &A, vector<int> &B) {
list<int> fish;
stack<int> upstream;
for (int ii = A.size() - 1; ii >= 0; --ii) {
if (B[ii] == 0)
upstream.push(A[ii]);
else {
fish.push_back(A[ii]);
while ( !upstream.empty() ) {
if ( upstream.top() > fish.back() ) {
fish.pop_back();
fish.push_back( upstream.top() );
upstream.pop();
--ii;
if (ii < 0) {
++ii;
break;
} else {
while (!fish.empty() && ii < (int) B.size()) {
if (B[ii] == 0) {
upstream.push(fish.back());
fish.pop_back();
++ii;
break;
}
if ( fish.back() > A[ii] )
--ii;
else {
++ii;
fish.pop_back();
break;
}
}
break;
}
} else
upstream.pop();
}
}
}
int add_size = 0;
if ( !upstream.empty() )
add_size = upstream.size();
return fish.size() + add_size;
}
Voici une solution que j'ai écrite en prenant votre testcase:
Direction Up: Eating Fish 2 by 1 Direction Up: Eating Fish 3 by 1 Direction Down: Eating Fish 1 by 4 Number Of Fish Remaining are: 2
Cette solution générera la sortie suivante:
#include <stdio.h>
#include <vector>
#include <iostream>
int main()
{
std::vector<int> fishSize = { 4, 3, 2, 1, 5 };
std::vector<int> fishDirection = { 0, 1, 0, 0, 0 };
int numberOfFish = fishSize.size();
for (int i=0; i < numberOfFish; i++) {
int curFishSize = fishSize[i];
int curFishDirection = fishDirection[i];
if (curFishDirection == 0) {
// Direction down
for (int j = i - 1; j > 0; j--) {
int compareFishSize = fishSize[j];
int compareFishDirection = fishDirection[j];
if (compareFishDirection == 1 && compareFishSize < curFishSize) {
// Eat this fish
fishSize[j] = -1;
fishDirection[j] = -1;
std::cout << "Direction Down: Eating Fish " << j << " by " << i << std::endl;
} else if (compareFishDirection == -1) {
continue;
} else {
break;
}
}
} else if (curFishDirection == 1) {
// Direction up
for (int j = i+1; j < numberOfFish; j++) {
int compareFishSize = fishSize[j];
int compareFishDirection = fishDirection[j];
if (compareFishDirection == 0 && compareFishSize < curFishSize) {
// Eat this fish
std::cout << "Direction Up: Eating Fish " << j << " by " << i << std::endl;
fishSize[j] = -1;
fishDirection[j] = -1;
} else if (compareFishDirection == -1) {
continue;
} else {
break;
}
}
}
}
int numberOfFishRemaining = 0;
for(int a : fishSize) {
if (a != -1) numberOfFishRemaining++;
}
std::cout << "Number Of Fish Remaining are: " << numberOfFishRemaining << std::endl;
return 0;
}
J'espère que cela résoudra également tous vos cas de test.
Pouvez-vous ajouter la description du défi à la question?
J'ai mis à jour le message.