91 - 有效的完全平方数

题目

给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。

说明：不要使用任何内置的库函数，如 sqrt。

示例 1：

输入：16 输出：True

示例 2：

输入：14 输出：False

解答

感觉又是数学题。。

只能想到从小到大循环一个个试，感觉这么做会超时。

牛顿迭代法

作者：Gerry_666

链接：https://leetcode-cn.com/problems/valid-perfect-square/solution/niu-dun-die-dai-fa-by-gerry_666/

image.png

var isPerfectSquare = function (num) {
  if (num === 1) {
    return true
  }
  let r = num
  while (r * r > num) {
    r = Math.floor((r + Math.floor(num / r)) / 2)
  }
  if (r * r === num) {
    return true
  } else {
    return false
  }
};

Runtime: 56 ms, faster than 58.80% of JavaScript online submissions for Valid Perfect Square.

Memory Usage: 33.7 MB, less than 75.00% of JavaScript online submissions for Valid Perfect Square.

func isPerfectSquare(num int) bool {
    if num == 1 {
        return true
    }
    r := num
    for r*r > num {
        r = (r + num/r) / 2
    }
    if r*r == num {
        return true
    } else {
        return false
    }
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Valid Perfect Square.

Memory Usage: 1.9 MB, less than 50.00% of Go online submissions for Valid Perfect Square.

二分法

看了题解意识到，还能用两分法😂

作者：gpe3DBjDS1

链接：https://leetcode-cn.com/problems/valid-perfect-square/solution/you-xiao-de-wan-quan-ping-fang-shu-by-gpe3dbjds1/

var isPerfectSquare = function (num) {
  if (num === 1) {
    return true
  }
  let left = 1, right = num
  while (left < right) {
    let mid = (left + right) >>> 1
    if (mid * mid < num) {
      left = mid + 1
    } else {
      right = mid
    }
  }
  if (right * right === num) {
    return true
  } else {
    return false
  }
};

Runtime: 56 ms, faster than 58.80% of JavaScript online submissions for Valid Perfect Square.

Memory Usage: 33.8 MB, less than 75.00% of JavaScript online submissions for Valid Perfect Square.

func isPerfectSquare(num int) bool {
    if num == 1 {
        return true
    }
    left, right := 1, num
    for left < right {
        mid := (left + right) >> 1
        if mid*mid < num {
            left = mid + 1
        } else {
            right = mid
        }
    }
    if right*right == num {
        return true
    } else {
        return false
    }
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Valid Perfect Square.

Memory Usage: 1.9 MB, less than 100.00% of Go online submissions for Valid Perfect Square.

完全平方数

1 + 3 + 5 + ... + (2n - 1) = n ^ 2

var isPerfectSquare = function (num) {
  if (num === 1) {
    return true;
  }
  let i = 1
  while (num > 0) {
    num -= i
    i += 2
  }
  return num === 0
};

Runtime: 68 ms, faster than 26.93% of JavaScript online submissions for Valid Perfect Square.

Memory Usage: 34.5 MB, less than 50.00% of JavaScript online submissions for Valid Perfect Square.

func isPerfectSquare(num int) bool {
    if num == 1 {
        return true
    }
    i := 1
    for num > 0 {
        num -= i
        i += 2
    }
    return num == 0
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Valid Perfect Square.

Memory Usage: 1.9 MB, less than 50.00% of Go online submissions for Valid Perfect Square.