Разтвор на Hameting Leetcode  


Ниво на трудност Лесно
Често задавани в Кирпич Амазонка Facebook
алгоритми Манипулация на битове Bits кодиране Интервю интерпретация LeetCode LeetCodeSolutions

Декларация за проблема  

В този проблем ни дават две цели числа, A и B, и целта е да намерим разстояние на коване между дадените цели числа. Целите числа са по-големи от / равни на и по-малко от 231   

Пример

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

Разтвор на Hameting Leetcodeщифт

Подход (броене по бит)  

Първото нещо, което е много ясно е, че тъй като трябва да намерим броя на бита където съответните битови стойности в дадените две числа са различни, трябва да направим побитово-XOR на дадените цели числа. Резултатите, които XOR ще произведе в индивидуална битова позиция, ще бъдат „1“, ако бита в двете цели числа в тази позиция са различни. В противен случай XOR ще изведе '0' на тази позиция.

След като изведохме тази част, единственото последващо действие е ефективното откриване на броя на битовете, които са определен (битова стойност = '1') в побитовия XOR на дадените цели числа. За да преброим тази стойност, ние циклираме за всеки бит (от да се 30) и проверете дали е зададена в стойността XOR или не.

Вижте също
Налични снимки за решението на Rook Leetcode

алгоритъм

  1. Съхранявайте побитовия XOR на двете цели числа в променлива - xor_
  2. Инициализиране CNT = 0 за съхраняване на резултата
  3. За всеки I = 0 и i <31:
    • АкоI-битът е зададен xor_
      • увеличение cnt: cnt ++ 
    • увеличение i
  4. връщане CNT

Внедряване на решение на Hamet Distance 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

Анализ на сложността на решението на Leetcode за разстоянието на Хаминг

Сложност във времето

O (1) тъй като извършваме постоянен брой операции, независимо от входа.

Космическа сложност

O (1) тъй като използваме постоянно пространство в паметта.

Подход (Ефективно преброяване на битове - алгоритъм на Керниган)  

Първите стъпки остават същите, което е да се намери битовият XOR на teo дадени числа. Въпреки това, ние преброяваме броя на зададените битове в техния XOR ефективно, използвайки алгоритъма на Kernighan, който се основава на идеята:

Когато изпълнявамепобитово &'операция между цяло число "Аз" и „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. Инициализиране CNT = 0 за съхраняване на резултата
  3. Докато xor_ е по-голяма от :
    1. увеличение cnt: cnt ++
    2. задайте xor_ = xor_ & (xor_ - 1)
  4. връщане CNT

Внедряване на решение на Hamet Distance 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

Анализ на сложността на решението на Leetcode за разстоянието на Хаминг

Сложност във времето

O (1) тъй като извършваме постоянен брой операции, независимо от входа.

Космическа сложност

O (1) тъй като използваме постоянно пространство в паметта.

1