Đề bài
Buổi gây quỹ của trường tổ chức một cuộc xổ số. Lượt quay chọn ra một số con số trúng thưởng khác nhau, và mỗi vé có cùng số lượng con số, các số trên vé cũng khác nhau. Thứ tự các số trên vé không quan trọng; điểm của một vé là số con số trên vé trùng với số trúng thưởng. Để định cơ cấu giải thưởng, ban tổ chức cần biết có bao nhiêu vé đạt mỗi mức điểm.
Hãy viết ticket_lottery(winning, tickets).
Đầu vào
winning: Các số trúng thưởng, khác nhau đôi một.
tickets: Các vé; mỗi hàng chứa các số khác nhau trên một vé, có cùng độ dài với winning.
Đầu ra
Trả về một danh sách độ dài len(winning) + 1, trong đó vị trí k là số vé trùng đúng k số trúng thưởng.
Ràng buộc
1 ≤ len(winning) ≤ 10
0 ≤ số vé ≤ 5,000
1 ≤ mỗi số ≤ 99
Ví dụ
Đầu vào:
winning = [3, 11, 20]
tickets = [
[3, 11, 20],
[20, 5, 7],
[1, 2, 4],
[11, 3, 9]
]
Kết quả mong đợi:
expected = [1, 1, 1, 1]
Đầu vào:
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}
};
Kết quả mong đợi:
std::vector<long long> expected = {1, 1, 1, 1};
Đầu vào:
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}
};
Kết quả mong đợi:
long[] expected = new long[] {1, 1, 1, 1};
Giải thích
Các vé lần lượt trùng 3, 1, 0 và 2 số, nên mỗi mức điểm từ 0 đến 3 xuất hiện đúng một lần: [1, 1, 1, 1].
Đầu vào:
winning = [7, 8]
tickets = [
[8, 7],
[7, 1],
[1, 7]
]
Kết quả mong đợi:
expected = [0, 2, 1]
Đầu vào:
std::vector<long long> winning = {7, 8};
std::vector<std::vector<long long>> tickets = {
{8, 7},
{7, 1},
{1, 7}
};
Kết quả mong đợi:
std::vector<long long> expected = {0, 2, 1};
Đầu vào:
long[] winning = new long[] {7, 8};
long[][] tickets = new long[][] {
new long[] {8, 7},
new long[] {7, 1},
new long[] {1, 7}
};
Kết quả mong đợi:
long[] expected = new long[] {0, 2, 1};
Giải thích
Một vé có cả hai số (thứ tự không quan trọng) và hai vé có một số: [0, 2, 1].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Đưa các số trúng thưởng vào một tập hợp hoặc một mảng boolean đánh chỉ số theo giá trị.
Gợi ý 2
Đếm số con số trùng trên một vé, rồi cộng 1 vào ô ứng với mức điểm đó.
Gợi ý 3
Kết quả có số ô nhiều hơn số lượng số trúng thưởng đúng một.
Độ phức tạp mong đợi
thời gian O(t × k), bộ nhớ phụ O(k)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.