Hamming Distance Leetcode ဖြေရှင်းချက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Adobe က အမေဇုံ Facebook က
နည်းနည်းခြယ်လှယ် bits

ပြProbleနာဖော်ပြချက်

ဒီပြproblemနာမှာ၊ A နဲ့ B နှစ်ခုလုံးကိုပေးထားတယ် hamming အကွာအဝေး ပေးထားသောကိန်းအကြား။ ကိန်းကပိုကြီးတယ် နှင့်ထက်နည်းသည် 231   

နမူနာ

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

Hamming Distance Leetcode ဖြေရှင်းချက်

ချဉ်းကပ်နည်း (နည်းနည်းချင်းစီရေတွက်ခြင်း)

ပထမ ဦး ဆုံးရှင်းရှင်းလင်းလင်းသိရတာကကျွန်တော်တို့နံပါတ်ရှာဖို့လိုလို့ပါ -bits ပေးထားသောနံပါတ်နှစ်ခု၏သက်ဆိုင်သော bit တန်ဖိုးများသည်ကွဲပြားခြားနားလျှင်ပေးထားသောကိန်းများ၏ bitwise-XOR ကိုလုပ်ရန်လိုအပ်သည်။ အကယ်၍ XOR သည် bit bit အနေအထားတစ်ခုတွင်ထုတ်လုပ်မည့်ရလဒ်သည် '1' ဖြစ်လိမ့်မည် ကြောင်းအနေအထားမှာနှစ်ခုကိန်းအတွက် -bits ကွဲပြားခြားနားသောဖြစ်ကြသည်။ ဒီလိုမှမဟုတ်ရင်, XOR ကြောင်းအနေအထားမှာ '0' ထုတ်လုပ်ပါလိမ့်မယ်။

ယခုကျွန်ုပ်တို့သည်ဤအပိုင်းကိုဆုံးဖြတ်လိုက်ပြီဆိုလျှင်ကျန်ရှိသောတစ်ခုတည်းသောနောက်ဆက်တွဲမှာ bits အရေအတွက်ကိုထိရောက်စွာရှာဖွေရန်ဖြစ်သည် အစုံ ပေးထားသောကိန်းများ၏ bitwise XOR တွင် (bit value = '1') ။ ဒီတန်ဖိုးကိုရေတွက်ဖို့အတွက်ကျွန်တော်တို့ဟာ bit ကတိုင်းအတွက် loop လုပ်တယ် 0 သို့ 30) နှင့် XOR တန်ဖိုးသတ်မှတ်ထားခြင်းရှိမရှိစစ်ဆေးပါ။

algorithm

  1. နှစ်လုံး၏ bitwise XOR ကို variable တစ်ခုထဲတွင်သိမ်းပါ။ xor_
  2. စတငျ cnt = 0 ရလဒ်သိုလှောင်ရန်
  3. တိုင်းအတွက် i = 0 နှင့် i <31:
    • အကယ်၍ith'' bit ကိုသတ်မှတ်ထားခြင်းဖြစ်သည် xor_
      • တိုး cnt: cnt ++ 
    • တိုး i
  4. ပြန်လာ cnt

Hamming Distance Leetcode Solution ၏အကောင်အထည်ဖော်မှု

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

Hamming Distance Leetcode Solution ၏ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (၁) ကျနော်တို့မသက်ဆိုင် input ကို၏စစ်ဆင်ရေးတစ်ခုစဉ်ဆက်မပြတ်အရေအတွက်ကလုပ်ဆောင်အဖြစ်။

အာကာသရှုပ်ထွေးမှု

အို (၁) ကျနော်တို့စဉ်ဆက်မပြတ်မှတ်ဉာဏ်အာကာသကိုသုံးပါအဖြစ်။

ချဉ်းကပ်နည်း (အရေအတွက်ကိုထိရောက်စွာတွက်ချက်ခြင်း - Kernighan's Algorithm)

ပထမအဆင့်သည်ထပ်တူကျသည်။ ၎င်းသည်ပေးထားသောနံပါတ်များ၏ bitwise XOR ကိုရှာရန်ဖြစ်သည်။ သို့သော်စိတ်ကူးပေါ်အခြေခံသော Kernighan's Algorithm ကို အသုံးပြု၍ သူတို့၏ XOR တွင် set-bits အရေအတွက်ကိုထိရောက်စွာရေတွက်သည်။

ငါတို့လုပ်တဲ့အချိန် 'တူညီသော &တစ်ခုကိန်းအကြား '' စစ်ဆင်ရေး 'ငါ' နှင့် 'i - 1', ၎င်း၏ညာဘက်အများဆုံးသတ်မှတ်ထား bit နဲ့ဖြစ်ပါတယ် မအောင်မြင်.

အထက်ပါအတွေးအခေါ်ကိုဥပမာတစ်ခုဖြင့်လိုက်နာကြပါစို့။ N ကို = 36 (100100) ကိုစဉ်းစားပါ။ အခု N-1 နဲ့ '&' လုပ်မယ်ဆိုရင်၊

ရှင်းရှင်းလင်းလင်းသော N & (N - 1) = (36 & 35) = (100100 & 100011) = (100000) မအောင်မြင် ညာဘက်အများဆုံး bit (ညာဘက်ကနေအနေအထား 2 မှာ) ။ အလားတူစွာကျွန်ုပ်တို့သည် ထပ်မံ၍ ရေးသားနိုင်သည်

N & (N-1) = (32 & 31) = (100000 & 011111) = 000000 ကိုနောက်တဖန်ညာဘက်မှအနေအထား 5 မှာ rightmost set bit နဲ့မသတ်မှတ်ပေးနိုင်သော။ N ကိန်းသုညဖြစ်လာသည်နှင့်အမျှလုပ်ငန်းစဉ်ကိုဆက်မလုပ်နိုင်တော့ပါ။

ဤလှပသောအတွေးအခေါ်သည်အလွန်အသုံးဝင်သည် set-bits ရေတွက် ကိန်းတစ်ခုတည်းကိုသာကျွန်တော်တို့လိုချင်တယ် ကြားက အကြိမ်ပေါင်းများစွာအဖြစ် set-bits ရှိပါတယ် ပေးထားသောကိန်း၌တည်၏။

algorithm

  1. နှစ်လုံး၏ bitwise XOR ကို variable တစ်ခုထဲတွင်သိမ်းပါ။ xor_
  2. ကန ဦး cnt = 0 ရလဒ်သိုလှောင်ရန်
  3. စဉ် xor_ ထက်သာ။ ကြီးမြတ်သည် 0:
    1. တိုး cnt: cnt ++
    2. xor_ = xor_ သတ်မှတ်မည် (xor_ - 1)
  4. ပြန်လာ cnt

Hamming Distance Leetcode Solution ၏အကောင်အထည်ဖော်မှု

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

Hamming Distance Leetcode Solution ၏ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (၁) ကျနော်တို့မသက်ဆိုင် input ကို၏စစ်ဆင်ရေးတစ်ခုစဉ်ဆက်မပြတ်အရေအတွက်ကလုပ်ဆောင်အဖြစ်။

အာကာသရှုပ်ထွေးမှု

အို (၁) ကျနော်တို့စဉ်ဆက်မပြတ်မှတ်ဉာဏ်အာကာသကိုသုံးပါအဖြစ်။