Сила двух решений Leetcode


Сложный уровень Легко
Часто спрашивают в Apple
Битовые манипуляции Биты Математики

Нам дается целое и цель состоит в том, чтобы проверить, является ли целое число степенью двойки, то есть может ли оно быть представлено как некоторая целая степень '2».

Сила двух решений Leetcode

Пример

16
Yes
13
No

Подход

Тривиальное решение может быть таким: проверьте, все ли простые множители целого числа равны '2'. Временная сложность этого метода будет O (log2N). Чтобы сделать это оптимальным образом, мы можем прибегнуть к помощи Bit-манипуляций.

«Любое число, представляющее собой степень двойки, может иметь только один бит, установленный в двоичном представлении»

Как можно проверить, что есть только одиночный набор бит в двоичной форме?

Рассмотрим любое число x.

Теперь, если x - некоторая степень двойки, то (х - 1) выключит все правые биты установленному биту (установите их как «0»), и установленный бит будет сброшен.

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

Итак, используя ПОБИТУ-И x и (x - 1), мы можем сказать, что если число является некоторой степенью двойки, то, х & (х - 1) = 0

Алгоритм (тривиальный)

  1. Продолжайте делить число на '2' пока он не делится на '2' больше не.
  2. Если число равно '1':
    • Целое число - это степень двойки
  3. Еще
    • Целое число не является степенью двойки

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

  1. Проверить, равно ли x & (x - 1) нулю
    • Если да, то число является степенью двойки.
    • Целое число не является степенью двойки, иначе

Реализация

Программа на C ++ о силе двух решений Leetcode

Наивный метод

#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-программа мощности двух решений Leetcode

Наивный метод

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).