367. Valid Perfect Square

Leetcode 问题: 367. Valid Perfect Square
Categories:
Tags:

题目

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Follow up: Do not use any built-in library function such as sqrt.

传入正整数 num，判断这个数字是不是完美的平方数

不能用内建的 sqrt 方法

Example

Input: num = 16
Output: true

Input: num = 14
Output: false

演算法

1. 设定左右检查数字范围

但一定介于 1~num 中间，所以可以使用 Binary Search 设定左右指标

2. 比较找到的数字

A. 找到的数字较大

检查数字比较小，平方数较大，所以右侧数字皆较大不可能是答案，检查左侧数字

B. 找到的数字较小

检查数字比较大，平方数较小，所以左侧数字皆较小不可能是答案，检查右侧数字

C. 找到了一样的数字

中位数平方与要检查的数字相同，回传 true

若 Binary Search 搜寻到最后都没有找到，则这个数字不是完美的平方数，回传 false

答案

JavaScript

function isPerfectSquare(checkNumber) {
    // 设定左右检查的数字
    var leftNumber = 1;
    var rightNumber = checkNumber;
    while (leftNumber <= rightNumber) {
        // 当「左边的数字」小于等于「右边的数字」继续检查
        // 中位数
        var middleNumber = Math.floor((leftNumber + rightNumber) / 2);
        // 中位数平方
        var squareMiddleNumber = middleNumber * middleNumber;
        if (checkNumber == squareMiddleNumber) {
            // 如果找到了数字
            return true;
        }
        else if (checkNumber < squareMiddleNumber) {
            // 检查数字比较小，平方数较大
            // 所以右侧数字皆较大不可能是答案，检查左侧数字
            rightNumber = middleNumber - 1;
        }
        else {
            // 检查数字比较大，平方数较小
            // 所以左侧数字皆较小不可能是答案，检查右侧数字
            leftNumber = middleNumber + 1;
        }
    }
    return false;
}

TypeScript

function isPerfectSquare(checkNumber: number): boolean {
    // 设定左右检查的数字
    let leftNumber: number = 1;
    let rightNumber:number = checkNumber;

    while (leftNumber <= rightNumber) {
        // 当「左边的数字」小于等于「右边的数字」继续检查
        // 中位数
        let middleNumber = Math.floor((leftNumber + rightNumber) / 2);
        // 中位数平方
        let squareMiddleNumber = middleNumber * middleNumber;

        if (checkNumber == squareMiddleNumber) {
            // 如果找到了数字
            return true;
        } else if (checkNumber < squareMiddleNumber) {
            // 检查数字比较小，平方数较大
            // 所以右侧数字皆较大不可能是答案，检查左侧数字
            rightNumber = middleNumber - 1;
        } else {
            // 检查数字比较大，平方数较小
            // 所以左侧数字皆较小不可能是答案，检查右侧数字
            leftNumber = middleNumber + 1;
        }
    }

    return false;
};

参考资料