题目

  • 求出1—13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1-13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

思路

  • 常规思路：每个数字都考虑一下，判断每个数自的含有几个1

  • 最优思路：从数字规律着手，明显提高时间效率的解法

代码

  • 常规思路
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int nums=0;
        for(int i=1;i<=n;i++){
            nums+= Find(i);
        }
        return nums;
    }
    public int Find(int n){
        int nums = 0;
        while(n>0){
            if(n%10==1)
                nums++;
            //改变数据的位数，减少一个位数
            n = n/10;
        }
        return nums;
    }
}
  • 最优思路
int NumberOf1Between1AndN_Solution(int n)
    {
        int cnt = 0;
        int a=0,b=0;
        for(long long m=1;m<=n;m*=10){
            a = n/m;
            b = n%m;
            cnt+=(a+8)/10*m + (a%10==1)*(b+1);
        }
        return cnt;
    }

注解：参考一位牛友提到的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时，为3142100，因为当百位数大于1时，前缀可以为0，即百位数可以从100到199，共100个数；当百位数不大于1时，为3141100；如何判断百位数是否大于1？假设百位数为x，若（x+8）/10等于1，则大于1，若（x+8）/10等于0，则小于1。因此前缀可用（n/m + 8）/10 m来计算(若计算2的个数，可以改为（n/m + 7）/10m,若计算3的个数，改为（n/m + 6）/10*m，…以此类推)。

再例如m=1000时，n分为a=3141和 b=592；千位数的前缀为314，千位数不大于1，故前缀计算为3141000；因为千位数为1，再加b+1(0到592)。即千位数为1的所有书的个数和为3141000+592+1；公式（n/m + 8）/10*m + b +1。

注意：只有n的第m位为1时需要计算后缀，后缀计算为 （n/m%10==1）*(b+1)，

即（n/m%10<mark>1）判断第m位是否为1，若为1，则加上（b+1），若不为1，则只计算前缀。（若计算2的个数，可以改为（n/m%10</mark>2）(b+1)，若计算3的个数，可以改为（n/m%10==3）(b+1)…以此类推）