Sayı Tamamlayıcı Leetcode Həlli

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

Bu problemdə bizə ondalık rəqəm verilir. Məqsəd onu tapmaqdır complement.

misal

N = 15

0

N = 5

2

Pin

Yanaşma (bit-bit sürüşmə)

Hər birini çevirə bilərik parça tamamlayıcısını almaq üçün 'N' tamsayıda. Əhəmiyyətli hissəsi bizdir bilməz 32 bitinin hamısını çevirin. Bu, onun ikili 1-in tamamlayıcısı ilə nəticələnəcəkdir. Yalnız LSB-dən başlayaraq nömrədəki ən sola qoyulmuş bitə qədər çevirməliyik. Verilən N sayını 2-yə, sıfıra qədər bölməklə buna nail ola bilərik. Və hər təkrarda uyğun biti çevirə bilərik.

Sayı Tamamlayıcı Leetcode həllinin tətbiqi

C ++ Proqramı

#include <bits/stdc++.h>

using namespace std;

int findComplement(int num) {
    int todo = num , i = 0;
    while(todo > 0) {
        num ^= (1 << i);
        todo >>= 1;
        ++i;
    }
    return num;
}

int main() {
    int n = 15;
    cout << findComplement(n) << endl;
    return 0;
}

Java Proqramı

class number_complement {
    public static void main(String args[]) {
        int n = 15;
        System.out.println(findComplement(n));
    }

    public static int findComplement(int num) {
        int todo = num , i = 0;
        while(todo > 0) {
            num ^= (1 << i);
            todo >>= 1;
            ++i;
        }
        return num;
    }
}

0

Sayı Tamamlayıcı Leetcode Çözümünün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (log2N)burada N = verilmiş tam. Verilən saydakı bitlərin sayı qədər təkrarlayırıq.

Kosmik Mürəkkəblik 

O (1), yalnız daimi yaddaşdan istifadə etdiyimiz üçün.

Yanaşma (optimallaşdırılmış)

Optimize edilmiş yanaşma heç birini istifadə etməməkdir dallanma kodda. Yəni kodu hər hansı bir döngə və ya hər hansı bir əsas olaraq, hər hansı bir dallanma təlimatı olmadan həll etmək. Bu yanaşmada əvvəlcə ikili bir maska ​​tapırıq bütün bitlər quraşdırılıb, dən başlayaraq '0' bit qədər ən solda bit verilmiş sayda və sonra özü ilə XOR. Bu, bizə lazımi tamamlayıcı verəcəkdir.

N üçün tələb olunan ikili maska ​​tapmaq üçün N >> 1, N >> 2, N >> 4,… N >> 16 ilə verilmiş ədədi VƏ ya verdik ki, burada N >> k = sağa N-yi k ilə dəyişirik. yerlər. Bu metodla, bütün bitləri Ən Əhəmiyyətli Bitdən (ən sol tərəfdən) sonra təyin edib lazımi maskanı istehsal edərdik.

Sayı Tamamlayıcı Leetcode həllinin tətbiqi

C ++ Proqramı

#include <bits/stdc++.h>

using namespace std;

int findComplement(int num) {
    int mask = num;
    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;
    return num ^ mask;
}

int main() {
    int n = 15;
    cout << findComplement(n) << endl;
    return 0;
}

Java Proqramı

class number_complement {
    public static void main(String args[]) {
        int n = 15;
        System.out.println(findComplement(n));
    }

    public static int findComplement(int num) {
        int mask = num;
        mask |= mask >> 1;
        mask |= mask >> 2;
        mask |= mask >> 4;
        mask |= mask >> 8;
        mask |= mask >> 16;
        return num ^ mask;
    }
}

0

Sayı Tamamlayıcı Leetcode Çözümünün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (1), bitsel ikili əməliyyatlar çox sürətli olduğundan əməliyyatlar davam etsə də O (log2N), zamanın mürəkkəbliyi 32 bit tam ədədlər üçün sabitdir.

Kosmik Mürəkkəblik 

O (1)yalnız daimi yaddaş boşluğundan istifadə etdiyimiz üçün.