Valid Perfect Square Leetcode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 46

Bu yazı Valid Perfect Square Leetcode Solution-dadır

Problem bəyanat

“Valid Perfect Square” problemində bizə “num” rəqəmi verilir və bu rəqəmin mükəmməl bir kvadrat olub olmadığını yoxlamalıyıq. Bunu daxili sqrt funksiyasından istifadə etmədən yoxlamalıyıq.

Əgər nömrə mükəmməl bir kvadratdırsa, doğrunu qaytaracağıq, əksinə yalanını qaytararıq.

misal

num = 25
true

Explanation:

Valid Perfect Square Leetcode Həlli

25, kökü 5 olduğu üçün etibarlı bir kvadratdır. Beləliklə, cavab doğru olur.

Yanaşma

Yerləşdirilmiş funksiyalardan istifadə edə bilmədiyimiz üçün bu problemi həll etmək üçün əsas yanaşma hər ədədi 1-dən num-a qədər yoxlamaq və kvadratını tapmaq, kvadratının num-a bərabər olub olmadığını yoxlamaqdır. Əgər kvadrat num-a bərabərdirsə, onda num bir Valid Perfect Square-dir, belə ki, true-a qayıdırıq, əks halda false-a qayıdarıq.

Hər bir ədədi xətti yoxlamaya baxmayaraq, a istifadə edərək həll yolunu inkişaf etdirə bilərik ikili axtarış yanaşması. Bu yanaşmada axtarış aralığımıza, başlanğıc nöqtəsinə və son nöqtəyə qərar verməyimiz lazımdır.

  1. Başlanğıc nöqtəsi 1 olacaqdır.
  2. Son nöqtə num olacaq, çünki num-dan böyük olan hər hansı bir ədədin kvadratı həmişə numdan böyük olacaqdır.
  3. Yəni o zaman üçündür ikili axtarış saya 1-dir.
  4. İndi ortanın kvadratını tapacağıq. Əgər kvadrat num-a bərabərdirsə, onda else true qayıdacağıq:
    1. kvadrat kvadratdan böyükdürsə, son nöqtəmiz 1-in ortasına enəcəkdir.
    2. əks halda başlanğıc nöqtəsi + 1 ortasına çevriləcək.
  5. Sonda, numun hər hansı bir kvadrat ilə uyğun gəlmirsə, yalnış qayıdırıq.

Kodu

Valid Perfect Square Leetcode Solution üçün C ++ kodu

#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

Valid Perfect Square Leetcode Solution üçün Java kodu

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

Valid Perfect Square Leetcode Solüsyonunun Mürəkkəblik Analizi

Zaman mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (logn). Burada n numun dəyəridir.

Kosmik mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki cavabı saxlamaq üçün yalnız dəyişəndən istifadə edirik.

References

Şərh yaz

Translate »