31.整数1出现的次数（从1到n整数中1出现的次数） 求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
方法1. 思路：是从一个数的个位开始，逐位分析，把1出现在各个位的情况考虑一下。 并以此分为三部分：当前分析位cur,当前位之后的数字post（low）和当前位之前的数字pre （high）。 另外根据当前位的高低，设置bit位。如当前位是个位，则bit=1；当前位是十位，则bit=10… 根据当前位cur的数字大小，可以找到如下规律： 1）当前位cur = 0: 当前位出现1的次数为 prebit; 2）当前位cur = 1: 当前位出现1的次数为 post + 1 + prebit; 3）当前位cur > 1: 当前位出现1的次数为（pre+1)*bit。 至于上述规律，我是通过举例分析找到的。 最后将各个位出现1的次数加起来就是答案。 这样时间复杂度只有O(lgn)
public class Solution { public int NumberOf1Between1AndN_Solution(int n) { //记录最大范围值，1出现的个数 int count=0; int cur=0;//当前位的数字 int pre=0;//当前位之前的数字 int post=0;//当前位之后的数字 int i = 0;//用于更新post数值 int bit=1; //每判断一个位置，需要其高位、当前位、及低位数字 while(n!=0){ //每轮的n的末尾数字就是当前位 cur=n;//得到当前分析的数字--个位开始 //高位 pre=n/10; if(cur==0){//如果为0,出现1的次数由高位决定,等于高位数字 * 当前位数 count+=pre*bit; }else if(cur==1){//如果为1,出现1的次数由高位和低位决定,高位*当前位+低位+1 count+=pre*bit+post+1; }else if(cur>1){//如果大于1,出现1的次数由高位决定,//（高位数字+1）* 当前位数 count+=(pre+1)*bit; } bit*=10;//更新bit位 post+=cur*Math.pow(10,i);//更新post //pow(10,i)返回第一个参数10的第二个参数i次方。 n=pre;//更新n i++; } return count; } }法2.循环遍历每一个数是否包含1.
public class Solution { public int NumberOf1Between1AndN_Solution(int n) { int count=0; for(int i=1;i<=n;i++){ int temp=i; while(temp!=0){ if(temp==1){//判断余数是否为1 count++; } temp=temp/10;//这一步可以除以10后判断是否为0 } } return count; } }法3.暴力法：循环遍历，循环统计 思路：
从1到n循环遍历，将n转为字符串
再转为字符数组，循环统计其中含有字符‘1’的个数
2中结果返回给1，累加
public class Solution { public int NumberOf1Between1AndN_Solution(int n) { int count=0; int sum=0; String num=null; for(int i=1;i<=n;i++){ num=String.valueOf(i); count=oneNum(num); sum += count; } return sum; } public int oneNum(String num){ int count=0; char[] ch=num.toCharArray(); for(int i=0;i<ch.length;i++){ if(ch[i]=='1'){ count++; } } return count; }}
