Problem
Given a positive integer num, write a function which returns True if num is a perfect square else False.
NoteDo not use any built-in library function such as sqrt.
ExamplesExample 1:
Input: 16 Returns: True
Example 2:
Input: 14 Returns: FalseSolution Newton"s method, close to O(1)
public class Solution { public boolean isPerfectSquare(int num) { if (num < 1) return false; long t = num/2+1; while (t*t > num) { t = (t+num/t)/2; } return t*t == num; } }Binary-Search method, O(logn)
public class Solution { public boolean isPerfectSquare(int num) { long start = 1, end = num; while (start <= end) { long mid = start + (end-start)/2; long t = mid * mid; if (t == num) return true; else if (t < num) start = mid+1; else end = mid-1; } return false; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/64981.html
Problem Given a positive integer num, write a function which returns True if num is a perfect square else False. Example For example:Given num = 16Returns True Solution class Solution { public boo...
摘要:动态规划法建立空数组从到每个数包含最少平方数情况,先所有值为将到范围内所有平方数的值赋两次循环更新,当它本身为平方数时,简化动态规划法四平方和定理法 Problem Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) whi...
摘要:动态规划复杂度时间空间思路如果一个数可以表示为一个任意数加上一个平方数,也就是,那么能组成这个数最少的平方数个数,就是能组成最少的平方数个数加上因为已经是平方数了。 Perfect Squares Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4...
Problem Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. Example 1: Input: n = 12Output: 3 Explanation: 12 = 4 + 4 + 4.Exampl...
摘要:题目要求判断一个数字最少由几个平方数的和构成。思路一暴力递归要想知道什么样的组合最好,暴力比较所有的结果就好啦。当然,效率奇差。代码如下思路三数学统治一切这里涉及了一个叫做四平方定理的内容。有兴趣的可以去了解一下这个定理。 题目要求 Given a positive integer n, find the least number of perfect square numbers (...
阅读 1949·2023-04-26 01:59
阅读 3264·2021-10-11 11:07
阅读 3295·2021-09-22 15:43
阅读 3374·2021-09-02 15:21
阅读 2549·2021-09-01 10:49
阅读 901·2019-08-29 15:15
阅读 3089·2019-08-29 13:59
阅读 2829·2019-08-26 13:36