經典的一道數1的面試題，詳細推論以及證明在其他很多博客上都有，講的都很好 看了下所有的PAT考試，裡面涉及到的算法和數據結構還是比較集中的。 因為PAT測試面向企業，所以還是比較喜歡出經典面試題，而在面試中要考察綜合性的編程能力的話，鏈表和樹相關操作 都是常考的。 [cpp] #include <iostream> int Count(int n) { int ans = 0; int base = 1; //count "1" in every digit, then sum while (n/base != 0) { int right = n%base;//low digit int left = n/(base*10);//high digit int now = (n/base)%10;//current digit if (now == 0)//current digit 0, then only determined by high digit ans += left*base; else if(now == 1)//current digit 1, then determined by both high and low digit ans += left*base+right+1; else//current digit > 1 ans += (left+1)*base; base *= 10; } return ans; } int main() { int n; www.2cto.com while(scanf("%d",&n)!=EOF) { int ans = Count(n); printf("%d\n", ans); } return 0; }
