google筆試題

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

2、，就貼出來(lái)，發(fā)表一下自己的解法。這道題還有另一半當(dāng)f(n)＝n是，最小的n是多少？本人還沒有好的方法，所以就不貼了。下面的程序是上半部java實(shí)現(xiàn)的?？梢酝瞥鱿铝羞f推公式:f(n)=(a1s:nsa1)af(s1)f(nsa)當(dāng)n9時(shí)L是n的位數(shù)a是n的第一位數(shù)字s是10的L－1次方nsa求的是a后面的數(shù).公式說(shuō)明：求0n由多少個(gè)數(shù)字1，分三部分，一是所有數(shù)中第一位有多少個(gè)1，對(duì)應(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二是對(duì)應(yīng)af(s1）如n是223應(yīng)該有2f(99)個(gè)1三是對(duì)應(yīng)f(nsa)如n是223應(yīng)該有f(23)個(gè)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在一個(gè)集合S中尋找最大的C使AB=C且ABC均在集合當(dāng)中解答(原創(chuàng))1，將集合S中的數(shù)排序X10i)備注，不考慮證整數(shù)溢出，盡可能優(yōu)化算法。這一題我一看就知道要考什么，很顯然的遞歸定義，但也是很顯然的，這里所謂的優(yōu)化是指不要重復(fù)計(jì)算。簡(jiǎn)單的說(shuō)，在計(jì)算T(n)的時(shí)候要用到T(n1)、T(n2)和T(n3)的結(jié)果，在計(jì)算T(n1)的時(shí)候

5、也要用到T(n2)和T(n3)的結(jié)果，所以在各項(xiàng)計(jì)算的時(shí)候必須把以前計(jì)算的結(jié)果記錄下來(lái)，去掉重復(fù)計(jì)算。這里用到的一點(diǎn)小技巧就是要新寫一個(gè)函數(shù)用來(lái)做這種事情，嗯，看看我寫的代碼吧！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