您當前位置：首頁 > php開源 > 綜合技術 > 編程之美1：那些關于1的個數的經典面試題

編程之美1：那些關于1的個數的經典面試題

來源：程序員人生發布時間：2015-04-28 08:39:46 閱讀次數：2991次

那些關于1的個數的經典面試題

好長時間沒有練算法了，筆試題1做，發現非常費勁，所以近日來找來《編程之美》1書來看看練練。為了鼓勵自己多練，樓樓可能會出個專欄甚么的，感興趣的同學我們可以1起抱團，樓樓也會保證每天都會更新。那今天呢，就是《編程之美》的第1題了，原題叫做“1”的數目，樓樓會把這道題還有相干的1些題都會記錄下來，下面要開始了哦，Are you ready?

題目1 給定1個10進制正整數N，寫下從1開始，到N的所有整數，然后數1下其中出現的所有“1”的個數

解法1 暴力窮舉

我相信如果是我們正在處于筆試或面試確當場，暴力窮舉肯定是我們的第1個想法。1個1個算，算出1中出現“1”的個數，再算出2中出現“1”的個數，順次類推，直到N中“1”的個數，然后相加得出最后的結論。我們看代碼：

#include <iostream>  

using namespace std;  
int getOneShowTimes(unsigned int n) ;
int getOneShowSumTimes(unsigned int N) ;

int main()  
{  
    unsigned int N = 123;
    cout << "1出現的次數為：" << getOneShowSumTimes(N) << endl;
    system("pause");
}  

int getOneShowSumTimes(unsigned int N) 
{
    unsigned int count = 0;
    for (unsigned int i = 0; i <= N; i++)
    {
        count += getOneShowTimes(i);
    }
    return count;
}

int getOneShowTimes(unsigned int n) 
{
    unsigned count = 0;
    while(0 != n) 
    {
        count += (n % 10) == 1 ? 1 : 0;
        n /= 10;
    }
    return count;
}

我們分析1下復雜度，外層循環要循環N次，內存循環要循環 $log_{10}{N} + 1$ 次，所以總的復雜度為 $Oleft(Nleft(log_{10}{N} + 1 ight) ight)$ ，可以看出這個復雜度是比較高的。

下面我們想一想，有無更簡單的辦法呢？比如對1個3位數123而言，“1”只能在個位出現，或10位出現或千位出現。如果是依照這個原理來統計的，那我們可以完全將外層循環下降到 $log_{10}{N} + 1$ 次。那我們來寫幾個例子來尋覓1下規律。

解法2 逐位統計法

如123，那末

個位出現1	10位出現1	百位出現1
1	10	100
11	11	101
21	12	102
31	13	103
41	14	104
51	15	…
61	16
71	17
81	18
91	19
101	110
111	…
121	119	123
總計13次	總計20次	總計24次
料想公式 $N/10+1$	料想公式 $(N/100+1)*10$	料想公式 $(N/1000)*100+N\%100+1$

但是在這里有我們有幾個特殊的情況需要特別斟酌，如相應的位數為0怎樣辦？比如51和50結果是完全不1樣的。還有相應的位數為1怎樣辦？12和22的結果也是不1樣的。我下面把結果羅列出來，大家也能夠試著推導1下。

分情況	個位出現1	10位出現1	百位出現1
bit = 0	$(N/10) * 1$	$(N/100) * 10$	$(N/1000) * 100$
bit = 1	$(N/10) * 1 + N \% 1 + 1$	$(N/100) * 10 + N \% 10 + 1$	$(N/1000) * 100 + N \% 100 + 1$
bit > 1	$(N/10 + 1) * 1$	$(N/100 + 1) * 10$	$(N/1000 + 1) * 100$

總結1下，假定每位對應的權值為quan，如個位quan = 1,10位quan = 10，那末總的公式為

bit=0	bit=1	bit>1
$(N/(10quan))quan$	$(N/(10quan))quan+N\%quan+1$	$(N/(10quan) + 1)quan$

下面看代碼：

package net.mindview.util;

public class MyThread {
  public static void main(String[] args) {
      int N = 123;
      System.out.println("總共出現" + getOneShowTimes(N) + "次");
  }

  public static int getOneShowTimes(int N) {
      int numPerBit; //存儲每位的數目
      int sumTimes = 0;  //存儲最后的結果
      int quan = 1;      //每位的權值，各位為1，10位為10，順次類推
      int tempN = N;
      if (0 == N) {
          return 0;
      }
      while(0 != tempN) {
          numPerBit = tempN % 10;     
          sumTimes += getOneShowTimesPerBit(N, numPerBit, quan);
          tempN /= 10;
          quan *= 10;
      }
      return sumTimes;
  }

  public static int getOneShowTimesPerBit(int N, int numPerBit, int quan) {
      if (0 == numPerBit) {
          return N / (quan * 10) * quan;
      } else if (1 == numPerBit) {
          return (N / (quan * 10)) * quan + N % quan + 1;
      } else {
          return (N / (quan * 10) + 1 ) * quan;
      }
  }
}

非常不好意思，這里的代碼是Java的，由于原來就寫好了，我就懶得再寫成c++的了，請見諒哈！復雜度為 $Oleft(log_{10}{N} + 1 ight)$ ，可以看出來效力是提升了很多的。下面我們來看第2個題。

題目2：給定1個10進制正整數N，寫下從1開始，到N的所有整數，然后數1下其中2進制中出現的所有“1”的個數

題目1是10進制，題目2是2進制。注意這里的區分。那我們一樣寫寫看，看能不能找出甚么規律

假定N=3，那末我們看每位出現“1”的次數之和都是相等的，都是2次。那末結果就是2 * 2=4總共4次。其次，假定N=7，我們又驚奇地發現，所有小于7的數中每位出現“1”的次數之和也是相等的，每位出現“1”的次數之和為4，那末結果就是3 * 4 = 12次。那我們可以料想，當N=15時，總數為4 * 8 = 32次。這是非常理想的情況，那當N = 13呢？很easy，N=13，我們就先算N = 7。還剩下6個數，視察1下我們可以發現，剩下的6個數中“1”出現的次數=最小的6個數“1”出現的次數+6。那末我們就把問題降下來了，本來是要求左側6個數中1出現的個數，轉變成了求右側6個數中1出現的個數。

本來要求的“1”出現的個數	簡化以后要求的“1”出現的個數
1000	0000
1001	0001
1010	0010
1011	0011
1100	0100
1101	0101

那末剩下的6個數，又可以重復前面的步驟，先求N=3。
總結1下，假定不大于N的最小的2的次方數為 $biggest2Pow$
log2(biggest2Pow)?biggest2Pow2+(N+1 生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈

------分隔線----------------------------

上一篇 基于數據分析，是否自動檔汽車比手動擋更耗油

下一篇 linux下mysql的root密碼忘記解決方法

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關注

欄目熱點

一些開發或使用軟件過程中的經驗（不斷更新）

移動支付和人臉識別的聯姻

Dijkstra 算法尋找最短路徑較簡易

UVa 12554 - A Special "Happy Birthday" Song!!!

android ListView簡單用法

人性多面性的終極教材――北漂18年（4）

【五個非常重要的移動Web內容適應設計理念】

用好LLDB調試，其樂無窮

日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

編程之美1：那些關于1的個數的經典面試題

那些關于1的個數的經典面試題

題目1 給定1個10進制正整數N，寫下從1開始，到N的所有整數，然后數1下其中出現的所有“1”的個數

題目2：給定1個10進制正整數N，寫下從1開始，到N的所有整數，然后數1下其中2進制中出現的所有“1”的個數