LeetCode算法题-Sum of Square Numbers(Java实现)

时间:2021-09-12 00:43:08

这是悦乐书的第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实现)的更多相关文章

  1. LeetCode算法题-Valid Perfect Square(Java实现-四种解法)

    这是悦乐书的第209次更新,第221篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第77题(顺位题号是367).给定正整数num,写一个函数,如果num是一个完美的正方形 ...

  2. LeetCode算法题-Sum of Left Leaves(Java实现)

    这是悦乐书的第217次更新,第230篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第85题(顺位题号是404).找到给定二叉树中所有左叶的总和.例如: 二叉树中有两个左叶 ...

  3. LeetCode算法题-Sum of Two Integers(Java实现)

    这是悦乐书的第210次更新,第222篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第78题(顺位题号是371).计算两个整数a和b的总和,但不允许使用运算符+和 - .例 ...

  4. LeetCode算法题-Reach a Number(Java实现)

    这是悦乐书的第310次更新,第331篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第179题(顺位题号是754).你站在无限数字线的0号位置.在目的地有个target.在 ...

  5. LeetCode算法题-Find Pivot Index(Java实现)

    这是悦乐书的第304次更新,第323篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第172题(顺位题号是724).给定一个整数nums数组,编写一个返回此数组的&quot ...

  6. LeetCode算法题-Binary Tree Tilt(Java实现)

    这是悦乐书的第263次更新,第276篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第130题(顺位题号是563).给定二叉树,返回整棵树的倾斜度.树节点的倾斜被定义为所有 ...

  7. LeetCode算法题-Array Partition I(Java实现)

    这是悦乐书的第262次更新,第275篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第129题(顺位题号是561).给定一个2n个整数的数组,你的任务是将这些整数分组为n对 ...

  8. LeetCode算法题-Max Consecutive Ones(Java实现)

    这是悦乐书的第242次更新,第255篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第109题(顺位题号是485).给定二进制数组,找到此数组中连续1的最大数量.例如: 输 ...

  9. LeetCode算法题-Subdomain Visit Count(Java实现)

    这是悦乐书的第320次更新,第341篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第189题(顺位题号是811).像"discuss.leetcode.com& ...

随机推荐

  1. leetcode:1-5题代码整理

    以下是这段时间抽时间刷的前5题,都是自己想的解法,或许不是最优解,只是整理下,方便日后优化提升 1. Two Sum: class Solution: # @return a tuple, (inde ...

  2. linux学习笔记——基础命令

    最近看了一些老男孩linux运维视频,挺不错的,特此记录一下 linux组成 gun组件 shell等 linux内核 其他软件 linux主要内核: linux kernel2.2 linux ke ...

  3. HOLOLENS如何调节屏幕亮度和音量?

    圆环左边的两个是亮度按键,右边的是两个音量按键,值得注意的是,无论是两个音量键还是亮度键,它们都被设置成了一凸一凹,凸的按键为音量/亮度+键,凹为-键,其工业设计可见一斑.

  4. dipole antenna simulation by HFSS

    工作频点为1GHz,新建工程,添加新设计,编辑添加下面的变量 建立天线模型,即两个金属圆柱.编辑完一个振子后,另一半可以用镜像命令产生参数如下设置 ,材料为PEC 两个圆柱间建立一个矩形片,连接两个圆 ...

  5. android中的一些问题

    1. Android dvm的进程和Linux的进程, 应用程序的进程是否为同一个概念 DVM指dalivk的虚拟机.每一个Android应用程序都在它自己的进程中运行,都拥有一个独立的Dalvik虚 ...

  6. &commat;Autowired 和 &commat;Resource

    转自:Spring中@Autowired注解.@Resource注解的区别 Spring不但支持自己定义的@Autowired注解,还支持几个由JSR-250规范定义的注解,它们分别是@Resourc ...

  7. &period;NetCore WebApi——Swagger简单配置

    在前后端分离的大环境下,API接口文档成为了前后端交流的一个重点.Swagger让开发人员摆脱了写接口文档的痛苦. 官方网址:https://swagger.io/ 在.Net Core WebApi ...

  8. Python中字符串二三事

    首先说两个运算符: " == " 运算符测试值的等价性,递归地比较所有内嵌对象 " is " 表达式测试对象的同一性,测试两者是否为同一对象(是否为同一地址) ...

  9. TLS 1&period;3 VS TLS 1&period;2,让你明白 TLS 1&period;3 的强大

    HTTPS 加密时代已经来临,近两年,Google.Baidu.Facebook 等互联网巨头,不谋而合地开始大力推行 HTTPS, 2018 年 7 月 25 日,Chrome 68 上线,所有 H ...

  10. jqGrid之treeGrid及行拖拽

    单纯的做个小记录 今天做功能用到了jqGrid里面的treeGrid,遇到几个问题,这里做下记录 treeGrid 树表格的应用在官网给出了很直白的例子: 1.http://blog.mn886.ne ...