題目：求出1~13的整數(shù)中1出現(xiàn)的次數(shù),并算出100~1300的整數(shù)中1出現(xiàn)的次數(shù)？為此他特別數(shù)了一下1~13中包含1的數(shù)字有1、10、11、12、13因此共出現(xiàn)6次,但是對于后面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)（從1 到 n 中1出現(xiàn)的次數(shù)）。

思路：

方法一：

??直接一個數(shù)字一個數(shù)字的計算每個數(shù)字1出現(xiàn)的次數(shù)，并返回其和。

方法二：

個位

個位數(shù)上，1會每隔10出現(xiàn)一次，例如1、11、21等等，以10為一個階梯的話，每一個完整的階梯里面都有一個1，例如數(shù)字22，按照10為間隔來分三個階梯，在完整階梯0-9，10-19之中都有一個1，但是19之后有一個不完整的階梯，需要去判斷這個階梯中會不會出現(xiàn)1，易推斷知，如果最后這個露出來的部分小于1，則不可能出現(xiàn)1（這個歸納換做其它數(shù)字也成立）。

歸納出個位上1出現(xiàn)的個數(shù)為：

n/10 * 1+(n%10!=0 ? 1 : 0)

十位

十位數(shù)上出現(xiàn)1的情況應(yīng)該是10-19，依然沿用分析個位數(shù)時候的階梯理論，10-19這組數(shù)，每隔100出現(xiàn)一次，這次階梯是100，例如數(shù)字317，分析有階梯0-99，100-199，200-299三段完整階梯，每一段階梯里面都會出現(xiàn)10次1（從10-19），最后分析露出來的那段不完整的階梯。如果露出來的數(shù)大于19，那么直接算10個1就行了，因為10-19肯定會出現(xiàn)；如果小于10，那么肯定不會出現(xiàn)十位數(shù)的1；如果在10-19之間的，計算結(jié)果應(yīng)該是k - 10 + 1。例如分析300-317，17這個數(shù)字，1出現(xiàn)的個數(shù)應(yīng)該是17-10+1=8個。

那么現(xiàn)在可以歸納：十位上1出現(xiàn)的個數(shù)為：

• 設(shè)k = n % 100，即為不完整階梯段的數(shù)字
• 歸納式為：(n / 100) * 10 + (if(k > 19) 10 else if(k < 10) 0 else k - 10 + 1)

百位

在百位，100-199都會出現(xiàn)百位1，一共出現(xiàn)100次，階梯間隔為1000，100-199這組數(shù)，每隔1000就會出現(xiàn)一次。假設(shè)數(shù)為2139。跟上述思想一致，先算階梯數(shù) * 完整階梯中1在百位出現(xiàn)的個數(shù)，即n/1000 * 100得到前兩個階梯中1的個數(shù)，那么再算漏出來的部分139，沿用上述思想，不完整階梯數(shù)k199，得到100個百位1，100<=k<=199則得到k - 100 + 1個百位1。

那么歸納百位上出現(xiàn)1的個數(shù)：

• 設(shè)k = n % 1000
• 歸納式為：(n / 1000) * 100 + (if(k >199) 100 else if(k < 100) 0 else k - 100 + 1)

后面的依次類推....

再次回顧個位

把個位數(shù)上算1的個數(shù)的式子也納入歸納式中

• k = n % 10
• 個位數(shù)上1的個數(shù)為：n / 10 * 1 + (if(k > 1) 1 else if(k < 1) 0 else k - 1 + 1)

設(shè)i為計算1所在的位數(shù)，i=1表示計算個位數(shù)的1的個數(shù)，10表示計算十位數(shù)的1的個數(shù)等等。

• k = n % (i * 10)
• count(i) = (n / (i * 10)) * i + (if(k > i * 2 - 1) i else if(k < i) 0 else k - i + 1)

好了，這樣從10到10的n次方的歸納就完成了。

• sum1 = sum(count(i))，i = Math.pow(10, j), 0<=j<=log10(n)

源碼：GitHub源碼

方法一：

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int sum = 0;
        for(int i = 1;i <= n;i++){
            int temp = i;
            while(temp != 0){
                if(temp % 10 == 1) sum++;
                temp = temp / 10;
            }
        }
        return sum;
    }
}

方法二：

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        if(n <= 0) return 0;
        int count = 0;
        for(int i = 1;i <= n;i *= 10){
            int sum = i * 10;
            count += (n / sum) * i;
            if((n % sum) > (i * 2 - 1)) count += i;
            else if(n % sum < i) ;
            else count += n % sum - i + 1;
        }
        return count;
    }
}