共计 936 个字符,预计需要花费 3 分钟才能阅读完成。
无效的齐全平方数
题目形容:给定一个 正整数 num,编写一个函数,如果 num 是一个齐全平方数,则返回 true,否则返回 false。
齐全平方数:齐全平方指用一个整数乘以本人例如
1*1
,2*2
,3*3
等,依此类推。若一个数能示意成某个整数的平方的模式,则称这个数为齐全平方数。齐全平方数是非正数,而一个齐全平方数的项有两个。进阶 : 不要 应用任何内置的库函数,如 sqrt。
示例阐明请见 LeetCode 官网。
起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。
解法一:二分查找法
用二分查找的办法来寻找 num 的开方是否是一个整数。首先,申明 low 为 0,high 为最大整数的平方根,二分查找的过程如下:
- 首先,low 不大于 high;
- 申明一个 mid,mid 等于
(low + high) / 2
;- 如果
mid * mid == num
,则阐明 num 是一个齐全平方数,间接返回 true;- 如果
mid * mid > num
,则将 high 设置为mid - 1
,而后进行下一轮解决;- 如果
mid * mid < num
,则将 low 设置为mid + 1
,而后进行下一轮解决。最初,如果没找到整数的平方等于 num,则阐明 num 不是一个齐全平方数,返回 false。
public class LeetCode_367 {
/**
* 二分查找法
* @param num
* @return
*/
public static boolean isPerfectSquare(int num) {int low = 1, high = (int) Math.sqrt(Integer.MAX_VALUE);
while (low <= high) {int mid = (low + high) / 2;
if (mid * mid == num) {return true;} else if (mid * mid > num) {high = mid - 1;} else if (mid * mid < num) {low = mid + 1;}
}
return false;
}
public static void main(String[] args) {System.out.println(isPerfectSquare(14));
}
}
【每日寄语】愿你忠于本人,活的认真; 笑得放肆。
正文完