有効なパーフェクトスクエアリートコードソリューション


難易度 簡単に
よく聞かれる Amazon (アマゾン)
リートコード

この投稿は、有効なパーフェクトスクエアリートコードソリューションに関するものです。

問題文

問題「有効な完全な正方形」では、番号「num」が与えられ、この番号が完全な正方形であるかどうかを確認する必要があります。 組み込みのsqrt関数を使用せずにこれを確認する必要があります。

数値が完全な平方である場合はtrueを返し、そうでない場合はfalseを返します。

num = 25
true

説明:

有効なパーフェクトスクエアリートコードソリューション

25は、平方根が5であるため、有効な完全な正方形です。したがって、答えは真になります。

アプローチ

組み込み関数を使用できないため、この問題を解決するための基本的なアプローチは、1からnumまでの各数値をチェックしてその正方形を見つけ、その正方形がnumに等しいかどうかをチェックすることです。 正方形がnumと等しい場合、numは有効な完全な正方形であるため、trueを返します。それ以外の場合は、falseを返します。

各数値を線形にチェックするにもかかわらず、を使用することでソリューションを改善できます。 二分探索アプローチ。 このアプローチでは、検索範囲、開始点、および終了点を決定する必要があります。

  1. 開始点は1になります。
  2. numより大きい任意の数の二乗は常にnumより大きいため、エンドポイントはnumになります。
  3. だからその時の範囲 二分探索 1からnumです。
  4. 今、私たちは真ん中の正方形を見つけるでしょう。 二乗がnumに等しい場合、それ以外の場合はtrueを返します。
    1. 正方形がnumより大きい場合、エンドポイントは1の中央に減少します。
    2. それ以外の場合、開始点はmid +1になります。
  5. 結局、numが数値のどの平方とも一致しない場合、falseを返します。

コード

有効なパーフェクトスクエアリートコードソリューションのC ++コード

#include <bits/stdc++.h> 
using namespace std; 
    bool isPerfectSquare(int num) {
        int s=1,e=num;
        while(s<=e)
        {
            long long int mid=s+(e-s)/2;
            if(mid*mid==num)
                return true;
            else if(mid*mid>num)
             e=mid-1;
            else
                s=mid+1;
        }
        return false;
    }
int main() 
{ 
 int num=25;
 cout<<boolalpha;
 cout<<isPerfectSquare(num)<<endl; 
 return 0;
}
true

有効なパーフェクトスクエアリートコードソリューションのJavaコード

import java.util.Arrays; 
public class Tutorialcup {
    public static  boolean isPerfectSquare(int num){
    long s=1,e=num;
        while(s<=e)
        {
            long mid=s+(e-s)/2;
            if(mid*mid==num)
                return true;
            else if(mid*mid>num)
             e=mid-1;
            else
                s=mid+1;
        }
        return false;
    }
  public static void main(String[] args) {
    int num=25;
    boolean ans=  isPerfectSquare(num);
    System.out.println(ans);
  }
}
true

有効なパーフェクトスクエアリートコードソリューションの複雑さの分析

時間の複雑さ

上記のコードの時間計算量は O(logn)。 ここで、nはnumの値です。

スペースの複雑さ

上記のコードのスペースの複雑さは O(1) 回答を格納するために変数のみを使用しているためです。

リファレンス