Problem
Bei einer Spendenaktion der Schule gibt es eine Zahlenlotterie. Bei der Ziehung werden einige verschiedene Gewinnzahlen gezogen, und auf jedem Los steht dieselbe Anzahl verschiedener Zahlen. Die Reihenfolge der Zahlen auf einem Los spielt keine Rolle; die Trefferzahl eines Loses ist die Anzahl seiner Zahlen, die Gewinnzahlen sind. Um die Preise festzulegen, müssen die Veranstalter wissen, wie viele Lose welche Trefferzahl erreicht haben.
Implementiere ticket_lottery(winning, tickets).
Eingabe
winning: Die verschiedenen Gewinnzahlen.
tickets: Die Lose; jede Zeile enthält die verschiedenen Zahlen eines Loses und ist genauso lang wie winning.
Ausgabe
Gib eine Liste der Länge len(winning) + 1 zurück, in der an Position k die Anzahl der Lose steht, die genau k Gewinnzahlen getroffen haben.
Einschränkungen
1 ≤ len(winning) ≤ 10
0 ≤ Anzahl der Lose ≤ 5000
1 ≤ jede Zahl ≤ 99
Beispiele
Eingabe:
winning = [3, 11, 20]
tickets = [
[3, 11, 20],
[20, 5, 7],
[1, 2, 4],
[11, 3, 9]
]
Erwartete Ausgabe:
expected = [1, 1, 1, 1]
Eingabe:
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}
};
Erwartete Ausgabe:
std::vector<long long> expected = {1, 1, 1, 1};
Eingabe:
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}
};
Erwartete Ausgabe:
long[] expected = new long[] {1, 1, 1, 1};
Erläuterung
Die Lose treffen 3, 1, 0 und 2 Zahlen, also kommt jede Trefferzahl von 0 bis 3 genau einmal vor: [1, 1, 1, 1].
Eingabe:
winning = [7, 8]
tickets = [
[8, 7],
[7, 1],
[1, 7]
]
Erwartete Ausgabe:
expected = [0, 2, 1]
Eingabe:
std::vector<long long> winning = {7, 8};
std::vector<std::vector<long long>> tickets = {
{8, 7},
{7, 1},
{1, 7}
};
Erwartete Ausgabe:
std::vector<long long> expected = {0, 2, 1};
Eingabe:
long[] winning = new long[] {7, 8};
long[][] tickets = new long[][] {
new long[] {8, 7},
new long[] {7, 1},
new long[] {1, 7}
};
Erwartete Ausgabe:
long[] expected = new long[] {0, 2, 1};
Erläuterung
Ein Los hat beide Zahlen (die Reihenfolge spielt keine Rolle) und zwei haben eine: [0, 2, 1].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Leg die Gewinnzahlen in ein Set oder in ein boolesches Array, das über die Zahl indiziert wird.
Hinweis 2
Zähle die Treffer eines Loses und erhöhe dann den Zähler für diese Trefferzahl um 1.
Hinweis 3
Das Ergebnis hat einen Zähler mehr, als es Gewinnzahlen gibt.
Erwartete Komplexität
Zeit O(t × k), zusätzlicher Speicher O(k)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.