[转帖]google的一道JAVA面试题
<p><a href="http://www.hzguig.com/bbs"><font size="4">www.hzguig.com/bbs</font></a></p><p><font size="4">java代码: </font></p><p><font size="4"> Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n. </font></p><p><font size="4"> For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n? </font></p><p><font size="4"> 翻译过来大体是这样： <br/> 有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问下一个最大的f(n)=n的n是什么？</font></p> <p>int getCountOfNumber(int number){ <br/> int count=0; <br/> int length=("" + number).length(); <br/> <br/> for(int i=0;i<=length;i++){ <br/> int num=number%10; <br/> number=(number-num)/10; <br/> <br/> if(num*num==1) count++; <br/> } <br/> <br/> return count; <br/> } </p><p> 计算到：199981 用了203<br/> 不过只计算到上边的数值就没多大意思，看看这个：<br/> 这个是4000000000以内的结果！：<br/> f(0) = 0 <br/> f(1) = 1 <br/> f(199981) = 199981 <br/> f(199982) = 199982 <br/> f(199983) = 199983 <br/> f(199984) = 199984 <br/> f(199985) = 199985 <br/> f(199986) = 199986 <br/> f(199987) = 199987 <br/> f(199988) = 199988 <br/> f(199989) = 199989 <br/> f(199990) = 199990 <br/> f(200000) = 200000 <br/> f(200001) = 200001 <br/> f(1599981) = 1599981 <br/> f(1599982) = 1599982 <br/> f(1599983) = 1599983 <br/> f(1599984) = 1599984 <br/> f(1599985) = 1599985 <br/> f(1599986) = 1599986 <br/> f(1599987) = 1599987 <br/> f(1599988) = 1599988 <br/> f(1599989) = 1599989 <br/> f(1599990) = 1599990 <br/> f(2600000) = 2600000 <br/> f(2600001) = 2600001 <br/> f(13199998) = 13199998 <br/> f(35000000) = 35000000 <br/> f(35000001) = 35000001 <br/> f(35199981) = 35199981 <br/> f(35199982) = 35199982 <br/> f(35199983) = 35199983 <br/> f(35199984) = 35199984 <br/> f(35199985) = 35199985 <br/> f(35199986) = 35199986 <br/> f(35199987) = 35199987 <br/> f(35199988) = 35199988 <br/> f(35199989) = 35199989 <br/> f(35199990) = 35199990 <br/> f(35200000) = 35200000 <br/> f(35200001) = 35200001 <br/> f(117463825) = 117463825 <br/> f(500000000) = 500000000 <br/> f(500000001) = 500000001 <br/> f(500199981) = 500199981 <br/> f(500199982) = 500199982 <br/> f(500199983) = 500199983 <br/> f(500199984) = 500199984 <br/> f(500199985) = 500199985 <br/> f(500199986) = 500199986 <br/> f(500199987) = 500199987 <br/> f(500199988) = 500199988 <br/> f(500199989) = 500199989 <br/> f(500199990) = 500199990 <br/> f(500200000) = 500200000 <br/> f(500200001) = 500200001 <br/> f(501599981) = 501599981 <br/> f(501599982) = 501599982 <br/> f(501599983) = 501599983 <br/> f(501599984) = 501599984 <br/> f(501599985) = 501599985 <br/> f(501599986) = 501599986 <br/> f(501599987) = 501599987 <br/> f(501599988) = 501599988 <br/> f(501599989) = 501599989 <br/> f(501599990) = 501599990 <br/> f(502600000) = 502600000 <br/> f(502600001) = 502600001 <br/> f(513199998) = 513199998 <br/> f(535000000) = 535000000 <br/> f(535000001) = 535000001 <br/> f(535199981) = 535199981 <br/> f(535199982) = 535199982 <br/> f(535199983) = 535199983 <br/> f(535199984) = 535199984 <br/> f(535199985) = 535199985 <br/> f(535199986) = 535199986 <br/> f(535199987) = 535199987 <br/> f(535199988) = 535199988 <br/> f(535199989) = 535199989 <br/> f(535199990) = 535199990 <br/> f(535200000) = 535200000 <br/> f(535200001) = 535200001 <br/> f(1111111110) = 1111111110 </p><p> 有人用c写了一个，得出这些结果只用了几十毫秒！ <br/> 有更好思路的可以讨论讨论。</p> <p>楼主的代码，实在不敢恭维，纯粹是为了写代码而写代码。怪不得现在的代码的质量都越来越差了。</p><p>提示：写程序之前要用数学的方法来分析一遍。</p> <p>楼主试试下面的代码，GetCount就是f(x)的功能。不用像你那样一个位一个位的枚举了。</p><p>不过几十毫秒就把4000000000全跑遍了那也太夸张了吧？我这个几十毫秒只是到了</p><p>f(2600001) = 2600001 </p><p>你自己看看吧。<br/></p><p>#include <iostream.h></p><p>int GetCount(int n)<br/>{<br/> int nIncome = n; // 用来临时保存参数传入的n<br/> int nPower = 1; // 记录被10除过的次数x，nPower是10的x次方<br/> int nSum = 0; // 最后返回的1的个数</p><p> int nByte = 0; // 暂存每次取的某一位上的值<br/> int nCount = 0; // 每一个位能得到1的个数<br/> while (nIncome > 0)<br/> {<br/> nByte = nIncome % 10;<br/> nIncome = nIncome / 10;</p><p> if (nByte == 0)<br/> {<br/> nCount = nIncome * nPower;<br/> } <br/> else if (nByte == 1)// 当某一位是1时，那这个位的1的次数要考虑到尾数的个数<br/> {<br/> nCount = nIncome * nPower + (n % nPower + 1);<br/> } <br/> else<br/> {<br/> nCount = (nIncome + 1) * nPower;<br/> }</p><p> nSum += nCount;<br/> nPower *= 10;<br/> }</p><p> return nSum;<br/>}</p><p>int main(int argc, char* argv[])<br/>{<br/> int nCount = 0;<br/> for (int i = 0; i < 1111111110; i ++)<br/> {<br/> nCount = GetCount(i);<br/> if (nCount == i)<br/> cout << "f(" << i << ") = " << nCount << endl;<br/> }<br/> return 0;<br/>}</p> <p>论坛的排版风格……实在……</p>
页:
[1]