Posted on 2006-09-16 15:35
chenger 閱讀(888)
評論(4) 編輯 收藏 引用 所屬分類:
Programming Stuff
上次寫了一篇關(guān)于google面試題的
文章。我給的算法跑得很慢，后面張沈鵬同學(xué)用python寫了一個
算法，速度很快（再次感覺python的性能不像想象中那么壞，當(dāng)然和算法有關(guān)），看了一下他的代碼，函數(shù)count(i)用來計(jì)算小于i的1的個數(shù)，和我寫的calc_ones算法基本相同，只不過count(i)用了遞歸，看上去更清楚一些。主要的速度差別在little(i)函數(shù)上，這個函數(shù)避免了很多迭代：
size_t little(size_t i)
{
??? size_t ones = calc_ones(i);
??? if(ones == i)
??????? cout << i << "\n";
??? if(i < ones)
??????? if((ones - i)/9 > 1)
??????????? return i - (ones - i)/8;
??? if(i > ones)
??????? return ones;
??? return i - 1;
}這是C++版本。主循環(huán)也要略微改變一下：
void solve()
{
??? size_t max = 10000000000;
??? for(size_t i = max;i > 0;i = little(i));
}可以看到，現(xiàn)在循環(huán)從大到小。little函數(shù)找到下一個可能滿足題目約束的i。在little函數(shù)中，首先計(jì)算小于i的1的個數(shù)ones，如果ones和i相等，就將i輸出（這就是題目要求干的事）。如果i小于ones，那么就要在小于i的自然數(shù)中找下一個可能滿足條件的數(shù)。因?yàn)樗阉鞯姆秶怀^10^10，所以一個數(shù)中至多含有9個1，按照這種極端情況，也必須將i減少(ones-i)/8才有可能滿足條件(這里之所以是8，因?yàn)橥瑫r(shí)i也減少了）。如果i大于ones，考慮一個小于i的數(shù)i'，可以考慮一下calc_ones(i')的取值，極端情況，[i',i)的范圍內(nèi)的整數(shù)沒有一個包含1，也就是說當(dāng)i減少到i'時(shí)1的個數(shù)沒有損失，那么calc_ones(i') = calc_ones(i)，如果i'>calc_ones(i)，則就有i'>calc_ones(i')，直到i'=calc_ones(i)，因此下一個需要查看的數(shù)就是calc_ones(i)。其實(shí)上面這一段討論可以用一個式子來概括：對i'<i,calc_ones(i)-9*(i-i') <= calc_ones(i') <= calc_ones(i)。這樣就能大大提高速度了。