Leetcode——367. Valid Perfect Square

本文主要是介绍Leetcode——367. Valid Perfect Square，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

判断一个数是不是完全平方数

题目要求不能使用sqrt()

数学性质

1=1
4=1+3
9=1+3+5

所以第一种O(sqrt(N))的算法是这里写代码片

class Solution {
public:bool isPerfectSquare(int num) {int i=1;while(num>0){num=num-i;i=i+2;}return num==0;}
};

利用二叉搜索性质O(logN)

class Solution2 {
public:bool isPerfectSquare(int num) {int low=1,high=num;while(low<high){long mid=(low+high)/2;if(mid*mid==num) return true;else if(mid*mid>num){high=mid-1;//very important!!! Or it will not stop!}else{low=mid+1;//very important!!!}}return false;}
};

Newton迭代法

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

https://en.wikipedia.org/wiki/Integer_square_root#Using_only_integer_division

这篇关于Leetcode——367. Valid Perfect Square的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---