LeetCode Valid Perfect Square

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]]>

1 thought on “LeetCode Valid Perfect Square

  1. Pingback: LeetCode Sqrt(x) | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *