码疯窝

LeetCode 每日一题 — Sqrt(x)

2015/01/20 10:56:59    分类: 日志连载    2人评论 次浏览

Implement int sqrt(int x).

Compute and return the square root of x.

算法分析: 这道题目就是道很数学的题目了. 因为题目返回值要求是int 型的, 相应就简单多了.
思路一, 等差数组穷举法: n^2 = 1 + 3 + 5 + … + (2n – 1), 利用穷举就能计算出n的值, 时间复杂度为 O(n), 在leetcode上面无法通过.
思路二, 2分法: 每次取中间值n^2与x比, 若小, 取取右边中间值再比, 若大, 取左边中间值比. (Python 用此解法)
思路三, 牛顿迭代法: 迭代公式: xi+1= (xi + n/xi) / 2
当然, 还有其它算法. 有兴趣找度娘.

Java:

public class Solution {
    public int sqrt(int x) {
        double pre = 0;
        double cur = 1;
        while(Math.abs(cur - pre) > 0.0001) {
            pre = cur;
            cur = x / (2 * pre) + pre / 2.0;  
        }
        return (int)cur;
    }
}

C++:

class Solution {
class Solution {
public:
    int sqrt(int x) {
        double pre = 0;
        double cur = 1;
        while (abs(cur - pre) > 0.0001) {
            pre = cur;
            cur = (pre + x / pre) / 2.0;
        }
        return (int)cur;
    }
};

Python:

class Solution:
    # @param x, an integer
    # @return an integer
    def sqrt(self, x):
        if (x <= 1):
            return x;
        n = x >> 1
        left = 0
        right = x
        while left < right - 1:
            s = n * n
            if (s < x):
                left = n
                n += (right - left) >> 1
            elif (s > x):
                right = n
                n -= (right - left) >> 1
            else:
                return n
        return n if n * n <= x else n - 1
继续查看有关 日志连载的文章

2个访客评论

  1. 久发网

    再次来访,希望每次都有新鲜感。

    qweqwe Reply