程序員面試題精選100題(25)-在從1到n的正數中1出現的次數[算法]

時間:2019-09-22 編輯:范文亭
題目:輸入一個整數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);
}

/////////////////////////////////////////////////////////////////////////////
// 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<unsigned int>(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;
}
本文已影響
相關文章
大亨pk10计划苹果版