Đếm số trong phạm vi

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

Vì vậy, nếu đầu vào là d =1, thấp =1, cao =13, thì đầu ra sẽ là 6, vì chữ số d =1 xảy ra 6 lần như 1,10,11,12,13.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm zero (), điều này sẽ lấy n,

ret:=0, x:=0
nếu n giống 0 thì -
- trả lại 1
để khởi tạo m:=1, khi m <=n, cập nhật m:=m * 10, do -
- a:=n / m
- b:=n mod m
- z:=a mod 10
- nếu số chữ số trong m giống với số chữ số trong n, thì -
  - Ra khỏi vòng lặp
- nếu z> x, thì -
  - ret:=ret + ((a / 10) + 1)
- ngược lại khi z giống với x thì
  - ret:=ret + ((a / 10) * m + (b + 1))
- Nếu không
  - ret:=ret + (a / 10)
trả lại ret
Xác định một hàm f (), điều này sẽ nhận x, n,
ret:=0
để khởi tạo m:=1, khi m <=n, cập nhật m:=m * 10, do -
- 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 với x thì -
  - ret:=ret + ((a / 10) * m + (b + 1))
- Nếu không
  - ret:=ret + (a / 10)
- nếu x giống 0 thì -
  - ret:=ret - m
trả lại ret
Từ phương thức chính, hãy làm như sau
trả lại ret
return f (d, high - f (d, low - 1))

Hãy cùng chúng tôi xem cách 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

Đếm số trong phạm vi

Ví dụ

Đầu vào

Đầu ra