google筆試題

1、Google筆試題整理（超全?。└讲糠执鸢腹P試題[此帖已被設(shè)為好帖]Google筆試題整理（超全！）附部分答案，希望能幫到有需要的人！寫出這樣一個函數(shù)輸入一個n輸出從1到這個數(shù)字之間的出現(xiàn)的1的個數(shù)比如f(13)等于6f(9)等于1網(wǎng)上有很多這道題的解法，大多采用窮舉法。這把這個算法題變成了程序設(shè)計，這道題，我認(rèn)為是總結(jié)一個遞推公式，然后用遞推法實現(xiàn)，比較好。后來在網(wǎng)上考證了一下，這道題本來也是讓總結(jié)一個數(shù)學(xué)函數(shù)即可，無需編程。既然寫了

2、，就貼出來，發(fā)表一下自己的解法。這道題還有另一半當(dāng)f(n)＝n是，最小的n是多少？本人還沒有好的方法，所以就不貼了。下面的程序是上半部java實現(xiàn)的?？梢酝瞥鱿铝羞f推公式:f(n)=(a1s:nsa1)af(s1)f(nsa)當(dāng)n9時L是n的位數(shù)a是n的第一位數(shù)字s是10的L－1次方nsa求的是a后面的數(shù).公式說明：求0n由多少個數(shù)字1，分三部分，一是所有數(shù)中第一位有多少個1，對應(yīng)(a1s:nsa1)當(dāng)a大于1是應(yīng)該有a的L1次，a小于

3、1是有nsa1。如n是223所有數(shù)中第一位有1是100n是123所有數(shù)中第一位是1的有24二是對應(yīng)af(s1）如n是223應(yīng)該有2f(99)個1三是對應(yīng)f(nsa)如n是223應(yīng)該有f(23)個1。longf(longn)if(n01:0intL=(int)(Math.log10(n)1)求n的位數(shù)llongs=(long)Math.pow(10L1)求10的l－1次方，方便求后面n的第一位數(shù)字，及其后面的數(shù)。longa=(long)(

4、ns)求n的第一位數(shù)字return(a1s:nsa1)af(s1)f(nsa)google筆試題：AB=C在一個集合S中尋找最大的C使AB=C且ABC均在集合當(dāng)中解答(原創(chuàng))1，將集合S中的數(shù)排序X10i)備注，不考慮證整數(shù)溢出，盡可能優(yōu)化算法。這一題我一看就知道要考什么，很顯然的遞歸定義，但也是很顯然的，這里所謂的優(yōu)化是指不要重復(fù)計算。簡單的說，在計算T(n)的時候要用到T(n1)、T(n2)和T(n3)的結(jié)果，在計算T(n1)的時候

5、也要用到T(n2)和T(n3)的結(jié)果，所以在各項計算的時候必須把以前計算的結(jié)果記錄下來，去掉重復(fù)計算。這里用到的一點小技巧就是要新寫一個函數(shù)用來做這種事情，嗯，看看我寫的代碼吧！GetthevalueofT(n1)retrievetheresultofT(n2)T(n3).@param[in]nTheninT(n).@param[out]ValueofT(n2).@param[out]rightValueofT(n3).@returnV

6、alueofT(n1).intfind_trib(intnintright=1return2elseinttemp=find_trib(n1righttemp)returnrighttempFindvalueofT(n).@param[in]TheninT(n).@returnValueofT(n).@noteT(n)=T(n1)T(n2)T(n3)(n2)T(0)=T(1)=1T(2)=2.inttribonaci(intn)if(n