首页 > 代码库 > 367. Valid Perfect Square
367. Valid Perfect Square
<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 14.0px "Helvetica Neue"; color: #323333 }
p.p2 { margin: 0.0px 0.0px 0.0px 0.0px; font: 13.0px Menlo; color: #323333; background-color: #f5f5f5 }
p.p3 { margin: 0.0px 0.0px 0.0px 0.0px; font: 14.0px "Helvetica Neue"; color: #323333; min-height: 16.0px }
span.s1 { }
span.s2 { font: 13.0px Menlo; color: #c7254e; background-color: #f9f2f4 }</style>
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
Solution 1: use BST,O(logn)
1 class Solution { 2 public: 3 bool isPerfectSquare(int num) { 4 if (num==1) return true; 5 int begin=0,end=num; 6 while (begin<end-1){ 7 long long mid=(begin+end)/2; 8 if (mid*mid==num) return true; 9 if (mid*mid<num) begin=mid; 10 if (mid*mid>num) end=mid; 11 } 12 return false; 13 } 14 };
Solution 2: Newton‘s method, http://blog.csdn.net/wangxiaojun911/article/details/18203333
1 class Solution { 2 public: 3 bool isPerfectSquare(int num) { 4 long long x=num; 5 while(x*x>num) x=(x+num/x)/2; 6 return x*x==num; 7 } 8 };
Soulution 3: q_math.c special method, O(1)
<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 14.0px Arial } span.s1 { }</style>367. Valid Perfect Square
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。