Etibarlı Mükəmməl Kvadrat LeetCode Həlli

cuqquldamaq Facebook LinkedIn Bufer Reddit Tumblr

Mündəricat

Problem bəyanat

Etibarlı Mükəmməl Kvadrat LeetCode Həlli – Verilmiş a müsbət tam num, True if qaytaran funksiya yazın num mükəmməl kvadratdır, başqa yanlışdır.

İzlə: Etməyin kimi hər hansı daxili kitabxana funksiyasından istifadə edin sqrt.

Input: num = 16
Output: true

Izahat

Bizim həllimiz üçün bir sərhəd müəyyən edilmişdir. istənilən n ədədi üçün onun kvadrat kökü 1 ilə n arasında ola bilər, ona görə də cavabın 1-dən n-ə qədər olacağını bilirik.

Sadə yanaşma

1-dən n-ə qədər hər nömrəni yoxlayın. O(n) vaxtını alacaqdı.

Optimallaşdırılmış yanaşma

İdeya sadədir, biz sadəcə bütün cüt bölənləri tapırıq. 2-dən …-ə qədər təkrar edirik və bölən tapdıqda,
bölməyə çalışırıq num bununla bir daha.

Misal üçün:
giriş: ədəd = 180

2-dən başlayaraq təkrarlayın:
180%2==0 ?
bəli -> ədəd = 180/2 = 90

yenidən 2-yə bölə biləcəyimizi yoxlayın:
90%2==0 ?
bəli -> ədəd = 90/2 = 45

indi 45-dir.
say azaldığından, biz yenidən 2-dən başlayaraq təkrar etməliyik:

45%2==0 ?
yox -> təkrarlamağa davam edin

45%3==0 ?
bəli -> ədədlər = 45/3 = 15
bir daha bölək

15%3==0 ?
bəli -> ədədlər = 15/3 = 5
indi 5-dir.

num azaldı -> 2-dən başlayaraq yenidən təkrarlayın
5%2==0 ?
yox -> təkrarlamağa davam edin
5%3==0 ?
yox -> təkrarlamağa davam edin
5%4==0 ?
yox -> təkrarlamağa davam edin
5%5==0 ?
bəli -> ədədlər = 5/5 = 1
bir dəfə daha bölə biləcəyimizi yoxlayın:
1%5==0 ?
yox -> yalanı qaytarın

tətbiq etmək ikili axtarış axtarış fəzasında və problem O(log n) vaxtında həll edilə bilər.

Kodu

Etibarlı Mükəmməl Kvadrat üçün C++ Kodu

class Solution {
public:
    bool isPerfectSquare(int num) {
        if (num < 0) return false;
        if (num == 0 || num == 1) return true;
        
        int i = 0;
        int j = num;
        
        while (i <= j) {
            long b = i + (j-i)/2;
            
            if (b*b == num)
                return true;
            else if (b*b < num)
                i = b+1;
            else
                j = b-1;
        }
        
        return false;
    }
};

Etibarlı Mükəmməl Meydan üçün Java Kodu

class Solution {
    public boolean isPerfectSquare(int num) {
        int low=1, high=num;
        while(low<=high) {
            long mid=(low+high)>>>1;
            if(mid*mid==num) return true;
            else if(mid*mid>num) high=(int)mid-1;
            else low=(int)mid+1;
        }
        return false;
    }
}

Etibarlı Mükəmməl Meydan üçün Python Kodu

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left = 0
        right = num
        while left <= right:

            mid = (left+right)//2

            if mid*mid==num:
                return True
            elif mid*mid > num:
                right = mid - 1
            else:
                left = mid+1
        return False