C++博客 :: 首页 ::  :: 联系 ::  :: 管理

Google面试题之补充

Posted on 2006-09-16 15:35 chenger 阅读(861) 评论(4)  编辑 收藏 引用 所属分类: Programming Stuff
上次写了一篇关于google面试题的文章。我给的算法跑得很慢,后面张沈鹏同学用python写了一个算法,速度很快(再次感觉python的性能不像想象中那么坏,当然和算法有关),看了一下他的代码,函数count(i)用来计算小于i的1的个数,和我写的calc_ones算法基本相同,只不过count(i)用了递归,看上去更清楚一些。主要的速度差别在little(i)函数上,这个函数避免了很多迭代:

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++版本。主循环也要略微改变一下:

void
solve()
{

    size_t
max = 10000000000;
    for
(size_t i = max;i > 0;i = little(i));
}


可以看到,现在循环从大到小。little函数找到下一个可能满足题目约束的i。在little函数中,首先计算小于i的1的个数ones,如果ones和i相等,就将i输出(这就是题目要求干的事)。如果i小于ones,那么就要在小于i的自然数中找下一个可能满足条件的数。因为搜索的范围不超过10^10,所以一个数中至多含有9个1,按照这种极端情况,也必须将i减少(ones-i)/8才有可能满足条件(这里之所以是8,因为同时i也减少了)。如果i大于ones,考虑一个小于i的数i',可以考虑一下calc_ones(i')的取值,极端情况,[i',i)的范围内的整数没有一个包含1,也就是说当i减少到i'时1的个数没有损失,那么calc_ones(i') = calc_ones(i),如果i'>calc_ones(i),则就有i'>calc_ones(i'),直到i'=calc_ones(i),因此下一个需要查看的数就是calc_ones(i)。其实上面这一段讨论可以用一个式子来概括:对i'<i,calc_ones(i)-9*(i-i') <= calc_ones(i') <= calc_ones(i)。这样就能大大提高速度了。

Feedback

# re: Google面试题之补充  回复  更多评论   

2006-09-17 12:57 by 张沈鹏
sorry,我有个笔误
(count_i-i)/9
=>
(count_i-i)/8
至多含有9个1,count每次最多减9,而i-=1,所以差距至多-8,
这样会更快一点

# re: Google面试题之补充  回复  更多评论   

2006-09-17 13:19 by 张沈鹏
说实话,第一次我和你说的算法是指的
fastrun()
不过后来你叫我把算法给你看看,我觉得这种奇技淫巧不好意思拿出手
只好想了一个算法
不过,我还是觉得fastrun比run更有价值,我想这也是Google面试的本意吧:)

# re: Google面试题之补充  回复  更多评论   

2006-09-17 13:25 by chenger
后来我也觉得那个不正经。
我认为还是正经解决一下比较好。做到这个份上,也差不多了。

# re: Google面试题之补充  回复  更多评论   

2007-08-16 14:17 by 哈胖头
Show一下我的程序:

int count_ones(int n)
{
static int pow10[]={1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

int ones=0;

for(int m=n, b=0; m; m/=10, b++)
{
int d=m%10;
ones+=d*pow10[b]*b/10;
if(d>1) ones+=pow10[b];
if(d==1) ones+=n%pow10[b];
}

return ones;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理