Lexi's Leetcode solutions

[leetcode] sqrt(int) | 求一个正整数的平方根

Posted on: October 6, 2013

这题真是做了挺久,尼玛还是二分法不熟悉。。怎么终止还是想了很久。

二分法永远是(p, mid – 1)和(mid + 1, q), 不要想什么(p, mid)之类的,那样范围永远没法缩小,最后肯定死循环。

二分的模板终止条件永远是p > q,不要去想p == q + 1, p == q这些,这些都可以经过下一次recurse再分解成p > q的形式。

最后p > q说明没找到,比如foo(5, 4),即那么x应该是在4,5之间,这个时候p的值是5,q的值是4,说明小的那个是q,大的那个是p。所以二分法找x应该在的index那题返回p(返回较大的),这题应该返回q(返回较小的)。别去考虑p==q之类的的情况,那种再走一遍就会又形成p > q。若是找到了,更会在mid==x这个catch里直接接住,不用在终止条件处考虑。

还有一个要注意的地方:代码中间有mid * mid这种式子,这个就很可能overflow,所以要在出现这个之前接住overflow的情况。因为整数的乘法可能导致溢出,而溢出的监测和整数加法直接判断是否小于0是不同的(整数加法溢出时和会<0因为第一位bit被从0顶到1了),因为整数的乘法有可能多次溢出,当奇书次溢出时是负数,当偶数次溢出时时整数。网上看的巧妙的解决办法是干脆不要乘,而是用x/mid和mid比较。

public int sqrt(int x) {
    return sqrt(x, 1, x);
}
private int sqrt(int x, int p, int q) {
    if (p > q)
        return q;
    int mid = (p + q) / 2;
    if (x / mid == mid)
        return mid;
    else if (x / mid < mid )
        return sqrt(x, p, mid - 1);
    else
        return sqrt(x, mid + 1, q);
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

Blog Stats

  • 217,337 hits
October 2013
M T W T F S S
« Sep   Nov »
 123456
78910111213
14151617181920
21222324252627
28293031  
Advertisements
%d bloggers like this: