69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

---

本题要对一个数开平方根。相当于LeetCode Valid Perfect Square的逆过程，很多方法都可以通用。 解法1。直接借用LeetCode Valid Perfect Square提到的牛顿法开方，代码如下：

class Solution {
public:
    int mySqrt(int x)
    {
        long long y = x;
        while (y * y > x) {
            y = (y + x / y) / 2;
        }
        return y;
    }
};

本代码提交AC，用时6MS。

解法2。二分搜索，由于sqrt(x)不可能超过x/2+1（查看两个函数图像），所以可以在[0,x/2+1]范围内二分搜索，因为是向下取整，所以返回的是r，代码如下：

class Solution {
public:
    int mySqrt(int x)
    {
        long long l = 0, r = x / 2 + 1;
        while (l <= r) {
            long long mid = (l + r) / 2;
            long long prod = mid * mid;
            if (prod == x)
                return mid;
            if (prod < x)
                l = mid + 1;
            else
                r = mid – 1;
        }
        return r;
    }
};

本代码提交AC，用时6MS。

三刷。暴力枚举：

class Solution {
public:
	int mySqrt(int x) {
		long long xx = x;
		if (x == 1)return 1;
		long long i = 1;
		for (; i < xx; ++i) {
			if (i*i > xx)break;
		}
		return i - 1;
	}
};

本代码提交AC，用时16MS，还是用前两个方法吧。

LeetCode Valid Perfect Square Given a positive integer num, write a function which returns True if num is a perfect square else False. Note: Do not use any built-in library function such as sqrt. Example 1:

Input: 16
Returns: True

Example 2:

Input: 14
Returns: False

---

本题要判断一个数是否是完全平方数。有很多种解法，现列举如下： 解法1。牛顿法。牛顿法本是用来求解函数f(x)=0的根的，可以用来开方。$$f(x)=x^2-num$$等于0的正根就是num的根号。下面就是牛顿法求解f(x)=0的根的更新公式，$$x_{n+1}$$比$$x_n$$更接近f(x)=0的真实根。初始的时候可以随便代一个$$x_0$$到公式中。 对于函数$$f(x)=x^2-num$$，$$f'(x)=2x$$，所以牛顿递推式为$$!x_{n+1}=x_n-\frac{x_n^2-num}{2x_n}=(x_n+num/x_n)/2$$ 所以我们可以初始代入$$x_n=num$$，然后不断用牛顿法，直到x*x<=num时，如果x*x==num，则num为完全平方数，否则不是。 关于牛顿法用于开放的原理介绍，果壳网上有个人介绍得很详细。 代码如下： [cpp] class Solution { public: bool isPerfectSquare(int num) { long long x = num; while (x*x > num) { x = (x + num / x) / 2; } return x*x == num; } }; [/cpp] 本代码提交AC，用时0MS。 解法2。对于num，如果$$x=\frac{num}{2}$$的平方依然大于num，则$$x=\frac{x}{2}$$，如果x的平方依然大于num，则继续对x除以2，不断除，直到x平方小于等于num时，遍历[x,2*x]之间的数，看看x*x==num是否成立，如果成立，说明num是完全平方数，否则不是。这种解法在高级算法里好像讲过。完整代码如下： [cpp] class Solution { public: bool isPerfectSquare(int num) { if (num == 1)return true; long long x = num >> 1; while (x*x > num)x >>= 1; for (int y = x; y <= (x << 1); ++y) { if (y*y == num)return true; } return false; } }; [/cpp] 本代码提交AC，用时3MS。 解法3。观测下面的等式发现完全平方数都是由连续奇数相加而来，所以我们也可以把连续奇数加起来，直到超过num时，看看和与num是否相等。 1 = 1 4 = 1 + 3 9 = 1 + 3 + 5 16 = 1 + 3 + 5 + 7 25 = 1 + 3 + 5 + 7 + 9 36 = 1 + 3 + 5 + 7 + 9 + 11 …. 1+3+…+(2n-1) = (2n-1 + 1)n/2 = n*n 代码如下： [cpp] class Solution { public: bool isPerfectSquare(int num) { long long sum = 1; for (int i = 3; sum < num; i += 2) sum += i; return sum == num; } }; [/cpp] 本代码提交AC，用时3MS。 解法4。二分搜索。l=0,r=num，mid=(l+r)/2，根据mid*mid和num的大小关系一步步缩小范围。复杂度为O(lgn)，完整代码如下： [cpp] class Solution { public: bool isPerfectSquare(int num) { long long l = 0, r = num; while (l <= r) { long long mid = (l + r) / 2; long long prod = mid*mid; if (prod == num)return true; if (prod < num)l = mid + 1; else r = mid – 1; } return l*l == num; } }; [/cpp] 本代码提交AC，用时0MS。 注意这个题的代码中，为了防止int越界，都需要用long long。 参考： http://bookshadow.com/weblog/2016/06/26/leetcode-valid-perfect-square/ http://www.cnblogs.com/grandyang/p/5619296.html]]>