유효한 Perfect Square Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 아마존
알고리즘 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 27

이 게시물은 유효한 Perfect Square Leetcode 솔루션에 있습니다.

문제 설명

“Valid Perfect Square”문제에서는“num”이라는 숫자가 주어지고이 숫자가 완전 제곱인지 아닌지 확인해야합니다. 내장 된 sqrt 함수를 사용하지 않고이를 확인해야합니다.

숫자가 완전한 제곱이면 true를 반환하고 그렇지 않으면 false를 반환합니다.

num = 25
true

설명 :

유효한 Perfect Square Leetcode 솔루션

25는 제곱근이 5이므로 유효한 완전 제곱입니다. 따라서 답은 참이됩니다.

접근

내장 함수를 사용할 수 없으므로이 문제를 해결하기위한 기본 접근 방식은 1에서 num까지의 각 숫자를 확인하고 그 제곱을 찾은 다음 제곱이 num과 같은지 확인하는 것입니다. 제곱이 num과 같으면 num은 유효한 완전 제곱이므로 true를 반환하고 그렇지 않으면 false를 반환합니다.

각 숫자를 선형으로 확인하지만, 우리는 이진 검색 방식. 이 접근 방식에서는 검색 범위, 시작 지점 및 끝점을 결정해야합니다.

  1. 시작점은 1이됩니다.
  2. num보다 큰 숫자의 제곱은 항상 num보다 크므로 끝점은 num이됩니다.
  3. 그래서 그때의 범위 이진 검색 1에서 숫자입니다.
  4. 이제 우리는 중간의 제곱을 찾을 것입니다. 제곱이 num과 같으면 true를 반환합니다. else :
    1. 정사각형이 num보다 크면 끝 점이 mid-1로 줄어 듭니다.
    2. 그렇지 않으면 시작점이 mid + 1이됩니다.
  5. 결국 num이 숫자의 제곱과 일치하지 않으면 false를 반환합니다.

암호

유효한 Perfect Square Leetcode 솔루션을위한 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

유효한 Perfect Square Leetcode 솔루션을위한 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

유효한 Perfect Square Leetcode 솔루션의 복잡성 분석

시간 복잡성

위 코드의 시간 복잡성은 O (로그온). 여기서 n은 num의 값입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (1) 답을 저장하는 데 변수 만 사용하고 있기 때문입니다.

참조

코멘트를 남겨

Translate »