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;
};

參考資料