《剑指offer》 第43题 从1到n中 1出现次数

思路1：将所有数字转换成字符串，再遍历每个字符串的每一位。当n位数较大时，时间复杂度会比较高
思路2：与思路1相似，每次对10取模，然后判断个位数是否为1，当n位数大时，时间复杂度也比较高.
思路3及4：既然蛮力不好用，自然需要找规律，也就是1出现的规律。

首先附上一段思路1和2的代码，然后对思路3进行分析

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count = 0;
        for(int i = 0; i <= n; i++) {
            String str = String.valueOf(i);
            for(int j = 0; j < str.length(); j++) {
                if(str.charAt(j) == '1')
                    count++;
            }
        }
        return count;
    }
}
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        //count表示1出现的总次数
        int count = 0;
        //从1到n循环n次，对每一个数求它包含多少个1
        for (int i = 1; i <= n; i++) {
            int temp = i;
            //求这个数包含多少个1
            while (temp != 0) {   
                if (temp % 10 == 1) {
                    count++;
                }
                temp = temp / 10;
            }
        }
        return count;
    }
}

思路3：
很明显，在拿到比如34567这个数时，进行分段处理。
最直观的方式是分成1-9999和10000-19999和20000到34567三个部分来进行计算时，显然我们还需要将20000到34567继续分，分成（20000，29999）和（30000，34567），而（30000，34567）还需要分为（30000，33999）和（34000，34567），还要继续分，这种分法虽然有一定的规律性，但是写起来稍微复杂，因此我们考虑换一种分的方式
那就是将首位剥夺。即分成(1,4567)和(4568，34567),而4567再分成(1,567)和(568,4567)，而(1,567)再分成（1，67）和（68，567）....
显然第二种分法规律性更强，分成的组数也更少，可以使用递归.（看起来比较费劲，先mark一下，以后再来学习）

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        if(n<=0||n==1){
            return n;
        }
    String str=n+"";              
        return numberOf1(str);  
    }

    public static int numberOf1(String str){
        char[] strN=str.toCharArray();
        int length=strN.length;       
        if(length==1&&strN[0]=='0'){
            return 0;
        }
        if(length==1&&strN[0]>'1'){
            return 1;
        }
        int numFirstDigit=0;
        if(strN[0]>'1')
            numFirstDigit=(int) Math.pow(10,length-1);
        else if(strN[0]=='1')
            numFirstDigit=Integer.parseInt(str.substring(1))+1;
        int numOtherDigits=(int) ((strN[0]-'0')*(length-1)*Math.pow(10, length-2));        
        int numRecursive=numberOf1(str.substring(1));   
        return numFirstDigit+numOtherDigits+numRecursive;

    } 

}

4.再考虑一种新思路。统计某个位置上 1出现的次数。如34，1在十位上出现的次数是10次
（10到19），1在个位上出现的次数是4次（1，11，21，31），因此34中1出现了14次。

对于整数n，将这个整数分为三部分：当前位数字cur，更高位数字high，更低位数字low，如：对于n=21034，当位数是十位时，cur=3，high=210，low=4。
我们从个位到最高位 依次计算每个位置出现1的次数：
在计算时，会出现三种情况
1）当前位的数字等于0时，例如n=21034，在百位上的数字cur=0，百位上是1的情况有：00100-00199，01100-01199，……，20100-20199。一共有21*100种情况，即high*100;
2）当前位的数字等于1时，例如n=21034，在千位上的数字cur=1，千位上是1的情况有：01000-01999，11000-11999，21000-21034。一共有2*1000+（34+1）种情况，即high*1000+(low+1)。
3）当前位的数字大于1时，例如n=21034，在十位上的数字cur=3，十位上是1的情况有：00010-00019，……，21010-21019。一共有(210+1)*10种情况，即(high+1)*10。

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count=0;
        for(int i=1;i<=n;i*=10){  //i代表位数
            int high=n/(i*10); //更高位数字
            int low=(n%i);  //更低位数字
            int cur=(n/i)%10;  //当前位数字
            if(cur==0){
                count+=high*i;
            }else if(cur==1){
                count+=high*i+(low+1);
            }else{
                count+=(high+1)*i;
            }
        }
        return count;
    }
}

综合来看，最后一种思路还是容易想到，也有大佬针对最后一种思路进行了优化，这里就不赘述了，毕竟初学者先消化思路4的初始写法就很OK了。