Đề bài
Trong hệ cơ số b, một số được viết bằng các chữ số từ 0 đến b − 1, trong đó các chữ cái từ A đến Z biểu diễn giá trị từ 10 đến 35. Chẳng hạn FF trong hệ 16 là 255, tức là 377 trong hệ 8 và 11111111 trong hệ 2. Hãy chuyển digits, đang viết ở hệ from_base, thành cùng số đó viết ở hệ to_base.
Hãy viết base_converter(digits, from_base, to_base).
Đầu vào
digits: Số ở hệ from_base, là một chuỗi khác rỗng gồm chữ số và chữ cái in hoa, mỗi ký tự có giá trị nhỏ hơn from_base. Chuỗi có thể có số 0 ở đầu.
from_base: Cơ số của đầu vào.
to_base: Cơ số của kết quả.
Đầu ra
Trả về số ở hệ to_base, dùng 0-9 và chữ in hoa A-Z, không có số 0 ở đầu. Số không được trả về là "0".
Ràng buộc
2 ≤ from_base, to_base ≤ 36
Giá trị của số không vượt quá 10^18.
Ví dụ
Đầu vào:
digits = "FF"
from_base = 16
to_base = 8
Kết quả mong đợi:
expected = "377"
Đầu vào:
std::string digits = "FF";
long long from_base = 16;
long long to_base = 8;
Kết quả mong đợi:
std::string expected = "377";
Đầu vào:
string digits = "FF";
long from_base = 16;
long to_base = 8;
Kết quả mong đợi:
string expected = "377";
Giải thích
FF là 15 × 16 + 15 = 255, và 255 = 3 × 64 + 7 × 8 + 7, nên đáp án là "377".
Đầu vào:
digits = "1010"
from_base = 2
to_base = 36
Kết quả mong đợi:
expected = "A"
Đầu vào:
std::string digits = "1010";
long long from_base = 2;
long long to_base = 36;
Kết quả mong đợi:
std::string expected = "A";
Đầu vào:
string digits = "1010";
long from_base = 2;
long to_base = 36;
Kết quả mong đợi:
string expected = "A";
Giải thích
1010 ở hệ nhị phân là 10, trong hệ 36 chỉ là một chữ số "A".
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Duyệt đầu vào từ trái sang phải, nhân giá trị hiện tại với from_base rồi cộng thêm từng chữ số.
Gợi ý 2
Để viết kết quả, lấy số dư khi chia cho to_base; chúng xuất hiện theo thứ tự từ chữ số cuối lên.
Gợi ý 3
Xử lý riêng số không để kết quả là "0" chứ không phải chuỗi rỗng.
Độ phức tạp mong đợi
thời gian O(L), bộ nhớ phụ O(L), với L là số chữ số
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.