求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

参考思路：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/javadi-gui-by-xujunyi/

解题思路

f(n))函数的意思是1～n这n个整数的十进制表示中1出现的次数，将n拆分为两部分，最高一位的数字high和其他位的数字last，分别判断情况后将结果相加，看例子更加简单。

1.例子如n=1234，high=1, pow=1000, last=234
可以将数字范围分成两部分1-999和1000-1234
1-999这个范围1的个数是f(pow-1)

1000-1234这个范围1的个数需要分为两部分：
千分位是1的个数：千分位为1的个数刚好就是234+1(last+1)，注意，这儿只看千分位，不看其他位
其他位是1的个数：即是234中出现1的个数，为f(last)
所以全部加起来是f(pow-1) + last + 1 + f(last);

2.例子如3234，high=3, pow=1000, last=234
可以将数字范围分成两部分1-99，1000-1999，2000-2999和3000-3234

1-999这个范围1的个数是f(pow-1)
1000-1999这个范围1的个数需要分为两部分：
千分位是1的个数：千分位为1的个数刚好就是pow，注意，这儿只看千分位，不看其他位
其他位是1的个数：即是999中出现1的个数，为f(pow-1)
2000-2999这个范围1的个数是f(pow-1)
3000-3234这个范围1的个数是f(last)
所以全部加起来是pow + high*f(pow-1) + f(last);

 int NumberOf1Between1AndN_Solution(int n)
    {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 1;
        //用to_string(int i) : 将 int 变量 i 转换成字符串 ,求取变量n的最高位
        string str = to_string(n);
        int length = str.size();
        int pow_n = pow(10, length-1);
        int high = str[0] - '0';
        int low = n - high*pow(10, length-1);
        if (high == 1)
            return NumberOf1Between1AndN_Solution(pow_n - 1) + low + 1 + NumberOf1Between1AndN_Solution(low);
        else
            return NumberOf1Between1AndN_Solution(low) + high * NumberOf1Between1AndN_Solution(pow_n - 1) + pow_n;
    }