美文网首页
367. Valid Perfect Square[Easy,

367. Valid Perfect Square[Easy,

作者: DrunkPian0 | 来源:发表于2017-09-28 00:10 被阅读9次

Given a positive integer num, write a function which returns True if num is a perfect square else False.
Note: Do not use any built-in library function such as sqrt.
Example 1:
Input: 16
Returns: True

从1开始加的话会超时。要利用一个数学规律:

1 = 1
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
25 = 1 + 3 + 5 + 7 + 9
36 = 1 + 3 + 5 + 7 + 9 + 11
....
so 1+3+...+(2n-1) = (2n-1 + 1)n/2 = nn

复杂度O(sqrt(n))

public boolean isPerfectSquare(int num) {
     int i = 1;
     while (num > 0) {
         num -= i;
         i += 2;
     }
     return num == 0;
 }

或者用牛顿法。
https://discuss.leetcode.com/topic/49325/a-square-number-is-1-3-5-7-java-code/2

相关文章

网友评论

      本文标题:367. Valid Perfect Square[Easy,

      本文链接:https://www.haomeiwen.com/subject/rogpextx.html