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.
Mündəricat
Problem bəyanat
Prime Palindrome LeetCode Həlli - Bizə tam ədəd verilir və ən kiçik əsası qaytarmağımız xahiş olunur. palindrom verilmiş 'n' tam ədədinə bərabər və ya böyükdür.
Tam ədəddir baş tam olaraq iki bölən varsa: 1 və özü. Qeyd edək ki, 1 a deyil baş nömrə.
- Məsələn, 2, 3, 5, 7, 11 və 13 sadə ədədlərdir.
Tam ədəd adır palindrom sağdan sola oxuduğu kimi soldan sağa oxuyursa.
- Məsələn, 101 və 12321 palindromlar.
Test nümunələri cavabın həmişə mövcud olması və [2, 2*10^8] diapazonunda olması üçün yaradılır.
Nümunələr və izahatlar
Misal 1:
Input: n = 6 Output: 7 Explanation: 7 is prime & palindrome
Misal 2:
Input: n = 8 Output: 11 Explanation: 9 is palindrome but not prime, 10 is neither prime nor palindrome, hence 11
Misal 3:
Input: n = 13 Output: 101 Explanation: no two digits number can be palindrome with both different digits, eg. palindromes having 2 digits are 22, 33, 44, 55 ..... but none of these are prime.
Yanaşma
Optimallaşdırma ilə Brute-Force
Biz n+1-dən 2*10^8-ə qədər bütün ədədləri təkrarlaya bilərik (çünki sualda cavablar həmişə mövcuddur və [2, 2*10^8] diapazonundadır).
Bununla belə, bu yanaşma TLE-yə səbəb olacaqdır. Bu həlli optimallaşdırmaq üçün [1e7, 1e8] diapazonunda ən kiçik sadə palindromun 100030001 olması faktından istifadə edəcəyik. Buna görə də, əgər n bu diapazonda yerləşirsə, sadəcə olaraq bu ədəddən keçməyə başlayın və hər bir ədədin sadə olub olmadığını yoxlamağa davam edin. palindrom.
Zamanın mürəkkəbliyini daha da azaltmaq üçün heç vaxt ola bilməyəcəyi kimi bütün cüt ədədləri atlaya bilərik baş. Beləliklə, hər təkrarlamada döngədə göstəricini 2 dəfə artırın.
Primallığı və ədədin palindrom olub olmadığını yoxlamaq üçün 2 ayrı funksiyadan istifadə edə bilərik. Primallığın yoxlanılması asan məsələdir, lakin nəzərə alın ki, biz palindromun yoxlanılmasında istifadə olunan əks funksiyanı təyin etdik. Bu funksiya hər dəfə təkrarlamada ədədi 10-a bölür və qalanı saxlayır.
QEYD: biz palindromik xüsusiyyəti yoxlamaq üçün to_string inbuilt funksiyasından istifadə etməmişik. to_String-dən istifadə çox vaxt aparır və TLE ilə nəticələnir.
Kodu
Prime Palindrome LeetCode Həlli üçün C++ kodu
class Solution {
bool isPrime(int n) {
for(int i=2; i<=sqrt(n);i++) {
if(n%i==0) return 0;
}
return 1;
}
int reverse(int n){
int m = 0;
while (n) {
m = m*10 + n % 10;
n /= 10;
}
return m;
}
int isPalindrome(int n){
return n == reverse(n);
}
public:
int primePalindrome(int n) {
if( n <= 2) return 2;
if(n>=1e7 && n<=1e8) {
n=100030001;
}
if(n%2==0) n++;
for(int i=n; i>=n; i+=2){
if(isPalindrome(i)) {
if(isPrime(i)) return i;
}
}
return -1;
}
};
Prime Palindrome LeetCode Solution üçün Java kodu
class Solution {
private Boolean isPrime(int n) {
for(int i=2; i<=Math.sqrt(n);i++) {
if(n%i==0) return false;
}
return true;
}
private int reverse(int n){
int m = 0;
while (n>0) {
m = m*10 + n % 10;
n /= 10;
}
return m;
}
private Boolean isPalindrome(int n){
return n== reverse(n);
}
public int primePalindrome(int n) {
if( n <= 2) return 2;
if(n>=1e7 && n<=1e8) {
n=100030001;
}
if(n%2==0) n++;
for(int i=n; i>=n; i+=2){
if(isPalindrome(i))
if(isPrime(i)) return i;
}
return -1;
}
}
Mürəkkəblik təhlili
- Zamanın mürəkkəbliyi: O(n*logn*sqrt(n))
- Döngə O(n/2) vaxtını alaraq n/2 dəfə işləyir, yəni. O(n) Bu, Baş və Palindrom adlı 2 funksiyanı çağırır
- isPrime O(sqrt(n)) vaxt alır
- isPalindrome O(logn) vaxtını alır
- Kosmik mürəkkəblik: O (1)
- əlavə yer tələb olunmur
