一、问题描述
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
题目链接：数字 1 的个数
二、题目要求
样例 1
输入： n = 13 输出： 6
样例 2
输入： n = 0 输出： 0
考察
数学思想、超时优化 建议用时15~35min
三、问题分析
这一题我一拿到手就感觉不对劲，明明很简单的一道题，只需要循环统计就行了，力扣居然为它加上困难的标签。
classSolution { public: intcountDigitOne(intn) { inti,k,ans=0;//初始化数据for(i=1;i<=n;i++)//循环1~n { k=i; while(k)//数位中是否包含1 { if(k%10==1) ans++;//计数k=k/10; } } returnans;//输出结果 } };
所以，我的代码肯定会超时。
看了题解>_<发现，这是一道规律题：
规律如下，借鉴了大佬的思路：
/**从低往高位，计算每一位的数量：第1位上的1的个数：1+(n-1)/10第2位上的1的个数：(1+(n/10-1)/10)*10第3位上的1的个数：(1+(n/100-1)/10)*100……第k+1位上的1的个数：(1+(n/(10^k)-1)/10)*(10^k)如果n的第k+1位上是1，则说明可能没有填满该位，计算第k+1位的数量时还要 -10^k+1+n%(10^k)，相当于独立计算*/
四、编码实现
classSolution { public: intcountDigitOne(intn) { longlongk=1,ans=0;//初始化数据while (n>=k){ ans+= (1+(n/k-1)/10)*k;//计数if (n/k%10==1) ans=ans-k+1+n%k;//当前位为1，减去数据k*=10; } returnans;//输出结果 } };
