2015年軟件水平考試精選題(13)

在從1到n的正數(shù)中1出現(xiàn)的次數(shù)
    題目：輸入一個整數(shù)n，求從1到n這n個整數(shù)的十進制表示中1出現(xiàn)的次數(shù)。
    例如輸入12，從1到12這些整數(shù)中包含1 的數(shù)字有1，10，11和12，1一共出現(xiàn)了5次。
    分析：這是一道廣為流傳的google面試題。用最直觀的方法求解并不是很難，但遺憾的是效率不是很高;而要得出一個效率較高的算法，需要比較強的分析能力，并不是件很容易的事情。當(dāng)然，google的面試題中簡單的也沒有幾道。
    首先我們來看最直觀的方法，分別求得1到n中每個整數(shù)中1出現(xiàn)的次數(shù)。而求一個整數(shù)的十進制表示中1出現(xiàn)的次數(shù)，就和本面試題系列的第22題很相像了。我們每次判斷整數(shù)的個位數(shù)字是不是1。如果這個數(shù)字大于10，除以10之后再判斷個位數(shù)字是不是1。基于這個思路，不難寫出如下的代碼：
    int NumberOf1(unsigned int n);
    /////////////////////////////////////////////////////////////////////////////
    // Find the number of 1 in the integers between 1 and n
    // Input: n - an integer
    // Output: the number of 1 in the integers between 1 and n
    /////////////////////////////////////////////////////////////////////////////
    int NumberOf1BeforeBetween1AndN_Solution1(unsigned int n)
    {
    int number = 0;
    // Find the number of 1 in each integer between 1 and n
    for(unsigned int i = 1; i <= n; ++ i)
    number += NumberOf1(i);
    return number;
    }
    /////////////////////////////////////////////////////////////////////////////
    // Find the number of 1 in an integer with radix 10
    // Input: n - an integer
    // Output: the number of 1 in n with radix
    /////////////////////////////////////////////////////////////////////////////
    int NumberOf1(unsigned int n)
    {
    int number = 0;
    while(n)
    {
    if(n % 10 == 1)
    number ++;
    n = n / 10;
    }
    return number;
    }
    這個思路有一個非常明顯的缺點就是每個數(shù)字都要計算1在該數(shù)字中出現(xiàn)的次數(shù)，因此時間復(fù)雜度是O(n)。當(dāng)輸入的n非常大的時候，需要大量的計算，運算效率很低。我們試著找出一些規(guī)律，來避免不必要的計算。
    我們用一個稍微大一點的數(shù)字21345作為例子來分析。我們把從1到21345的所有數(shù)字分成兩段，即1-1235和1346-21345。
    先來看1346-21345中1出現(xiàn)的次數(shù)。1的出現(xiàn)分為兩種情況：一種情況是1出現(xiàn)在位(萬位)。從1到21345的數(shù)字中，1出現(xiàn)在10000-19999這10000個數(shù)字的萬位中，一共出現(xiàn)了10000(104)次;另外一種情況是1出現(xiàn)在除了位之外的其他位中。例子中1346-21345，這20000個數(shù)字中后面四位中1出現(xiàn)的次數(shù)是2000次(2*103，其中2的第一位的數(shù)值，103是因為數(shù)字的后四位數(shù)字其中一位為1，其余的三位數(shù)字可以在0到9這10個數(shù)字任意選擇，由排列組合可以得出總次數(shù)是2*103)。
    至于從1到1345的所有數(shù)字中1出現(xiàn)的次數(shù)，我們就可以用遞歸地求得了。這也是我們?yōu)槭裁匆?-21345分為1-1235和1346-21345兩段的原因。因為把21345的位去掉就得到1345，便于我們采用遞歸的思路。
    分析到這里還有一種特殊情況需要注意：前面我們舉例子是位是一個比1大的數(shù)字，此時位1出現(xiàn)的次數(shù)104(對五位數(shù)而言)。但如果位是1呢?比如輸入12345，從10000到12345這些數(shù)字中，1在萬位出現(xiàn)的次數(shù)就不是104次，而是2346次了，也就是除去位數(shù)字之后剩下的數(shù)字再加上1。
    基于前面的分析，我們可以寫出以下的代碼。在參考代碼中，為了編程方便，我把數(shù)字轉(zhuǎn)換成字符串了。
    #include "string.h"
    #include "stdlib.h"
    int NumberOf1(const char* strN);
    int PowerBase10(unsigned int n);
    /////////////////////////////////////////////////////////////////////////////
    // Find the number of 1 in an integer with radix 10
    // Input: n - an integer
    // Output: the number of 1 in n with radix
    /////////////////////////////////////////////////////////////////////////////
    int NumberOf1BeforeBetween1AndN_Solution2(int n)
    {
    if(n <= 0)
    return 0;
    // convert the integer into a string
    char strN[50];
    sprintf(strN, "%d", n);
    return NumberOf1(strN);
    }
    /////////////////////////////////////////////////////////////////////////////
    // Find the number of 1 in an integer with radix 10
    // Input: strN - a string, which represents an integer
    // Output: the number of 1 in n with radix
    /////////////////////////////////////////////////////////////////////////////
    int NumberOf1(const char* strN)
    {
    if(!strN || *strN < '0' || *strN > '9' || *strN == '\0')
    return 0;
    int firstDigit = *strN - '0';
    unsigned int length = static_cast(strlen(strN));
    // the integer contains only one digit
    if(length == 1 && firstDigit == 0)
    return 0;
    if(length == 1 && firstDigit > 0)
    return 1;
    // suppose the integer is 21345
    // numFirstDigit is the number of 1 of 10000-19999 due to the first digit
    int numFirstDigit = 0;
    // numOtherDigits is the number of 1 01346-21345 due to all digits
    // except the first one
    int numOtherDigits = firstDigit * (length - 1) * PowerBase10(length - 2);
    // numRecursive is the number of 1 of integer 1345
    int numRecursive = NumberOf1(strN + 1);
    // if the first digit is greater than 1, suppose in integer 21345
    // number of 1 due to the first digit is 10^4. It's 10000-19999
    if(firstDigit > 1)
    numFirstDigit = PowerBase10(length - 1);
    // if the first digit equals to 1, suppose in integer 12345
    // number of 1 due to the first digit is 2346. It's 10000-12345
    else if(firstDigit == 1)
    numFirstDigit = atoi(strN + 1) + 1;
    return numFirstDigit + numOtherDigits + numRecursive;
    }
    /////////////////////////////////////////////////////////////////////////////
    // Calculate 10^n
    /////////////////////////////////////////////////////////////////////////////
    int PowerBase10(unsigned int n)
    {
    int result = 1;
    for(unsigned int i = 0; i < n; ++ i)
    result *= 10;
    return result;
    }