查看匯總：2015軟件水平考試程序員精選題匯總

　　在從1到n的正數中1出現的次數

　　題目：輸入一個整數n，求從1到n這n個整數的十進制表示中1出現的次數。

　　例如輸入12，從1到12這些整數中包含1 的數字有1，10，11和12，1一共出現了5次。

　　分析：這是一道廣為流傳的google面試題。用最直觀的方法求解并不是很難，但遺憾的是效率不是很高;而要得出一個效率較高的算法，需要比較強的分析能力，并不是件很容易的事情。當然，google的面試題中簡單的也沒有幾道。

　　首先我們來看最直觀的方法，分別求得1到n中每個整數中1出現的次數。而求一個整數的十進制表示中1出現的次數，就和本面試題系列的第22題很相像了。我們每次判斷整數的個位數字是不是1。如果這個數字大于10，除以10之后再判斷個位數字是不是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;

　　}

　　這個思路有一個非常明顯的缺點就是每個數字都要計算1在該數字中出現的次數，因此時間復雜度是O(n)。當輸入的n非常大的時候，需要大量的計算，運算效率很低。我們試著找出一些規律，來避免不必要的計算。

　　我們用一個稍微大一點的數字21345作為例子來分析。我們把從1到21345的所有數字分成兩段，即1-1235和1346-21345。

　　先來看1346-21345中1出現的次數。1的出現分為兩種情況：一種情況是1出現在最高位(萬位)。從1到21345的數字中，1出現在10000-19999這10000個數字的萬位中，一共出現了10000(104)次;另外一種情況是1出現在除了最高位之外的其他位中。例子中1346-21345，這20000個數字中后面四位中1出現的次數是2000次(2*103，其中2的第一位的數值，103是因為數字的后四位數字其中一位為1，其余的三位數字可以在0到9這10個數字任意選擇，由排列組合可以得出總次數是2*103)。

　　至于從1到1345的所有數字中1出現的次數，我們就可以用遞歸地求得了。這也是我們為什么要把1-21345分為1-1235和1346-21345兩段的原因。因為把21345的最高位去掉就得到1345，便于我們采用遞歸的思路。

　　分析到這里還有一種特殊情況需要注意：前面我們舉例子是最高位是一個比1大的數字，此時最高位1出現的次數104(對五位數而言)。但如果最高位是1呢?比如輸入12345，從10000到12345這些數字中，1在萬位出現的次數就不是104次，而是2346次了，也就是除去最高位數字之后剩下的數字再加上1。

　　基于前面的分析，我們可以寫出以下的代碼。在參考代碼中，為了編程方便，我把數字轉換成字符串了。

　　#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);

　　}

　　/////////////////////////////////////////////////////////////////////////////

　　相關推薦：

　　2015年軟考信息技術處理員考前知識點總結匯總

　　2015年軟件水平考試《程序員》提高練習題匯總

　　2015軟件水平考試《程序員》知識點總結匯總