N və onun ikiqat leetcode həllini yoxlayın

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

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

“N-nin və onun ikiqat olduğunu yoxlayın” problemində bizə bir sıra n element verilir. Dizinin uzunluğu ikidən böyük və ya bərabərdir.

Bizim vəzifəmiz, sıra içərisində birinci dəyərin ikinci dəyərdən ikiqat çox olması üçün bir cütün olub olmadığını yoxlamaqdır.

Daha rəsmi olaraq i, j üçün i mövcud olub olmadığını yoxlamalıyıq

misal

arr = [7,1,14,11]
true

Explanation:

N və onun ikiqat leetcode həllini yoxlayınPin

Bu giriş üçün nəticə doğrudur, çünki sual bizdən hər hansı bir dəyərin və verilmiş massivdəki ikiqat çıxışının olub olmadığını yoxlamağımızı tələb edir, belə ki, 7 və 14 bu meyarlara cavab verir, çünki 14 7-nin ikiqatdır.

N və onun ikiqat mövcud Leetcode həllinin olub olmadığını yoxlamaq üçün yanaşma

Bu problemi həll etmək üçün ilk yanaşma Gücün tətbiqi yanaşma. Dizidəki hər bir element üçün tam massivi keçib onun ikiqat mövcud olub olmadığını yoxlayacağıq. bu şərti təmin edən bir element tapsaq, gerçək qayıdacağıq, əks halda sonunda yalan qayıdacağıq. Bu yanaşma üçün zaman mürəkkəbliyi O (n * n) -dir, çünki massivin hər elementi üçün biz tam massivi keçirik.

Sırasız bir xəritə və ya sıralanmamış dəst istifadə edərək bu problemi daha yaxşı bir zaman mürəkkəbliyində həll edə bilərik.

  1. Dizini keçin.
  2. Dizidəki hər bir element üçün ikiqat olub olmadığını yoxlayın və ya yarısı onsuz da var.
  3. Şərt doğrudursa, sadəcə geriyə qayıdın, əks halda həmin elementi xəritəyə əlavə edin.
  4. Bir sıra keçidi tamamlanırsa və hər hansı bir elementin ikiqatını tapmasaq, yalnış olaraq qaytarırıq.

Həyata keçirilməsi

Check N və onun ikiqat olduğunu yoxlamaq üçün C ++ kodu

#include <bits/stdc++.h> 
using namespace std; 
    bool checkIfExist(vector<int>& arr) {
      unordered_map<int,bool>mp;
        for(int i=0;i<arr.size();i++)
        {
            if(mp[arr[i]*2]==1||(mp[arr[i]/2]==1&&arr[i]%2==0))
                return true;
            mp[arr[i]]=1;
        }
        return false;
    }
int main() 
{ 
 vector<int> arr = {7,1,14,11}; 
 bool ans=checkIfExist(arr);
 cout <<boolalpha;
 cout<<ans<<endl;
 return 0;
}
true

Check If N və Onun Cüt Mövcudluğu üçün Java kodu

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static boolean checkIfExist(int[] arr) {
        Set<Integer> seen = new HashSet<>();   
        for (int i : arr) {
            if (seen.contains(2 * i) || (i % 2 == 0 && seen.contains(i / 2)))
                return true;
            seen.add(i);
        }
        return false;
    }
  public static void main(String[] args) {
        int [] arr = {7,1,14,11}; 
        boolean ans=checkIfExist(arr); 
        System.out.println(ans);
  }
}
true

N və onun ikiqat mövcud Leetcode həllinin olub olmadığını yoxlamaq üçün mürəkkəbliyin təhlili

Zaman mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (n) Sıralanmamış xəritədə axtarışın və yerləşdirmənin orta vaxt mürəkkəbliyini O (1) olaraq nəzərə alaraq.

Kosmik mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (n) çünki ən pis halda bütün elementləri saxlamağımız lazım ola bilər.

References

Crack Sistemi Dizayn Müsahibələri
Translate »