နှစ် ဦး Leetcode ဖြေရှင်းချက်၏ပါဝါ


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

ကျွန်တော်တို့ကိုပေးထားတယ် ကိန်း နှင့်ရည်မှန်းချက်မှာကိန်းပြည့်သည်နှစ်စွမ်းအားဟုတ်မဟုတ်စစ်ဆေးရန်ဖြစ်သည်။ ဆိုလိုသည်မှာ၎င်းသည် 'စွမ်းအားတစ်ခုလုံးအဖြစ်ကိုယ်စားပြုနိုင်သည်။2'' ။

နှစ် ဦး Leetcode ဖြေရှင်းချက်၏ပါဝါ

နမူနာ

16
Yes
13
No

ချဉ်းကပ်နည်း

အသေးအဖွဲဖြေရှင်းချက်တစ်ခုဖြစ်နိုင်သည်။ ကိန်း၏အဓိကအချက်များအားလုံးရှိမရှိစစ်ဆေးပါ။ '2' ဤနည်းလမ်း၏အချိန်ရှုပ်ထွေးမှုသည်အိုဖြစ်သည် (log2N) ။ အကောင်းဆုံးနည်းလမ်းဖြင့်လုပ်ရန်ကျွန်ုပ်တို့သည် Bit ကိုင်တွယ်ခြင်း၏အကူအညီကိုယူနိုင်သည်။

"နှစ်လုံး၏စွမ်းအားရှိသောမည်သည့်နံပါတ်မဆို binary ကိုယ်စားပြုမှုတစ်ခုတည်း bit ကိုသာသတ်မှတ်နိုင်သည်"

တစ် ဦး တည်းသာရှိကြောင်းမည်သို့စစ်ဆေးနိုင်မည်နည်း တစ်ခုတည်း bit နဲ့ set အဆိုပါ binary form မှာ?

နံပါတ်တစ်ခုကိုစဉ်းစားပါ၊ x ။

အခု x ကနှစ်ခုရဲ့စွမ်းအားရှိမယ်ဆိုရင် (x - ၁) လူအပေါင်းတို့သည်ပိတ်ပါလိမ့်မယ် ညာဘက် -bits set bit နဲ့ ('0' ဟုသတ်မှတ်ပါ) နှင့် set bit သည် unset ဖြစ်လိမ့်မည်။

x = 8 [1000] x - 1 = 7 [0111]

ဒီတော့သုံးပါ BITWISE-AND ကိန်းရှင် (x - 1) ကိန်းတစ်ခုကနှစ်ခုရဲ့စွမ်းအားရှိသလားလို့ပြောနိုင်တယ်။ x ကို & (x - 1) = 0

Algorithm (အသေးအဖွဲ)

  1. ကိန်းဂဏန်းအားဖြင့် ဆက်၍ စားပါ '2' ကခွဲလို့မရပါဘူးသည်အထိ '2' တော့ဘူး.
  2. ကိန်းဂဏန်းနှင့်ညီလျှင် '1':
    • ကိန်းပြည့်ကနှစ်ရဲ့စွမ်းအားတစ်ခု
  3. အခြားသူ
    • ကိန်းပြည့်ကနှစ်ရဲ့စွမ်းအားမဟုတ်ဘူး

Algorithm (Bit-Manipulation)

  1. x & (x - 1) သည်သုညနှင့်ညီလားဆိုတာစစ်ဆေးပါ
    • ဟုတ်လျှင်နံပါတ်သည် 2 ၏စွမ်းအားဖြစ်သည်
    • ကိန်းစစ်မဟုတ်ရင် 2 ရဲ့စွမ်းအားမဟုတ်ဘူး

အကောင်အထည်ဖော်ရေး

နှစ် ဦး Leetcode ဖြေရှင်းချက်၏ပါဝါ၏ C ++ အစီအစဉ်

နုံနည်းလမ်း

#include <bits/stdc++.h>
using namespace std;

bool powerOfTwo(int n)
{
    while(n % 2 == 0)
        n /= 2;
    return (n == 1);
}


int main()
{
    int n = 16;
    if(powerOfTwo(n))
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';


    return 0;
}

အကောင်းဆုံးနည်းလမ်း

#include <bits/stdc++.h>
using namespace std;

bool powerOfTwo(int n)
{
    //16 = [10000]
    //15 = [01111]
    //16 & 15 = 0
    return (n & (n - 1)) == 0;
}


int main()
{
    int n = 16;
    if(powerOfTwo(n))
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';


    return 0;
}
Yes

Two Leetcode Solution ၏စွမ်းအား၏ Java Program

နုံနည်းလမ်း

class power_of_two
{
    public static boolean powerOfTwo(int n)
    {
        while(n % 2 == 0)
            n /= 2;
        return (n == 1);
    }

    public static void main(String args[])
    {
        int n = 16;
        if(powerOfTwo(n))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

အကောင်းဆုံးနည်းလမ်း

class power_of_two
{
    public static boolean powerOfTwo(int n)
    {
        return (n & (n - 1)) == 0;
    }

    public static void main(String args[])
    {
        int n = 16;
        if(powerOfTwo(n))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
Yes

ရှုပ်ထွေးဆန်းစစ်ခြင်း

နှစ် ဦး Leetcode ဖြေရှင်းချက်၏ပါဝါကိုအချိန်ရှုပ်ထွေး

Naive ချဉ်းကပ်မှု၏အချိန်ရှုပ်ထွေးသည် အို (log2N), ဘယ်မှာ N ကို = ပေးထားသောကိန်း။ သို့သော်အကောင်းဆုံးချဉ်းကပ်နည်းသည် Bitwise-And ကဲ့သို့လျင်မြန်ပြီးပိုမိုမြန်ဆန်သောကြောင့်အချိန်ရှုပ်ထွေးမှုရှိသည် အို (၁)

နှစ် ဦး Leetcode ဖြေရှင်းချက်၏ပါဝါ၏အာကာသရှုပ်ထွေး

ပရိုဂရမ်တွင်သုံးသောနေရာသည် function လက်မှတ်ဖြစ်သည်။ ထို့ကြောင့်စဉ်ဆက်မပြတ်နေရာကိုအသုံးပြုသည် - အို (၁)