image.png
思路:
00100~00199
,01100~01199
,……,20100~20199
。一共有21*100种情况,即high*100;01000~01999
,11000~11999
,21000~21034
。一共有2*1000+(34+1)种情况,即high*1000+(low+1)。00010~00019
,00110~00119
,……,21010~21019
。一共有(210+1)*10种情况,即(high+1)*10。代码:
public int NumberOf1Between1AndN_Solution(int n) {
int count=0;
for (int i = 1; i <=n; i*=10) {
//更高位的((数字
int high=n/i*10;
//更低位数字
int low=n%i;
//当前位数字
int curr=n/i%10;
if (curr==0){
count+=high*10;
}else if (curr==1){
count+=high*i+(low+1);
}else {
count+=(high+1)*i;
}
}
return count;
}
注解:参考一位牛友提到的leetcode的链接网址(包括求1~n的所有整数中2,3,4,5,6,7,8,9出现的所有次数) 通过使用一个 位置乘子m 遍历数字的位置, m 分别为1,10,100,1000…etc.(m<=n)
对于每个位置来说,把10进制数分成两个部分,比如说 当m=100的时候, 把十进制数 n=3141592 分成 a=31415 和 b=92 ,以此来分析百位数为1时所有数的个数和。m=100时,百位数的前缀为3141,当百位数大于1时,为3142*100,因为当百位数大于1时,前缀可以为0,即百位数可以从100到199,共100个数;当百位数不大于1时,为3141*100;如何判断百位数是否大于1?假设百位数为x,若(x+8)/10等于1,则大于1,若(x+8)/10等于0,则小于1。因此前缀可用(n/m + 8)/10 *m来计算(若计算2的个数,可以改为(n/m + 7)/10*m,若计算3的个数,改为(n/m + 6)/10*m,…以此类推)。
再例如m=1000时,n分为a=3141和 b=592;千位数的前缀为314,千位数不大于1,故前缀计算为314*1000;因为千位数为1,再加b+1(0到592)。即千位数为1的所有书的个数和为314*1000+592+1;公式(n/m + 8)/10*m + b +1。
注意:只有n的第m位为1时需要计算后缀,后缀计算为 (n/m%10==1)*(b+1),另外a+8的巧妙之处在于当a的最后一位(当前分析位)为0或1时,加8不产生进位,这是为需要单独算的特殊情况做准备,而当前分析位为2~9时,不需要考虑特殊情况,所以允许加8产生的进位。
即(n/m%10==1)判断第m位是否为1,若为1,则加上(b+1),若不为1,则只计算前缀。(若计算2的个数,可以改为(n/m%10==2)*(b+1),若计算3的个数,可以改为(n/m%10==3)*(b+1)…以此类推)
代码:
public int NumberOf1Between1AndN_Solution(int n) {
int count = 0;
//m为个位, 十位 百位 千位....
for (long m = 1; m <= n; m *= 10) {
//n除以基数后的数
long a = n / m;
//n在基础上的数
long b = n % m;
//a%10表示上一位是否为1,为0?后一位为几就加几:0
count+=(a+8)/10*m+(a%10==1?b+1:0);
}
return count;
}