面試題：4億里有多少個1（11算2個）

乍看這題真夠唬人的，群里看到這個題目后爭先恐后的說看法。最簡單的辦法不外乎就是遍歷每個數(shù)，然后toString() 看看里面有多少個1，最后全部加起來，這是我們得到標(biāo)準(zhǔn)答案的辦法。

群里算上我3個人寫了3個笨方法都跑出來了，3個笨方法，呵呵 有意思，笨方法也不一樣。 程序的實現(xiàn)真是變幻莫測。

var re = /1{1}/g;   
var max = 4 * 10000 * 10000;   
getTotal(f);   
getTotal(f1);   
getTotal(f2);   
function getTotal(func)   
{   
var total = 0;   
var begin = new Date();   
for(var i= 1 ;i <= max;i++)   
{   
total += func(i);   
}   
var end = new Date();   
var timespan = end - begin;   
alert("開始時間:"+begin + "\n 結(jié)束時間："+end +"\n總耗時:"+timespan + "毫秒 \n 總數(shù)："+total);   
}   
function f(num)   
{   
var t = 0;   
while(num)   
{   
if(num < 10){ if(num==1)t++;break;}   
var i = num % 10;   
if(i == 1) t++;   
num = parseInt(num / 10);   
}   
return t;   
}   
function f1(num)   
{   
var str = num.toString()   
var t = 0;   
for(var i=0;i<str.length;i++)   
{   
if(str.charAt(i)=="1") t++;   
}   
return t;   
}   
function f2(num)   
{   
var str = num.toString();   
var t = 0;   
while(re.exec(str))   
{   
t++;   
}   
return t;   
}  

當(dāng)數(shù)量少的時候第一種最快，顯然嘛，沒有處理字符串的步驟。按理說數(shù)量越大他越有優(yōu)勢。 可是實測結(jié)果，3個都差不多。但是用C#跑的話，第一個明顯越來越有優(yōu)勢。。。。

但是出題人肯定不是這樣想的，很多人都在說自己的技巧與看法，我也思考了很久。

先拿 100來說 ，100里面有多少個1？

10  
11  
12  
13  
14  
15   
16   
17   
18   
19   
01   
11   
21   
31   
41   
51   
61   
71   
81   
91 

故意這么排列是我們可以把 0~99看作是 1個長度為2的數(shù)組， 1位為1時，2位的可能性是10，2位為1時1位的可能性為10，所以 0~99應(yīng)該有20個1，而100有1個所以是21個。

999就應(yīng)該是 1*10*10 + 10*1*10 + 10*10*1 = 300

400呢？ 因為首位只能出現(xiàn)0~3 ，所以應(yīng)該是 1*10*10 + 4*1*10 + 4*1*10

4 0000 0000 應(yīng)該是 1 * (10^8) + 4*(10^7) * 8 = 420000000

通過本文的分析，你是不是了解了呢？？程序真的是太變化莫測了，同樣，一道題當(dāng)然有不同的解法。如果你有，我們可以一同分享。

【編輯推薦】

1. 三大鼎足IT名企面試題
2. 1.4.3 有趣的微軟面試題目
3. 深入剖析C/C++程序員應(yīng)聘常見面試題
4. 應(yīng)屆畢業(yè)生應(yīng)聘求職：25個刁鉆面試題解析