27、整數中1出現的次數（從1到n整數中1出現的次數）

題目

• 求出1—13的整數中1出現的次數,并算出100-1300的整數中1出現的次數？為此他特别數了一下1-13中包含1的數字有1、10、11、12、13是以共出現6次,但是對于後面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數（從1 到 n 中1出現的次數）。

思路

• 正常思路：每個數字都考慮一下，判斷每個數自的含有幾個1
• 最優思路：從數字規律着手，明顯提高時間效率的解法

代碼

• 正常思路

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int nums=0;
        for(int i=1;i<=n;i++){
            nums+= Find(i);
        }
        return nums;
    }
    public int Find(int n){
        int nums = 0;
        while(n>0){
            if(n%10==1)
                nums++;
            //改變資料的位數，減少一個位數
            n = n/10;
        }
        return nums;
    }
}
           

• 最優思路

int NumberOf1Between1AndN_Solution(int n)
    {
        int cnt = 0;
        int a=0,b=0;
        for(long long m=1;m<=n;m*=10){
            a = n/m;
            b = n%m;
            cnt+=(a+8)/10*m + (a%10==1)*(b+1);
        }
        return cnt;
    }
           

注解：參考一位牛友提到的leetcode的連結網址（包括求1~n的所有整數中2,3,4,5,6,7,8,9出現的所有次數）

通過使用一個 位置乘子m 周遊數字的位置, m 分别為1,10,100,1000…etc.（m<=n）

對于每個位置來說，把10進制數分成兩個部分，比如說 當m=100的時候， 把十進制數 n=3141592 分成 a=31415 和 b=92 ，以此來分析百位數為1時所有數的個數和。m=100時，百位數的字首為3141，當百位數大于1時，為3142100，因為當百位數大于1時，字首可以為0，即百位數可以從100到199，共100個數；當百位數不大于1時，為3141100；如何判斷百位數是否大于1？假設百位數為x，若（x+8）/10等于1，則大于1，若（x+8）/10等于0，則小于1。是以字首可用（n/m + 8）/10 m來計算(若計算2的個數，可以改為（n/m + 7）/10m,若計算3的個數，改為（n/m + 6）/10*m，…以此類推)。

再例如m=1000時，n分為a=3141和 b=592；千位數的字首為314，千位數不大于1，故字首計算為3141000；因為千位數為1，再加b+1(0到592)。即千位數為1的所有書的個數和為3141000+592+1；公式（n/m + 8）/10*m + b +1。

注意：隻有n的第m位為1時需要計算字尾，字尾計算為 （n/m%10==1）*(b+1)，

即（n/m%101）判斷第m位是否為1，若為1，則加上（b+1），若不為1，則隻計算字首。（若計算2的個數，可以改為（n/m%102）(b+1)，若計算3的個數，可以改為（n/m%10==3）(b+1)…以此類推）