유효한 Perfect Square Leetcode 솔루션

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

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

이 게시물은 유효한 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 »