这是悦乐书的第 209 次更新, 第 221 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 77 题(顺位题号是 367). 给定正整数 num, 写一个函数, 如果 num 是一个完美的正方形, 则返回 True, 否则返回 False. 例如:
输入: 16
输出: true
输入: 14
输出: false
注意: 不要使用任何内置库函数, 例如 sqrt.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
暴力解法, 定义一个 long 类型的变量, for 循环判断其平方是否小于 num, 但是不要写循环体, 这样省时, 最后直接判断其平方是否等于 num.
- public boolean isPerfectSquare(int num) {
- if (num <= 1) {
- return num == 1;
- }
- long i = 1;
- for( ; i*i <num; i++);
- return i*i == num;
- }
03 第二种解法
使用二分查找, 起点为 1, 终点为 num, 取两数中间值, 然后判断平方是否等于 num, 如果大了, 就把终点指向当前中间值减 1; 如果小了, 就把起点指向当前中间值加 1.
此解法中, 为了防范溢出的风险, 使用了 long 类型的变量.
- public boolean isPerfectSquare2(int num) {
- if (num <= 1) {
- return num == 1;
- }
- long start = 1;
- long end = num;
- while (start <= end) {
- long mid = (start+end)/2;
- if (mid*mid == num) {
- return true;
- }
- if (mid*mid < num) {
- start = mid + 1;
- }
- if (mid*mid> num) {
- end = mid -1;
- }
- }
- return false;
- }
04 第三种解法
使用牛顿迭代法, 核心代码是:
- x*x = num
- x = num/x
- 2*x = x + num/x
- x = (x + num/x)/2
对于 x 的初始值, 我们取 num 的值, 循环的判断条件是 x 的平方大于 num, 最后判断 x 的平方是否等于 num.
- public boolean isPerfectSquare3(int num) {
- long x = num;
- while (x*x> num) {
- x = (x + num / x) / 2;
- }
- return x*x == num;
- }
05 第四种解法
此题其实就是判断 num 能否被开平方且结果是整数. 如 1,4,9,16,25,36 等, 这些数字都是可以,. 同样, 我们可以观察一组奇数之和:
- 1 = 1
- 1+3 = 4
- 1+3+5 = 9
- 1+3+5+7 = 16
- 1+3+5+7+9 = 25
- 1+3+5+7+9+11 = 36
n 个奇数 (1,3,5,7,...) 之和等于 n 的平方, 其中 n 大于 0.
对此, 我们可以对 num 做减法, 每次减去一个奇数, 最后判断是否等于 0.
- public boolean isPerfectSquare4(int num) {
- int i = 1;
- while (num> 0) {
- num -= i;
- i += 2;
- }
- return num == 0;
- }
06 小结
算法专题目前已连续日更超过两个月, 算法题文章 77 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/4f9ba005c250