Магутнасць двух рашэнняў Leetcode  


Узровень складанасці Лёгка
Часта пытаюцца ў яблык
алгарытмы Бітавая маніпуляцыя біты кадаваньне інтэрв'ю інтэрв'юп LeetCode LeetCodeSolutions Матэматыка

Нам дадзена цэлае і мэта складаецца ў тым, каб праверыць, ці з'яўляецца цэлае лік у два разы, гэта значыць яно можа быць прадстаўлена як нейкая цэлая ступень '2».

Сіла двух рашэнняў LeetcodePin

Прыклад  

16
Yes
13
No

Падыход  

Банальным рашэннем можа быць: Праверце, ці ўсе простыя фактары цэлага ліку ўсе '2'. Часавая складанасць гэтага метаду будзе O (log2N). Для таго, каб зрабіць гэта аптымальным спосабам, мы можам скарыстацца бітавымі маніпуляцыямі.

"Любы лік, які складае ступень двое, можа мець толькі адзін біт, зададзены ў двайковым прадстаўленні"

Як можна праверыць, ці ёсць толькі адзін біт у двайковай форме?

Разгледзім любы лік, х.

Цяпер, калі х - гэта нейкая ступень у два, значыць (х - 1) выключыць усе правыя біты да зададзенага біта (усталюйце іх як "0"), і ўсталяваны біт будзе адключаны.

х = 8 [1000], х - 1 = 7 [0111]

Такім чынам, выкарыстоўваючы ДВУЦІ-І з х і (х - 1), мы можам сказаць, калі лік - гэта нейкая ступень у два, тады, x & (x - 1) = 0

Алгарытм (трывіяльны)  

  1. Працягвайце дзяліць лік на "2" пакуль ён не дзеліцца на "2" больш не.
  2. Калі лік роўны "1":
    • Цэлае лік - гэта ступені два
  3. Яшчэ
    • Цэлае лік - гэта не два
Глядзіце таксама
Сіла чатырох рашэнняў Leetcode

Алгарытм (біта-маніпуляцыя)  

  1. Праверце, калі x & (x - 1) роўна нулю
    • Калі так, то лік роўны 2
    • У адваротным выпадку цэлае лік не складае ступені 2

Рэалізацыя  

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

Java-праграма Power of Two Leetcode Solution

Наіўны метад

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

Аналіз складанасці  

Складанасць часу магутнасці двух рашэнняў з літаркодам

Складанасць часу наіўнага падыходу складаецца O (log2N), дзе N = дадзенае цэлае лік. Аднак аптымальны падыход больш хуткі, бо Bitwise-And хутчэй, і таму складанасць у часе складае O (1).

Касмічная складанасць магутнасці рашэння з двума літаркодамі

Сігнатурай функцыі з'яўляецца толькі месца, якое выкарыстоўваецца ў праграме. Такім чынам, выкарыстоўваецца пастаянная прастора - O (1).