代码如下
class Solution {
public int numberOf1Between1AndN_Solution(int n) {
return f(n);
}
private int f(int n){
if(n<=0) return 0;
String s=String.valueOf(n);
int len=s.length();
//最高位数字
int high=s.charAt(0)-'0';
//当前数量级,比如100,1000,10000
int cur=(int)Math.pow(10,len-1);
//除了最高位,其他数字 比如1234减去数量级1000就剩234
int last=n-high*cur;
//以1234 和2345举例
//我们先求1-999,为f(cur-1) 然后有带着千分位的1000-1234中有 1+last个 最后求不包含千分位中 f(last)
if(high==1) return f(cur-1)+1+last+f(last);
//同理可得
else return f(cur-1)*high+cur+f(last);
}
}
emmmmmmmmmmm……