Tất cả thử thách
Khó 1 đã giải Tỷ lệ chấp nhận 100.0%

Đếm Số Có Các Chữ Số Kề Nhau Khác Nhau

Đếm các giá trị trong một đoạn mà các chữ số thập phân liền kề không bao giờ giống nhau.

Bạn sẽ học được gì

  • Đếm các số đến một giới hạn theo từng chữ số
  • Theo dõi chữ số trước và cận chặt
  • Trả lời một đoạn bằng f(b) - f(a - 1)

Đề bài

Xem bản gốc (English)

Đếm các số nguyên từ left đến right, bao gồm cả hai đầu mút, mà không có hai chữ số liền kề nào giống nhau. Sử dụng cách viết thập phân thông thường, không có số 0 ở đầu. Số 0 và tất cả các số một chữ số khác đều thỏa mãn điều kiện này.

Cài đặt hàm counting_numbers(left, right).

Đầu vào

left: Giá trị nhỏ nhất được phép.

right: Giá trị lớn nhất được phép.

Đầu ra

Trả về số lượng giá trị thỏa mãn điều kiện trên.

Ràng buộc

0 ≤ left ≤ right ≤ 10¹⁸. Đoạn giá trị có thể quá lớn để kiểm tra từng số một cách tuần tự.

Ví dụ

Ví dụ 1
Đầu vào:
left = 10
right = 15

Kết quả mong đợi:
expected = 5
Đầu vào:
long long left = 10;
long long right = 15;

Kết quả mong đợi:
long long expected = 5;
Đầu vào:
long left = 10;
long right = 15;

Kết quả mong đợi:
long expected = 5;

Giải thích

Chỉ có số 11 là có hai chữ số liền kề giống nhau. Năm số còn lại đều thỏa mãn điều kiện.

Ví dụ 2
Đầu vào:
left = 0
right = 9

Kết quả mong đợi:
expected = 10
Đầu vào:
long long left = 0;
long long right = 9;

Kết quả mong đợi:
long long expected = 10;
Đầu vào:
long left = 0;
long right = 9;

Kết quả mong đợi:
long expected = 10;

Giải thích

Cả mười giá trị đều là số một chữ số nên không có hai chữ số liền kề giống nhau.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Đếm các số hợp lệ đến từng đầu mút rồi trừ để lấy kết quả trên đoạn.

Gợi ý 2

Digit DP rất hợp vì tính hợp lệ phụ thuộc vào các chữ số kề nhau và việc đã bắt đầu số hay chưa.

Gợi ý 3

Số 0 ở đầu cần xử lý riêng để các số ngắn hơn được đếm đúng.

Độ phức tạp mong đợi

thời gian O(k * 10 * states), bộ nhớ phụ O(k * states)

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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 807 ms - 5/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.