Valid Perfect Square

有效的完全平方数

题目描述

给定一个正整数，判断是否为完全平方数。不要使用库函数。

示例：

输入：15
输出：false

解法

解法一：牛顿法

• 时间复杂度：O(logn)

• 空间复杂度：O(1)

func isPerfectSquare(num int) bool {
    if num < 2 {
        return true
    }
    x := num / 2
    for x*x > num {
        x = (x + num/x) / 2
    }
    return x*x == num
}

解法二：二分法

• 时间复杂度：O(logn)

• 空间复杂度：O(1)

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

解法三：二分法2

• 时间复杂度：O(logn)

• 空间复杂度：O(1)

func isPerfectSquare(num int) bool {
    ans := 0
    for i := 30; i >= 0; i-- {
        tmp := ans + (1 << i)
        if tmp*tmp > num {
            continue
        }
        if tmp*tmp == num {
            return true
        }
        ans = tmp
    }
    return false
}

解法四：利用1 + 3 + ... + (2n-1) = n^2

• 时间复杂度：O(logn)

• 空间复杂度：O(1)

func isPerfectSquare(num int) bool {
    layer := 1
    for num > 0 {
        num -= 2*layer - 1
        layer++
    }
    return num == 0
}