计数问题
(计数问题) $O(mlogn)$
/
001~abc-1, 999
abc
1. num[i] < x, 0
2. num[i] == x, 0~efg
3. num[i] > x, 0~999
/
时间复杂度
mlogn
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int N = 10;
// 统计值
int get(vector<int> num, int l, int r)
{
int res = 0;
for (int i = l; i >= r; i -- ) res = res * 10 + num[i];
return res;
}
int count(int n, int x)
{
if (!n) return 0;
vector<int> num;
while (n)
{
num.push_back(n % 10);
n /= 10;
}
n = num.size();
int res = 0;
// 从高位到低位遍历 -!x是因为找0不可能从第一位开始找,而其余的1-9第一位也可能有下面的九种情况
// 分开讨论一下就行了, 从高位开始遍历
for (int i = n - 1 - !x; i >= 0; i -- )
{
if (i < n - 1)
{
res += get(num, n - 1, i + 1) * pow(10, i);
if (!x) res -= pow(10, i); // 0不配拥有全前导0的情况,要减去
}
if (num[i] == x) res += get(num, i - 1, 0) + 1; // 从0开始计数
else if (num[i] > x) res += pow(10, i); // 这样就只跟位数有关了 0-999
}
return res;
}
int main()
{
int a, b;
while (cin >> a >> b , a)
{
if (a > b) swap(a, b);
for (int i = 0; i <= 9; i ++ )
cout << count(b, i) - count(a - 1, i) << ' ';
cout << endl;
}
return 0;
}