题目:获取从1到n整数中1出现的次数,如n=13,则1,10,11,12,13中出现1的次数总共为6,则返回6
参数:范围的最大值n
方法一:递归方法(参考力扣答案)
思路:
f(n)为1-n范围内,这n个数中1出现的次数
首先将n分为两种情况:情况一:最高位为1(如1234);情况二:最高位不为1(如3234)
情况一:当最高位为1时(以1234为例):
①:将n分为两部分,最高位单独拿出来为1,定义为high;剩下的部分为234,定义为last;
②:获取到最高位的分位,为千分位,即定义pow=1000;
③将数据n定义两个范围:
    1.1-999范围内,1的个数为f(pow-1);
    2.1000-1234范围内:
        1)首先只考虑千分位是1的个数:也就是1000、1001、1002...1234,即234+1,转换下为:last+1
        2)其次考虑其他位数上的1的个数为:f(last)。
综上所述:情况一中1出现的次数为:f(pow-1)+last+1+f(last)
情况二:当最高为不为1时(以3234为例):
①:1-999范围内,1的个数依然为:f(pow-1);
②:1000-1999范围内:
    1)只考虑千分位是1的个数为:1000、1001、1002...1999即1000个也就是pow;
    2)其他位数上1的数量为:f(pow-1)
③:2000-2999范围内1的个数:f(pow-1),注意这里的千分位是2,所以不要考虑分两种情况
④:3000-3234范围内1的个数:f(last)
综上所述:情况二中1出现的次数为:pow+high*f(pow-1)+f(last);
测试结果:10ms;9288k
代码如下: 
public int NumberOf1Between1AndN_Solution(int n){
     //base case
        if(n<1){
            return 0;
        }
        if(n<10){
            return 1;
        }
        String s=String.valueOf(n);
        int high=s.charAt(0)-'0';
        int pow=(int)Math.pow(10,s.length()-1);
        int last=n-high*pow;
        if(high==1){
            return NumberOf1Between1AndN_Solution(pow-1)+last+1+NumberOf1Between1AndN_Solution(last);
        }else{
            return pow+high*NumberOf1Between1AndN_Solution(pow-1)+NumberOf1Between1AndN_Solution(last);
        }
}
附上参考地址:
思路:挨个获取到每个数字,然后每个分位上判断1的数量,然后将所有数量进行相加(不推荐) 
    //①:遍历获取从1-n的每个数
    //②:计算每个数包含1的数量:即先计算个位上的,n%10==1,数值相应加1
    //③:将原数依次/10,按照②步骤计算十位上1数量,依次类推
 public int NumberOf1Between1AndN_Solution(int n){
       //base case
        if(n<1){
            return 0;
        }
        if(n<10){
            return 1;
        }
        int cnt=0;
        for(int i=n;i>0;i--){
            for(int j=i;j>0;j/=10){
                if(j%10==1){
                    cnt++;
                }
            }
        }
        return cnt;
 }