მოქმედებს სრულყოფილი კვადრატული Leetcode ამოხსნა


Რთული ტური Easy
ხშირად ეკითხებიან Amazon
LeetCode

ეს პოსტი მოცემულია Valid Perfect Square Leetcode Solution- ზე

პრობლემის განცხადება

პრობლემის ”Valid Perfect Square” მოცემულია ნომერი ”num” და უნდა გადავამოწმოთ არის თუ არა ეს სრულყოფილი კვადრატი. ჩვენ უნდა შეამოწმოთ ეს ჩაშენებული sqrt ფუნქციის გამოყენების გარეშე.

თუ რიცხვი არის სრულყოფილი კვადრატი, ჩვენ დავაბრუნებთ სიმართლეს, სხვა შემთხვევაში დავაბრუნებთ false- ს.

მაგალითი

num = 25
true

განმარტება:

მოქმედებს სრულყოფილი კვადრატული Leetcode ამოხსნა

25 მოქმედი სრულყოფილი კვადრატია, რადგან მისი კვადრატული ფესვი 5. ასე რომ, პასუხი ხდება ჭეშმარიტი.

მიდგომა

რადგან ჩვენ ვერ ვიყენებთ ჩამონტაჟებულ ფუნქციებს, ამ პრობლემის გადაჭრის ძირითადი მიდგომაა თითოეული რიცხვის შემოწმება 1-დან ნომრამდე და მისი კვადრატის პოვნა, შემდეგ შეამოწმეთ მისი კვადრატი ტოლია თუ არა. თუ კვადრატი უდრის num- ს, num არის Valid Perfect Square, ასე რომ, ჩვენ დავუბრუნდებით true- ს, თორემ დავაბრუნებთ false- ს.

თითოეული რიცხვის ხაზოვანი შემოწმების მიუხედავად, ჩვენ შეგვიძლია გავაუმჯობესოთ ამოხსნა ა ორობითი ძიების მიდგომა. ამ მიდგომით, ჩვენ უნდა გადავწყვიტოთ ჩვენი ძებნის დიაპაზონი, საწყისი წერტილი და საბოლოო წერტილი.

  1. საწყისი წერტილი იქნება 1.
  2. საბოლოო წერტილი იქნება num, რადგან num– ზე მეტი ნებისმიერი რიცხვის კვადრატი ყოველთვის იქნება num– ზე მეტი.
  3. მაშ ასე, დიაპაზონი ორობითი ძებნა არის 1 დან ნომრამდე.
  4. ახლა ჩვენ შუა კვადრატს ვიპოვით. თუ კვადრატი ტოლია num- ისა, ჩვენ სხვას დავუბრუნდებით:
    1. თუ კვადრატი num- ზე მეტია, ჩვენი საბოლოო წერტილი შემცირდება 1-ის შუა რიცხვამდე.
    2. წინააღმდეგ შემთხვევაში, საწყისი წერტილი გახდება შუა რიცხვები + 1.
  5. დაბოლოს, თუ num არ ემთხვევა რიცხვის რომელიმე კვადრატს, მაშინ ჩვენ ვუბრუნდებით false.

კოდი

C ++ კოდი Valid Perfect Square Leetcode Solution- ისთვის

#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- ისთვის

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 არის რიცხვის მნიშვნელობა.

კოსმოსური სირთულის

ზემოთ მოცემული კოდის სივრცის სირთულეა O (1) რადგან პასუხის შესანახად ვიყენებთ მხოლოდ ცვლადს.

ლიტერატურა