LeetCode算法题-Sum of Square Numbers(Java实现)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode算法题-Sum of Square Numbers(Java实现),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2375字,纯文字阅读大概需要4分钟。
内容图文
![LeetCode算法题-Sum of Square Numbers(Java实现)](/upload/InfoBanner/zyjiaocheng/837/61284c4e396c4fad950f64bbac2374a8.jpg)
这是悦乐书的第276次更新,第292篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第144题(顺位题号是633)。给定一个非负整数c,判断是否存在两个整数a和b,使得a的平方与b的平方之和等于c。例如:
输入:5
输出:true
说明:1 x 1 + 2 x 2 = 5
输入:3
输出:false
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
暴力解法,直接使用两层for循环,分别从0开始,上限为c的平方根,如果存在两数平方和等于c,就返回true,否则返回false。
此解法可能会超时,不建议使用。
public boolean judgeSquareSum(int c) {
int num = (int)Math.sqrt(c);
for (int a=0; a <= num; a++) {
for (int b=0; b<= num; b++) {
if (a*a + b*b == c) {
return true;
}
}
}
return false;
}
03 第二种解法
使用HashSet。如果在c的平方根范围内,存在两数平方和等于c,那么先将单个数的平方值a添加进set中,然后再去判断set中是否存在c减去a的另一个值b,如果存在就返回true。
public boolean judgeSquareSum(int c) {
HashSet<Integer> set = new HashSet<>();
int num = (int)Math.sqrt(c);
for (int i=num; i >= 0; i--) {
set.add(i*i);
if (set.contains(c-i*i)) {
return true;
}
}
return false;
}
04 第三种解法
我们也可以不使用HashSet。依旧是先确定取值范围,上限为c的平方根取整。在0到c的平方根范围内,如果当前一个数的平方根正好等于c,直接返回true,因为另外一个数可能是0;如果不等于,就用c减去当前此数的平方根并赋值给a,再对得到的差开方并赋值给b,如果b的平方等于a,直接返回true,说明存在两数之和等于c。
public boolean judgeSquareSum(int c) {
int num = (int)Math.sqrt(c);
for (int i=num; i >= 0; i--) {
if (i*i == c) {
return true;
}
int a = c - i*i;
int b = (int)Math.sqrt(a);
if (b*b == a) {
return true;
}
}
return false;
}
05 第四种解法
使用双指针。首指针a从0开始,尾指针b从c的平方根开始,如果a的平方加上b的平方的值大于c,那么尾指针b就减1;如果小于c,那么首指针a就加1;如果等于c,直接返回true。
public boolean judgeSquareSum(int c) {
int num = (int)Math.sqrt(c);
int a = 0;
int b = num;
while (a <= b) {
if (a*a + b*b > c) {
b--;
} else if (a*a + b*b < c) {
a++;
} else {
return true;
}
}
return false;
}
06 小结
此题本质上是一道数学题,先需要确定取值范围,然后在该范围内找到合适的两个数,使其平方和等于另外一个数,你可以使用二分查找法、双指针或者其他算法来实现。
算法专题目前已日更超过四个月,算法题文章144+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!
内容总结
以上是互联网集市为您收集整理的LeetCode算法题-Sum of Square Numbers(Java实现)全部内容,希望文章能够帮你解决LeetCode算法题-Sum of Square Numbers(Java实现)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。