Hamming Distance Leetcode Solution


Кыйынчылык деңгээли жеңил
Көп суралган Adobe Amazon Facebook
Bit Manipulation Bits

Маселени билдирүү

Бул маселеде бизге А жана В эки бүтүн сандары берилген жана максаты табуу аралыкты согуу берилген сандардын ортосунда. Бүтүн сандар андан чоң / барабар жана андан азыраак 231   

мисал

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

Hamming Distance Leetcode Solution

Ыкма (Бит менен саноо)

Эң биринчи түшүнүктүү нерсе, анткени биз анын санын табышыбыз керек бит эгерде берилген эки сандын тиешелүү бит маанилери ар башка болсо, анда берилген сандардын бит-XOR кылышыбыз керек. XOR жеке бит абалында чыгарган натыйжалар эгер '1' болсо ал позициядагы эки бүтүн сандагы бит башкача. Болбосо, XOR ал позицияда '0' чыгарат.

Эми бул бөлүктү чыгарып, биттердин санын натыйжалуу билүү гана калды. коюлган (бит мааниси = '1') берилген бүтүндөй сандардын XOR разрядында. Бул маанини эсептөө үчүн, биз ар бир бит үчүн цикл (баштап.) 0 үчүн 30) жана XOR мааниде коюлгандыгын текшерип көрүңүз.

Algorithm

  1. Эки бүтүн сандын биттик XORсун өзгөрүлмө катары сактоо - xor_
  2. Initialize CNT Жыйынтыкты сактоо үчүн = 0
  3. Ар бири үчүн мен = 0 жана i <31:
    • Эгерде 'IMP'бит коюлган xor_
      • Көбөйтүү cnt: cnt ++ 
    • Көбөйтүү i
  4. Return CNT

Hamming Расстояние 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 разрядын аныктоо. Ошентсе да, алардын XORдогу коюлган биттердин санын Кернигандын алгоритмин колдонуп натыйжалуу эсептейбиз, ал идеяга негизделген:

Качан биз аткарабыз 'биттик &'бүтүн сан ортосундагы иш "Мен" жана 'i - 1', анын эң туура коюлган бити коюлбай калды.

Келгиле, жогорудагы идеяны мисал аркылуу келтирели. N = 36 (100100) карап көрөлү. Эми аны N - 1 менен '&' алсак, төмөнкүнү алабыз:

N & (N - 1) = (36 & 35) = (100100 & 100011) = (100000) unets оң эң көп (оңдон 2-позицияда). Ошо сыяктуу эле, биз дагы жаза алабыз:

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

Бул сонун идея абдан пайдалуу экендигин далилдейт белгиленген биттерди эсептөө бүтүндөй бир санда, биз жөн гана керек кайталоо канча эсе көп болсо белгиленген биттер бар берилген бүтүндөй

Algorithm

  1. Эки бүтүн сандын биттик XORсун өзгөрүлмө катары сактоо - xor_
  2. Баштоо CNT Жыйынтыкты сактоо үчүн = 0
  3. жатканда xor_ караганда чоң 0:
    1. Көбөйтүү cnt: cnt ++
    2. xor_ = xor_ & (xor_ - 1) койду
  4. Return CNT

Hamming Расстояние 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) биз туруктуу эс мейкиндигин колдонуп жатканда.