google算法题，看谁的速度快，先来个抛砖引玉。

runforu

f(n)=x表示从1到n出现1的个数为x。例如f(1)=1, f(13)=6,f(19)=20.求10，0000，0000以内所有满足f(n)=n的数。我的算法大概6.65秒。而且是线性的。
int BuildAdv( int count )
{
    int prev = 0;
    int cur = 0;
    int delt = 0;
    int rt = 0;
    char number[13]= "000000000000";

    for (int i = 1; i < count; i++ )
    {
        for (int j = 11; j >= 0; j-- )
        {
            if ( number[j] == '9' )
            {
                number[j] = '0';
            }
            else
            {
                if ( number[j] == '0' )
                {
                    delt++;
                }
                if ( number[j] == '1' )
                {
                    delt--;
                }
                number[j] += 1;
                break;
            }
        }
        cur = prev + delt;
        prev = cur;
        if ( i == cur )
        {
            printf("result:%d\n", i );
            rt = i;
        }
    }
    return rt;
}

int main( int argc, char* argv[] )
{
    int number = 1000000000;
    DWORD d2 = GetTickCount();
    int y = BuildAdv(number);
    DWORD d3 = GetTickCount();
    printf("BuildAdv use:%d\n", d3-d2);
    return 0;
}

[ 本帖最后由 runforu 于 2008-8-6 10:48 编辑 ]

runforu

怎么没人回复啊，自己顶吧

lipingtababa

没有注释的代码,很少人回愿意读的

converse

LZ自己看吧:

http://bbs.chinaunix.net/viewthread.php?tid=726091

tyz

我以前参加一个公司面试的时候（当然没有谷哥怎么牛了，是一家小公司），当时做的就是这道题，当时要求算出
1-1234567890，而且必须秒出，
我刚开始用的思路就是你那种，其实这种思路处理大数的时候慢的要死，实在不是一个好的方法。
正常较快的做法是动态规划做，还有一种神奇的做法（当然这必须要求有一定的数学基础了）见CU内的贴，搜下就有了
还有，给代码注释是个好习惯

lukeden

在《编程之美》上有这个题，并给出了几种解法。你可以去看看