我使用的是分治递归

假设一个数n是91238，或者是13232
递归函数是F(n)
递归三部曲

1. 递归功能：得到0到n之间1的出现次数
2. 终止条件：当0<n<9时，直接返回1
3. 下一次递归：这就是分治了

首先得到n的首位N是多少,示例为9或1
然后得到n是几位数，假设是k位数，示例为5
假设N1 = 10^(N-1)次方，按上面的示例表示10000
然后分情况向下递归：

• 如果首位是1，就分解成F(N1-1)+(n-N1)+F(n-N1)+1;
  -- 就是从0到9999出现多少次1+3232+F(3232)，因为10000后面的数字肯定每出现一次最高位就出现一次1
  加1是因为10000本身出现了一次1.
• 如果首位不是1，就分解成1+F(N1 - 1)+F(n-NN1)+(N1-1)+(NHmax-1)F(N1-1);
  --一样的道理分治成[0,9999],[10000,19999],[20000,89999],[90000,91238]

因为很多次重复计算F[9],F[99],F[999]，因此可以采用一个map映射记住值。

class Solution {
public:
    map<int, int> tmp;
    int numofdigits(int n)
    {
        int s = 0;
        while(n>0)
        {
            s++;
            n = n/10;
        }
        return s;
    }

    unsigned int F(unsigned int n)
    {
        if (n < 1)
            return 0;
        if(tmp.find(n)!=tmp.end())
            return tmp[n];
        int N = numofdigits(n);        // 先找出是几位数
        unsigned int N1 = pow(10, N - 1);
        unsigned int NHmax = n / N1;    // NHmax得到数字首位数
        if (0 < n && n < 9)    // 如果n是个位数 返回1
        {
            tmp[n] = 1;
            return tmp[n];
        }
        else {
            if (NHmax == 1)    // 如果首位数字是1， 返回首位数字加上
            {
                tmp[n] = 1 + F(N1 - 1) + (n - N1) + F(n - N1);
                return tmp[n];
            }
            else
            {
                tmp[n] = 1 + F(N1 - 1) + F(n - NHmax*N1) + (N1-1) + (NHmax-1)*F(N1 - 1);
                return tmp[n];
            }
        }
    }

    int NumberOf1Between1AndN_Solution(int n)
    {
        int s = F(n);
        return s;
    }
};