Hamming қашықтықтағы парақ шешімі  


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Amazon Facebook
алгоритмдер Бит манипуляциясы Биттер кодтау сұхбат сұхбат дайындау LeetCode LeetCodeSolutions

Проблемалық мәлімдеме  

Бұл есепте бізге A және B екі бүтін сандар беріледі, және мақсаты - табу қашықтықты соғу берілген бүтін сандар арасында. Бүтін сандар одан үлкен / тең және одан аз 231   

мысал

First Integer = 5 , Second Integer = 2
3
First Integer = 4 , Second Integer = 5
1

Hamming қашықтықтағы парақ шешімітүйреуіш

Тәсіл (Битпен бит санау)  

Бірінші анық нәрсе, өйткені біз оның санын табуымыз керек биттерді егер берілген екі сандағы сәйкес бит мәндері әр түрлі болса, біз берілген бүтін сандардың биттік-XOR-ын орындауымыз керек. XOR жеке биттік позицияда шығаратын нәтижелер егер '1' болады сол позициядағы екі бүтін санның биттері әр түрлі болды. Әйтпесе, XOR сол күйінде '0' шығарады.

Енді біз осы бөлімді шығарғаннан кейін, тек биттердің санын тиімді анықтау ғана қалады жиынтық (бит мәні = '1') берілген бүтін сандардың XOR разрядында. Бұл мәнді санау үшін біз әр бит үшін цикл жасаймыз (бастап дейін 30) және XOR мәнінде орнатылған-орнатылмағанын тексеріңіз.

Сондай-ақ, қараңыз
Rook Leetcode шешіміне арналған суреттер

Алгоритм

  1. Екі бүтін санның биттік XOR айнымалысында сақтаңыз - xor_
  2. Бастамаңыз ҰБТ = 0 нәтижені сақтау үшін
  3. Әрқайсысы үшін i = 0 және мен <31:
    • Егер 'ит'бит орнатылған xor_
      • Көбею cnt: cnt ++ 
    • Көбею i
  4. қайтару ҰБТ

Heting қашықтықтағы Leetcode шешімін енгізу

C ++ бағдарламасы

#include <bits/stdc++.h>

using namespace std;

int hammingDistance(int x , int y){
    int xor_ = x ^ y , cnt = 0;
    for(int i = 0 ; i < 31 ; i++){
        if((1 << i) & xor_)
            cnt++;
    }
    return cnt;
}

int main(){
    int x = 5 , y = 2;
    cout << hammingDistance(x , y) << endl;
    return 0;
}

Java бағдарламасы

class hamming_distance{

    static int hammingDistance(int x , int y){
        int xor_ = x ^ y , cnt = 0;
        for(int i = 0 ; i < 31 ; i++){
            if(((1 << i) & xor_) > 0)
                cnt++;
        }
        return cnt;
    }

    public static void main(String args[]){
        int x = 5 , y = 2;
        System.out.println(hammingDistance(x , y));
    }
}
3

Heting қашықтықты Leetcode шешімінің күрделілігін талдау

Уақыттың күрделілігі

O (1) өйткені біз кіріс түріне қарамастан операциялардың тұрақты санын жасаймыз.

Ғарыштың күрделілігі

O (1) өйткені біз жадтың тұрақты кеңістігін қолданамыз.

Тәсіл (Биттерді тиімді санау - Керниган алгоритмі)  

Алғашқы қадамдар өзгеріссіз қалады, яғни тео берілген сандардың биттік XOR-ын анықтау. Дегенмен, біз олардың биттер жиынтығының санын XOR-да керниган алгоритмін қолдана отырып тиімді түрде санаймыз, ол келесі идеяға негізделген:

Біз өнер көрсеткенде 'биттік &'бүтін сан арасындағы жұмыс 'мен' және 'i - 1', оның ең дұрыс орнатылған биті орнатылмаған.

Мысал арқылы жоғарыдағы идеяны ұстанайық. N = 36 (100100) қарастырайық. Енді біз N - 1-мен '' алсақ, біз мынаны аламыз:

N & (N - 1) = (36 & 35) = (100100 & 100011) = (100000) анық орнатылмаған ең оң жақ бит (оң жақтан 2 позицияда). Сол сияқты, біз бұдан әрі жаза аламыз:

Сондай-ақ, қараңыз
Leetcode шешімінің жылы күні

N & (N - 1) = (32 & 31) = (100000 & 011111) = 000000, қайтадан оң жақтағы орнатылған разрядты оң жақтан 5-позицияға шығарады. Бүтін N саны нөлге айналғандықтан, процесті әрі қарай жалғастыру мүмкін емес.

Бұл әдемі идея өте пайдалы екенін дәлелдейді берілген биттерді санау бүтін санда, өйткені бізге тек керек қайталану қанша рет болса белгіленген биттер бар берілген бүтін санда.

Алгоритм

  1. Екі бүтін санның биттік XOR айнымалысында сақтаңыз - xor_
  2. Бастау ҰБТ = 0 нәтижені сақтау үшін
  3. уақыт xor_ қарағанда үлкен :
    1. Көбею cnt: cnt ++
    2. xor_ = xor_ & (xor_ - 1) орнатыңыз
  4. қайтару ҰБТ

Heting қашықтықтағы Leetcode шешімін енгізу

C ++ бағдарламасы

#include <bits/stdc++.h>

using namespace std;

int hammingDistance(int x , int y){
    int xor_ = x ^ y , cnt = 0;
    while(xor_ > 0){
        xor_ = (xor_ & (xor_ - 1));
        ++cnt;
    }
    return cnt;
}

int main(){
    int x = 5 , y = 2;
    cout << hammingDistance(x , y) << endl;
    return 0;
}

Java бағдарламасы

class hamming_distance{

    static int hammingDistance(int x , int y){
        int xor_ = x ^ y;
        int cnt = 0;
        while(xor_ > 0){
            xor_ = (xor_ & (xor_ - 1));
            ++cnt;
        }
        return cnt;
    }

    public static void main(String args[]){
        int x = 5 , y = 2;
        System.out.println(hammingDistance(x , y));
    }
}
3

Heting қашықтықты Leetcode шешімінің күрделілігін талдау

Уақыттың күрделілігі

O (1) өйткені біз кіріс түріне қарамастан операциялардың тұрақты санын жасаймыз.

Ғарыштың күрделілігі

O (1) өйткені біз жадтың тұрақты кеңістігін қолданамыз.

1