首页 > 代码库 > 367. Valid Perfect Square

367. Valid Perfect Square

2024-09-20 04:54:23   218人阅读

<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


联系
我们