နံပါတ်ဖြည့်စွက် Leetcode ဖြေရှင်းချက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Apple
နည်းနည်းခြယ်လှယ် bits Cloudera

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

ဒီပြသနာမှာတော့ကျွန်တော်တို့ကိုဒdecimalမကိန်းတစ်ခုပေးထားတယ်။ ရည်ရွယ်ချက်မှာ၎င်းကိုရှာဖွေရန်ဖြစ်သည် အဖြည့်.

နမူနာ

N = 15
0
N = 5
2

နံပါတ်ဖြည့်စွက် Leetcode ဖြေရှင်းချက်

ချဉ်းကပ်မှု (နည်းနည်းချင်းစီလှန်ခြင်း)

ငါတို့ရှိသမျှကိုလှန်နိုင်ပါတယ် နည်းနည်း ကိန်းပြည့်ကိုရရန် 'N' ကိန်းပြည့်။ အရေးကြီးတဲ့အပိုင်းကငါတို့ပါ မပေးနိုင် ၎င်း၏ 32-bits အပေါငျးတို့သလှန်။ ကြောင်းကြောင့်၎င်း၏ binary 1 ရဲ့ဖြည့်စွက်မှုလိမ့်မယ်။ ကျွန်ုပ်တို့သည် LSB မှနံပါတ်ရှိလက်ဝဲဘက်အစွန်းသို့အနည်းငယ်သာလှန်လိုက်ပါ။ ဒါကိုသုညဖြစ်လာမချင်း၊ ပေးထားတဲ့နံပါတ် N ကို 2 နဲ့စားခြင်းအားဖြင့်၎င်းကိုကျွန်ုပ်တို့ရရှိနိုင်သည်။ နောက်တစ်ကြိမ်မှာလည်းသက်ဆိုင်ရာ bit ကိုလှန်နိုင်သည်။

နံပါတ်ဖြည့်စွက် Leetcode ဖြေရှင်းချက်၏အကောင်အထည်ဖော်မှု

C ++ အစီအစဉ်

#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 အစီအစဉ်

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

နံပါတ်ဖြည့် Leetcode ဖြေရှင်းချက်၏ရှုပ်ထွေးခွဲခြမ်းစိတ်ဖြာ

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

အို (log2N), ဘယ်မှာ N ကို = ပေးထားသောကိန်း။ ပေးထားသောနံပါတ်အတွက် bits အရေအတွက်ကိုအကြိမ်ပေါင်းများစွာ iterate လုပ်သည်။

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

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

ချဉ်းကပ်မှု (အကောင်းဆုံး)

အဆိုပါ optimized ချဉ်းကပ်မှုမဆိုအသုံးမပြုဖို့ဖြစ်ပါတယ် အကို ကုဒ်ထဲမှာ။ ဆိုလိုသည်မှာ code ကို loops များသို့မဟုတ်အခြေခံအားဖြင့်မည်သည့် branch မှညွှန်ကြားချက်မပါဘဲဖြေရှင်းရန်ဖြစ်သည်။ ဤချဉ်းကပ်မှုတွင်ကျွန်ုပ်တို့သည်ပထမ ဦး ဆုံးရှိသော binary mask ကိုရှာသည် အားလုံး -bits ထားကြ၏ကနေစတင် '0th' bit အမှ leftmost set ကိုနည်းနည်း ပေးထားတဲ့နံပါတ်အတွက်, ပြီးတော့သူ့ဟာသူနှင့်အတူ XOR ။ ဤသည်ကျွန်တော်တို့ကိုလိုအပ်သောဖြည့်စွက်ပေးပါလိမ့်မယ်။

N အတွက်လိုအပ်သော binary mask ကိုရှာရန် N >> 1, N >> 2, N >> 4, … N >> 16 နှင့်အတူ bwise OR OR ပေးထားတဲ့နံပါတ်ကိုရှာရန်အတွက် N >> k = N ကိုညာဘက်ရွေ့ပြောင်းခြင်း။ နေရာများ။ ဤနည်းအားဖြင့်ကျွန်ုပ်တို့သည်အများဆုံးသိသာထင်ရှားသော bit (leftmost bit) ပြီးနောက် bits များအားလုံးကိုသတ်မှတ်ပြီးလိုအပ်သော mask ကိုထုတ်လုပ်လိမ့်မည်။

နံပါတ်ဖြည့်စွက် Leetcode ဖြေရှင်းချက်၏အကောင်အထည်ဖော်မှု

C ++ အစီအစဉ်

#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 အစီအစဉ်

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

နံပါတ်ဖြည့် Leetcode ဖြေရှင်းချက်၏ရှုပ်ထွေးခွဲခြမ်းစိတ်ဖြာ

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

အို (၁), အ bitwise binary စစ်ဆင်ရေးအလွန်အစာရှောင်ခြင်းနှင့်စစ်ဆင်ရေးယူသော်လည်းအဖြစ် အို (log2N), အချိန်ရှုပ်ထွေး 32-bit နဲ့ကိန်းများအတွက်စဉ်ဆက်မပြတ်ဖြစ်ပါတယ်။

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

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