https://leetcode.com/problems/sum-of-square-numbers
https://discuss.leetcode.com/topic/94435/java-two-pointers-solution
Another method to check if is a perfect square, is by making use of Binary Search. The method remains same as that of a typical Binary Search to find a number. The only difference lies in that we need to find an integer, in the range , such that this number is the square root of . Or in other words, we need to find an integer, , in the range , such that x.
https://discuss.leetcode.com/topic/94430/java-solution
刚开始博主没仔细看题,没有看到必须要是两个平方数之和,博主以为任意一个就可以。所以写了个带优化的递归解法,楼主已经不是上来就无脑暴力破解的辣个青葱骚年了,直接带优化。可是居然对14返回false,难道14不等于1+4+9吗,结果仔细一看,必须要两个平方数之和。好吧,那么递归都省了,直接判断两次就行了。我们可以从c的平方根,注意即使c不是平方数,也会返回一个整型数。然后我们判断如果i*i等于c,说明c就是个平方数,只要再凑个0,就是两个平方数之和,返回true;如果不等于的话,那么算出差值c - i*i,如果这个差值也是平方数的话,返回true。遍历结束后返回false
Given a non-negative integer
c
, your task is to decide whether there're two integers a
and b
such that a2 + b2 = c.
Example 1:
Input: 5 Output: True Explanation: 1 * 1 + 2 * 2 = 5
Example 2:
Input: 3 Output: FalseX. Two Pointers
https://discuss.leetcode.com/topic/94435/java-two-pointers-solution
public boolean judgeSquareSum(int c) {
if (c < 0) {
return false;
}
int left = 0, right = (int)Math.sqrt(c);
while (left <= right) {
int cur = left * left + right * right;
if (cur < c) {
left++;
} else if (cur > c) {
right--;
} else {
return true;
}
}
return false;
}
X. Binary search
类似于二分查找。
从0 和sqrt(n)两端分别查找
https://leetcode.com/articles/sum-of-square-numbers/Another method to check if is a perfect square, is by making use of Binary Search. The method remains same as that of a typical Binary Search to find a number. The only difference lies in that we need to find an integer, in the range , such that this number is the square root of . Or in other words, we need to find an integer, , in the range , such that x.
public boolean judgeSquareSum(int c) { for (long a = 0; a * a <= c; a++) { int b = c - (int)(a * a); if (binary_search(0, b, b)) return true; } return false; } public boolean binary_search(long s, long e, int n) { if (s > e) return false; long mid = s + (e - s) / 2; if (mid * mid == n) return true; if (mid * mid > n) return binary_search(s, mid - 1, n); return binary_search(mid + 1, e, n); }X.
https://discuss.leetcode.com/topic/94430/java-solution
public static Boolean check (int c){
HashSet<Integer> hs = new HashSet<>();
for (int i=0; i<=Math.sqrt(c); i++) {
hs.add(i * i);
}
for (int i=0; i<=Math.sqrt(c); i++){
if (hs.contains(c - (i*i)))
return true;
}
return false;
}
https://discuss.leetcode.com/topic/94428/java-3-linerpublic static boolean judgeSquareSum(int c) {
for (int i=0;i<=Math.sqrt(c);i++)
if (Math.floor(Math.sqrt(c-i*i)) == Math.sqrt(c-i*i)) return true;
return false;
}
public boolean judgeSquareSum(int c) { for (long a = 0; a * a <= c; a++) { double b = Math.sqrt(c - a * a); if (b == (int) b) return true; } return false; }
Now, to determine, if the number is a perfect square or not, we can make use of the following theorem: "The square of positive integer can be represented as a sum of first odd positive integers." Or in mathematical terms:
.
To look at the proof of this statement, look at the L.H.S. of the above statement.
public boolean judgeSquareSum(int c) { for (long a = 0; a * a <= c; a++) { int b = c - (int)(a * a); int i = 1, sum = 0; while (sum < b) { sum += i; i += 2; } if (sum == b) return true; } return false; }
public boolean judgeSquareSum(int c) { for (long a = 0; a * a <= c; a++) { for (long b = 0; b * b <= c; b++) { if (a * a + b * b == c) return true; } } return false; }
public boolean judgeSquareSum(int c) { for (int i = 2; i * i <= c; i++) { int count = 0; if (c % i == 0) { while (c % i == 0) { count++; c /= i; } if (i % 4 == 3 && count % 2 != 0) return false; } } return c % 4 != 3; }http://www.cnblogs.com/grandyang/p/7190506.html
刚开始博主没仔细看题,没有看到必须要是两个平方数之和,博主以为任意一个就可以。所以写了个带优化的递归解法,楼主已经不是上来就无脑暴力破解的辣个青葱骚年了,直接带优化。可是居然对14返回false,难道14不等于1+4+9吗,结果仔细一看,必须要两个平方数之和。好吧,那么递归都省了,直接判断两次就行了。我们可以从c的平方根,注意即使c不是平方数,也会返回一个整型数。然后我们判断如果i*i等于c,说明c就是个平方数,只要再凑个0,就是两个平方数之和,返回true;如果不等于的话,那么算出差值c - i*i,如果这个差值也是平方数的话,返回true。遍历结束后返回false
for (int i = sqrt(c); i >= 0; --i) { if (i * i == c) return true; int d = c - i * i, t = sqrt(d); if (t * t == d) return true; } return false; }
bool judgeSquareSum(int c) { unordered_set<int> s; for (int i = 0; i <= sqrt(c); ++i) { s.insert(i * i); if (s.count(c - i * i)) return true; } return false; }