Problème
Pour financer une sortie, un lycée organise une loterie. Le tirage désigne quelques numéros gagnants distincts, et chaque billet porte le même nombre de numéros distincts. L'ordre des numéros sur un billet n'a pas d'importance ; le score d'un billet est le nombre de ses numéros qui sont gagnants. Pour fixer les lots, les organisateurs doivent savoir combien de billets ont atteint chaque score.
Implémentez ticket_lottery(winning, tickets).
Entrée
winning : les numéros gagnants, tous distincts.
tickets : les billets ; chaque ligne contient les numéros distincts d'un billet, avec la même longueur que winning.
Sortie
Renvoyez une liste de longueur len(winning) + 1 dont la position k contient le nombre de billets ayant exactement k numéros gagnants.
Contraintes
1 ≤ len(winning) ≤ 10
0 ≤ nombre de billets ≤ 5 000
1 ≤ chaque numéro ≤ 99
Exemples
Entrée :
winning = [3, 11, 20]
tickets = [
[3, 11, 20],
[20, 5, 7],
[1, 2, 4],
[11, 3, 9]
]
Sortie attendue :
expected = [1, 1, 1, 1]
Entrée :
std::vector<long long> winning = {3, 11, 20};
std::vector<std::vector<long long>> tickets = {
{3, 11, 20},
{20, 5, 7},
{1, 2, 4},
{11, 3, 9}
};
Sortie attendue :
std::vector<long long> expected = {1, 1, 1, 1};
Entrée :
long[] winning = new long[] {3, 11, 20};
long[][] tickets = new long[][] {
new long[] {3, 11, 20},
new long[] {20, 5, 7},
new long[] {1, 2, 4},
new long[] {11, 3, 9}
};
Sortie attendue :
long[] expected = new long[] {1, 1, 1, 1};
Explication
Les billets ont 3, 1, 0 et 2 bons numéros, donc chaque score de 0 à 3 apparaît une fois : [1, 1, 1, 1].
Entrée :
winning = [7, 8]
tickets = [
[8, 7],
[7, 1],
[1, 7]
]
Sortie attendue :
expected = [0, 2, 1]
Entrée :
std::vector<long long> winning = {7, 8};
std::vector<std::vector<long long>> tickets = {
{8, 7},
{7, 1},
{1, 7}
};
Sortie attendue :
std::vector<long long> expected = {0, 2, 1};
Entrée :
long[] winning = new long[] {7, 8};
long[][] tickets = new long[][] {
new long[] {8, 7},
new long[] {7, 1},
new long[] {1, 7}
};
Sortie attendue :
long[] expected = new long[] {0, 2, 1};
Explication
Un billet a les deux numéros (l'ordre n'a pas d'importance) et deux en ont un : [0, 2, 1].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Placez les numéros gagnants dans un ensemble ou dans un tableau de booléens indexé par numéro.
Indice 2
Comptez les bons numéros d'un billet, puis ajoutez 1 à la case de ce score.
Indice 3
Le résultat a une case de plus qu'il n'y a de numéros gagnants.
Complexité attendue
temps O(t × k), espace supplémentaire O(k)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.