首页 > ACM题库 > LeetCode > LeetCode-Sqrt(x)[分治]
2014
11-18

LeetCode-Sqrt(x)[分治]

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

标签: Math Binary Search
分析

二分查找

代码

//LeetCode, Pow(x, n)
// 二分法,$x^n = x^{n/2} * x^{n/2} * x^{n\%2}$
// 时间复杂度O(logn),空间复杂度O(1)
class Solution {
public:
    double pow(double x, int n) {
        if (n < 0) return 1.0 / power(x, -n);
        else return power(x, n);
    }
private:
    double power(double x, int n) {
        if (n == 0) return 1;
        double v = power(x, n / 2);
        if (n % 2 == 0) return v * v;
        else return v * v * x;
    }
};

  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  3. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.