Leetcode эки чечиминин күчү


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

Бизге ан бүтүн жана максаты бүтүн сандын экиден турган кубаттуулугун текшерүү, башкача айтканда, аны 'бүтүндөй кубаттуулугу катары көрсөтүүгө болот2'.

Leetcode эки чечиминин күчү

мисал

16
Yes
13
No

жакындоо

Маанилүү эмес чечим болушу мүмкүн: бүтүндөй негизги факторлордун бардыгын текшериңиз '2'. Бул ыкманын убакыттын татаалдыгы O (log2N). Муну оптималдуу түрдө жасаш үчүн, Бит манипуляцияларынын жардамын алабыз.

"Эки кубаттуулуктагы ар кандай сан экилик чагылдырууда бир гана битке ээ болот"

Бар экендигин кантип текшерсе болот бир бит коюлган экилик түрүндөбү?

Кандайдыр бир санды карап көрөлү, х.

Эми, эгер х экөөнүн кандайдыр бир кубаттуулугу болсо, анда (x - 1) бардыгын өчүрөт оң бит коюлган битке (аларды '0' кылып коюңуз) жана коюлган бит коюлбай калат.

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

Ошентип, колдонуу BITWISE-AND х жана (х - 1) санында, эгерде сан экөөнүн кандайдыр бир кубаттуулугуна ээ болсо, анда x & (x - 1) = 0

Алгоритм (Тривиалдуу)

  1. Санды бөлүштүрө бериңиз '2' чейин бөлүнбөйт '2' мындан ары.
  2. Эгерде саны барабар болсо '1':
    • Бүтүн сан эки күч
  3. дагы
    • Бүтүн сан эки күч эмес

Алгоритм (Бит-манипуляция)

  1. X & (x - 1) нөлгө барабар экендигин текшериңиз
    • Эгер ооба болсо, анда бул сан 2дин күчүн билдирет
    • Бүтүн сан 2 даража эмес, башкача айтканда

ишке ашыруу

Leetcode эки чечиминин кубаттуулугу программасы C ++

Naive Method

#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

Leetcode Solution эки кубаттуулугунун Java программасы

Naive Method

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 эки эритмесинин кубаттуулугунун убакыттын татаалдыгы

Наивдик мамиленин убакыттын татаалдыгы O (log2N), мында N = берилген бүтүн сан. Бирок, оптималдуу ыкма ылдамыраак, анткени Bitwise-And ылдамыраак, ошондуктан убакыттын татаалдыгына ээ O (1).

Leetcode эки чечиминин кубаттуулугунун космостук татаалдыгы

Программада боштук гана функциянын колу болуп саналат. Демек, туруктуу мейкиндик колдонулат - O (1).