43-1～n 整数中1出现的次数

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

暴力解法

我们可以遍历1-n，计算每个数字含有1的个数。在计算过程中，我们可以从小到大遍历，使用数组存储索引对应的1的个数。比如nums[1]=1表示1这个数字含有1的个数是1，计算nums[11]:

1. 11 % 10 = 1，表示11含有的1的个数是1含有1的个数基础上加1。
2. 10 % 10 = 0，表示10含有1的个数就是1含有1的个数。

 public int countDigitOne(int n) {
       if(n == 0 ){
            return 0;
        }
        int[] array = new int[n+1];

        int count = 0;
        for (int i = 1; i <= n; i++) {
             if(i % 10 == 1) {
                 array[i] = array[i / 10] + 1;
             }else{
                 array[i] = array[i / 10];
             }
            count += array[i];
        }
        return count;
    }

思想是后续数字含有1的个数是在前面数字基础上计算(加1或者不加1的)得到的。不过这个方法问题是耗内存，导致无法通过leetcode的测试用例。

找规律

参考

简而言之，就是就数字分为最高位和其他位，比如1234，分成1和234，然后拆成0-999到1000-1234，然后分别计算。假如高位不是1，那么需要考虑的情况更多一些。

我们使用f(n)表示n含有1的个数。

当高位是1时：比如1234，

pow表示位数^10，pow=1000，

hi表示最高位，hi=1

last表示其他位，last = 234

可以分为下面几种情况：

• 0-999，含有1的个数是f(999)，即f(pow-1)
• 1000-1234，含有1的个数是234+1+f(234)，这里的234+1表示1000-1234里仅千分位为1的，这里不考虑1111里的百分位、十分位和个位，那么显然是234+1个，而f(234)表示的是000-234里含有1的个数，这里就包括了1111里的后三位。即last+1+f(last)

最终为f(pow-1)+f(last) + last + 1

如果最高位不是1，比如3456

pow = 1000，hi=3，last=456，那么分成以下几种情况

• 0-999 含有1的个数是f(999),即f(pow-1)
• 1000-1999 含有1的个数是是pow + f(pow - 1)
• 2000-2999 含有1的个数是f(pow-1)
• 3000-3456 含有1的个数是f(last)

最终为hi * f(pow - 1) + pow+ f(last)

  public int countDigitOne(int n) {
        if(n == 0){
            return 0;
        }
        return f(n);
    }

    private int f(int n) {
        if (n <= 0) {
            return  0;
        }
        char[] ch = String.valueOf(n).toCharArray();
        int high = ch[0] - '0';
        int pow = (int) Math.pow(10, ch.length - 1);
        int last = n - high * pow;
        if(high == 1){
            return f(pow - 1) + f(last) + 1 + last;
        }else{
            return pow + high * f(pow - 1) + f(last);
        }
    }