題目介紹

求出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次,但是對(duì)于后面問(wèn)題他就沒(méi)轍了。ACMer希望你們幫幫他,并把問(wèn)題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)（從1 到 n 中1出現(xiàn)的次數(shù)）。

解題思路

方法一:遞歸每個(gè)數(shù)字

思路

思路很簡(jiǎn)單，寫(xiě)個(gè)for循環(huán)，從1到n，在循環(huán)體中判斷這個(gè)數(shù)包含了多少個(gè)1

復(fù)雜度O(nlogn)，面試官不怎么開(kāi)心呢。。 

方法二：找規(guī)律 

思路

設(shè)N = abcde,其中abcde分別為十進(jìn)制中各位上的數(shù)字。

如果要計(jì)算百位上1出現(xiàn)的次數(shù)，它要受到3方面的影響：百位上的數(shù)字，百位以下（低位）的數(shù)字，百位以上（高位）的數(shù)字。

①如果百位上數(shù)字為0，百位上可能出現(xiàn)1的次數(shù)由更高位決定。比如：12013，則可以知道百位出現(xiàn)1的情況可能是：100 ~ 199，1100 ~ 1199,2100 ~ 2199，，…，11100 ~ 11199，一共1200個(gè)?？梢钥闯鍪怯筛呶粩?shù)字（12）決定，并且等于更高位數(shù)字（12）乘以 當(dāng)前位數(shù)（100）。

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

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

代碼

public int NumberOf1Between1AndN_Solution(int n) {

    //1的個(gè)數(shù)
    int count = 0;

    //當(dāng)前位
    int i = 1;

    int current, after, before;

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

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

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