problem
solution:二分法;
class Solution { public: bool isPerfectSquare(int num) { int left = 1, right = num;// long mid = 0; while(left<=right) { mid = left + 0.5*(right - left); long t = mid*mid; if(t < num) left = mid+1; else if (t > num) right = mid-1; else return true; } return false; } };
solution2:
纯数学解法,利用到了这样一条性质,完全平方数是一系列奇数之和;
1 = 1 4 = 1 + 3 9 = 1 + 3 + 5 16 = 1 + 3 + 5 + 7 25 = 1 + 3 + 5 + 7 + 9 .... 1+3+...+(2n-1) = (2n-1 + 1)n/2 = n*n
时间复杂度为O(sqrt(n))
class Solution { public: bool isPerfectSquare(int num) { int i = 1; while(num>0) { num -= i; i +=2; } return num==0; } };
其他两种方法都出现超时的问题。
参考
1. Leetcode_367. Valid Perfect Square;
2. GrandYang;
完