Đề bài
Trong một buổi bốc thăm, mỗi tên được chấm điểm. Trước hết, sắp xếp các tên theo thứ tự bảng chữ cái. Giá trị chữ cái của một tên là tổng các chữ cái trong tên, với A = 1, B = 2, ..., Z = 26. Điểm của tên bằng giá trị đó nhân với vị trí của tên trong danh sách đã sắp xếp, đếm từ 1.
Hãy viết name_scores(names).
Sắp xếp theo thứ tự ký tự thông thường, nên một tên luôn đứng trước mọi tên dài hơn bắt đầu bằng nó ("AA" đứng trước "AAB").
Đầu vào
names: Các tên viết bằng chữ in hoa từ A đến Z. Một tên có thể xuất hiện nhiều lần; mỗi lần được tính điểm theo vị trí riêng của nó.
Đầu ra
Trả về tổng tất cả các điểm. Danh sách rỗng thì trả về 0.
Ràng buộc
0 ≤ names.length ≤ 1000; 1 ≤ độ dài tên ≤ 20
Ví dụ
Đầu vào:
names = ["NORA", "ABE", "LIAM"]
Kết quả mong đợi:
expected = 222
Đầu vào:
std::vector<std::string> names = {"NORA", "ABE", "LIAM"};
Kết quả mong đợi:
long long expected = 222;
Đầu vào:
string[] names = new string[] {"NORA", "ABE", "LIAM"};
Kết quả mong đợi:
long expected = 222;
Giải thích
Sau khi sắp xếp: ABE (8) × 1, LIAM (35) × 2, NORA (48) × 3, tổng 8 + 70 + 144 = 222.
Đầu vào:
names = ["ZOE", "AMY", "AMY"]
Kết quả mong đợi:
expected = 255
Đầu vào:
std::vector<std::string> names = {"ZOE", "AMY", "AMY"};
Kết quả mong đợi:
long long expected = 255;
Đầu vào:
string[] names = new string[] {"ZOE", "AMY", "AMY"};
Kết quả mong đợi:
long expected = 255;
Giải thích
Sau khi sắp xếp: AMY, AMY, ZOE. AMY có giá trị 39 và ZOE là 46: 39 × 1 + 39 × 2 + 46 × 3 = 255.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Sắp xếp trước rồi mới tính điểm; vị trí phụ thuộc vào thứ tự sau khi sắp xếp.
Gợi ý 2
Giá trị của một chữ cái là mã ký tự của nó trừ đi mã của 'A' rồi cộng 1.
Gợi ý 3
Vị trí bắt đầu từ 1, không phải 0.
Độ phức tạp mong đợi
thời gian O(n log n × L), bộ nhớ phụ O(n)
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.