題目介紹

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

解題思路

方法一:遞歸每個數字

思路

思路很簡單，寫個for循環，從1到n，在循環體中判斷這個數包含了多少個1

復雜度O(nlogn)，面試官不怎么開心呢。。 

方法二：找規律 

思路

設N = abcde,其中abcde分別為十進制中各位上的數字。

如果要計算百位上1出現的次數，它要受到3方面的影響：百位上的數字，百位以下（低位）的數字，百位以上（高位）的數字。

①如果百位上數字為0，百位上可能出現1的次數由更高位決定。比如：12013，則可以知道百位出現1的情況可能是：100 ~ 199，1100 ~ 1199,2100 ~ 2199，，…，11100 ~ 11199，一共1200個。可以看出是由更高位數字（12）決定，并且等于更高位數字（12）乘以 當前位數（100）。

② 如果百位上數字為1，百位上可能出現1的次數不僅受更高位影響還受低位影響。比如：12113，則可以知道百位受高位影響出現的情況是：100 ~ 199，1100 ~ 1199,2100 ~ 2199，，….，11100 ~ 11199，一共1200個。和上面情況一樣，并且等于更高位數字（12）乘以當前位數（100）。但同時它還受低位影響，百位出現1的情況是：12100~12113,一共114個，等于低位數字（113）+1。

③ 如果百位上數字大于1（2 ~ 9），則百位上出現1的情況僅由更高位決定，比如12213，則百位出現1的情況是：100 ~ 199,1100 ~ 1199，2100 ~ 2199，…，11100 ~ 11199,12100 ~ 12199,一共有1300個，并且等于更高位數字+1（12+1）乘以當前位數（100）。 

代碼

public int NumberOf1Between1AndN_Solution(int n) {

    //1的個數
    int count = 0;

    //當前位
    int i = 1;

    int current, after, before;

    while((n/i)!= 0){

        //高位數字
        current = (n/i)%10;
        //當前位數字
        before = n/(i*10);
        //低位數字
        after = n-(n/i)*i;

        //如果為0,出現1的次數由高位決定,數量等于高位數字 * 當前位數
        if (current == 0) {
            count += before * i;
        } else if(current == 1) {
            //如果為1,出現1的次數由高位和低位決定,高位*當前位+低位+1
            count += before * i + after + 1;
        } else{
            //如果大于1,出現1的次數由高位決定,（高位數字+1）* 當前位數
            count += (before + 1) * i;
        }
        //前移一位
        i = i*10;
    }
    return count;
}