Đếm chữ số trong phạm vi

Giả sử chúng ta có một số nguyên d giữa 0 và 9, chúng ta cũng có hai số nguyên dương low và high làm giới hạn dưới và trên. Chúng ta phải tìm số lần d xuất hiện như một chữ số trong tất cả các số nguyên giữa low và high, bao gồm cả ranh giới low và high.

Vì vậy, nếu đầu vào là d = 1, low = 1, high = 13, đầu ra sẽ là 6, vì chữ số d=1 xuất hiện 6 lần như 1,10,11,12,13.

Để giải quyết, chúng ta sẽ làm theo các bước:

Định nghĩa hàm zero(), nhận n,

• ret := 0, x := 0

• nếu n giống 0, thì:

  • Trả về 1

Khởi tạo m := 1, khi m <= n, cập nhật m := m * 10, làm:

• a := n / m

• b := n mod m

• z := a mod 10

• nếu số chữ số của m giống số chữ số của n, thì:

  • Thoát khỏi vòng lặp

• nếu z > x, thì:

  • ret := ret + ((a / 10) + 1)

• ngược lại khi z giống x, thì

  • ret := ret + ((a / 10) * m + (b + 1))

• Khác

  • ret := ret + (a / 10)

• Trả về ret

• Định nghĩa hàm f(), nhận x, n,

• ret := 0

• Khởi tạo m := 1, khi m <= n, cập nhật m := m * 10, làm:

  • a := n / m

  • b := n mod m

  • z := a mod 10

  • nếu z > x, thì:

    • ret := ret + ((a / 10) + 1)

  • ngược lại khi z giống x, thì:

    • ret := ret + ((a / 10) * m + (b + 1))

  • Khác

    • ret := ret + (a / 10)

  • nếu x giống 0, thì:

    • ret := ret - m

• Trả về ret

• Từ phương thức main làm sau

• Trả về ret

• Trả về f(d, high - f(d, low - 1))

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int digitCount(int x){       int ret = 0;       while (x) {          ret++;          x /= 10;       }       return ret;    }    int zero(int n){       int ret = 0;       int x = 0;       if (n == 0)       return 1;       for (int m = 1; m <= n; m *= 10) {          int a = n / m;          int b = n % m;          int z = a % 10;          if (digitCount(m) == digitCount(n))          break;          if (z > x) {             ret += ((a / 10) + 1) * m;          }          else if (z == x) {             ret += (a / 10) * m + (b + 1);          } else {             ret += (a / 10) * m;          }          cout << ret << endl;       }       return ret;    }    int f(int x, int n){       int ret = 0;       for (int m = 1; m <= n; m *= 10) {          int a = n / m;          int b = n % m;          int z = a % 10;          if (z > x) {             ret += ((a / 10) + 1) * m;          }          else if (z == x) {             ret += (a / 10) * m + (b + 1);          } else {             ret += (a / 10) * m;          }          if (x == 0) {             ret -= m;          }       }       return ret;    }    int digitsCount(int d, int low, int high){       return f(d, high) - f(d, low - 1);    } }; main(){    Solution ob;    cout << (ob.digitsCount(1,1,13)); }

Đầu vào

1,1,13

Đầu ra

6