摘要: 计算从m到n的所有数字中0~9的个数,可先计算0~m中0~9的个数,存放在数组ans中,再计算0~n中的个数,存放在数组cnt中,然后数组想减。
solve函数以123为例,先看以12开头的数,可知各位只能是0,1,2,3;在cnt数组中下标为0,1,2,3(共4个数)的数分别加1,然后计算此时120~123这数中1和2出现的个数(不算个位,个位已经加过),即为4次;然后cnt[1]+=4,cnt[2]+=4;然后考虑从0到119中个位数字出现的次数,为123/10=12次。这都是个位情况,若处理十位则要考虑到本来十位数后面还跟有10个个位数,计算十位数字个数要乘以10,同样,百位数要乘1000.......(不多说)
关键在处理个位0时要小心,每次让cnt[0]-=opera,因为计算12时(也就是递归的第二层),会再次得到一个0,然后把0*opera加入到cnt[0]中,此时已出现重复,应把重复的计算消灭掉
阅读全文