367.有效的完全平方数.md

367.有效的完全平方数

/*
 * @lc app=leetcode.cn id=367 lang=typescript
 *
 * [367] 有效的完全平方数
 */

// @lc code=start
function isPerfectSquare(num: number): boolean {}
// @lc code=end

解法 1: 二分查找

• 时间复杂度:
• 空间复杂度:

function isPerfectSquare(num: number): boolean {
  if (num < 2) return true
  let left = 0,
    right = num
  while (left < right) {
    const mid = Math.round(left + (right - left) / 2)

    if (mid > num / mid) {
      right = mid - 1
    } else {
      left = mid
    }
  }
  return right * right === num
}

解法 2: 牛顿迭代法

function isPerfectSquare(num: number): boolean {
  if (num < 2) return true

  let res = num
  while (true) {
    const tmp = res / 2 + num / (res * 2)
    if (Math.abs(tmp - res) <= 1e-7) break
    res = tmp
  }
  return Math.floor(res) * Math.floor(res) === num
}

Case

test.each([
  { x: 1, result: true },
  { x: 4, result: true },
  { x: 5, result: false },
  { x: 8, result: false },
  { x: 14, result: false },
  { x: 16, result: true },
  { x: 100, result: true },
])('x = $x', ({ x, result }) => {
  expect(isPerfectSquare(x)).toBe(result)
})