这样的面试题，你会吗？（有奖）

edshea

回复 108# hbmhalley
为什么说复杂度是n^1.6？

hbmhalley

回复 110# edshea


    设方阵为n*n
    每次将一个n*n变成三个(n/2)*(n/2)，即
    f(n) = 3*f(n/2)+1
    由主定理得 复杂度为O(n^log(2,3)) 约为O(n^1.6)

edshea

回复 111# hbmhalley
还请指教更高效的算法

hbmhalley

回复 112# edshea


    见22L
    这是目前我看到的所有正确算法中最快的一个 O(n)的
    3L也是O(n)的，不过是从f(n)=2*f(n/2)+log(n)得到的O(n+log(n))，会稍慢一点

    第二等是O(n*log(n))的，有逐行二分的，也有把22L改成二分的(87L)

    再就是O(n^1.6)的了

    再就是暴力找了 ..

edshea

回复 113# hbmhalley
22L的算法怎么证明正确性呢？

hbmhalley

回复 114# edshea


    对于一个左下角位置(x,y)，若Goal<(x,y)，那么对于所有t>y，有Goal<(x,t)；由于不存在(x,<y)的格子，所有第x行可以被删掉
                                       若Goal>(x,y)，那么对于所有t<x，有Goal>(t,y)；由于不存在(>x,y)的格子，所以第y列可以被删掉

edshea

回复 115# hbmhalley
受教了，不难理解，编码也简洁，很优雅！
多谢！

zhedahht

回复 22# crazyhadoop


    思路都是正确的，可惜没有代码

zhedahht

回复 33# 午夜凋零

谢谢参与本次活动。

第1题使用循环遍历的方法，结果正确，但效率有待提高。第2题的第一问的perl代码实现正确，第二问的思路正确，但在2的多少次方的细节上，有些小瑕疵。

zhedahht

回复 34# pozenfly


    谢谢关注这次活动。很好奇第2题的第2问怎么用DP来分析？

    另外，这是一本关于程序员面试的书。我们也不能要求每个来面试的应聘者，都是ACMer吧？