AcWing 338. 计数问题(对0的处理 其实很简单)
原题链接
中等
作者:
GinSoda
,
2019-10-11 20:58:11
,
所有人可见
,
阅读 1266
/*
acwing338是 acwing56/剑指offer44 统计1-n中1出现的次数 的拓展
思路:
1、求整数1~n中1出现的次数
对每一位计数
对每一位,统计两边出现的次数(分类讨论)
(1)比如n=11230,百位数是2。当百位数取1的时候,左边是0~11,右边是0~99,一共是12*100次
(2)比如n=11130,百位数是1。当百位数取1的时候,
左边是0~10,右边是0~99.左边是11,右边是0~30.一共是11*100+1*31次
(3)比如n=11030,百位数是0。当百位数取1的时候,左边是0~10,右边是0~99,一共是11*100次
公式 left = 112, right = 30
answer = (left + 8)//10 * 100 + [(right + 1) if left%10是1 else 0]
注意点:n=1输出res=1,所以注意i<=n
2、对非0计数
count(n, num): 求1~n中num出现的次数,num属于0-9
count(n, num) = (left + 9 - num)//10 * 100 + [(right + 1) if left%10==num else 0]
count(m, n, num): 求m~n中num出现的次数,num属于0-9
count(m, n, num) = count(n, num) - count(m - 1, num)
3、对0计数
把0当作正常数对待,所以当n = 324时
会如此计数: 000 001 002 …… 010 011 …… 099, 0被多数了110次(百位出现100次,十位出现10次)
对于0, 我们最后减去 111……110, 位数和n相同
4、时间复杂度:(10个数字 * 2遍 * 最多8位数 * 10(对d循环)) = 1600
*/
# include <iostream>
# include <cmath>
using namespace std;
int cnt(int n, int num) {// 计算从1到n的整数中数字num出现多少次
int res = 0;
int left = 0, right = 0, i = 1; // 数字高位,数字低位, 第几位
int zero_bias = 0;
while (i <= n) {
left = n / i, right = n % i;
res += (left + 9 - num) / 10 * i;
if (left % 10 == num)
res += (right + 1);
if(!num)
zero_bias += i;
i *= 10;
}
if(!num)
zero_bias -= 1;
return res - zero_bias;
}
int main() {
int a, b;
while (cin >> a >> b , a) {
if (a > b) swap(a, b);
for (int i = 0; i <= 9; ++ i)
cout << cnt(b, i) - cnt(a - 1, i) << ' ';
cout << endl;
}
return 0;
}
%%%