İki Leetcode həllinin gücü

Çətinlik səviyyəsi Asan
Tez-tez soruşulur alma
alqoritmlər Bit manipulyasiya Bits kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions RiyaziyyatBaxılıb 106

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Bizə bir tam və məqsəd, tam ədədin iki gücə sahib olub olmadığını yoxlamaqdır, yəni 'nin bəzi bütün gücü kimi təmsil edilə bilər2".

İki Leetcode həllinin gücüPin

misal

16
Yes
13
No

Yanaşma

Xırda bir həll ola bilər: Tam ədədin bütün əsas amillərinin hamısını yoxlayın '2'. Bu metodun zaman mürəkkəbliyi O olacaqdır (log2N). Bunu optimal şəkildə etmək üçün Bit manipulyasiyalarından kömək ala bilərik.

"İki gücə sahib olan hər hansı bir ədədin ikili təsvirdə yalnız bir bit dəsti ola bilər"

Yalnız bir olduğu necə yoxlanıla bilər tək bit dəsti ikili formada?

Hər hansı bir rəqəmi düşünün, x.

İndi x, ikinin gücünə bərabərdirsə, deməli (x - 1) hamısını söndürəcək sağ bit set bitə (onları '0' olaraq təyin edin) və təyin edilmiş bit ayarlanmayacaq.

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

Beləliklə, istifadə BITWISE-VƏ x və (x - 1) -dən, bir rəqəmin iki gücünə bərabər olduğunu deyə bilərik, onda x & (x - 1) = 0

Alqoritm (əhəmiyyətsiz)

  1. Nömrəni bölməyə davam edin '2' qədər bölünməyincə '2' artıq.
  2. Sayı bərabərdirsə '1':
    • Tam ədəd iki gücdür
  3. Daha
    • Tam ədəd iki güc deyil

Alqoritm (Bit-Manipulyasiya)

  1. X & (x - 1) sıfıra bərabər olub olmadığını yoxlayın
    • Varsa, rəqəm 2-nin gücünə bərabərdir
    • Tamam, əksinə, 2-nin gücü deyil

Həyata keçirilməsi

İki Leetcode Çözümünün C ++ Proqramı

Sadəlövh metod

#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;
}

Optimal metod

#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

İki Leetcode Çözümünün Gücünün Java Proqramı

Sadəlövh metod

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");
    }
}

Optimal metod

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

Mürəkkəblik təhlili

İki Leetcode Həllinin Gücünün Zaman Mürəkkəbliyi

Sadəlövh yanaşmanın zaman mürəkkəbliyi O (log2N)burada N = verilən tam ədəd. Bununla birlikdə, Bitwise-Və daha sürətli olduğu üçün optimal yanaşma daha sürətlidir və bu səbəbdən də zaman mürəkkəbliyinə malikdir O (1).

İki Leetcode həllinin gücünün kosmik mürəkkəbliyi

Proqramda istifadə olunan boşluq yalnız funksiya imzasıdır. Buna görə daimi yer istifadə olunur - O (1).

Crack Sistemi Dizayn Müsahibələri
Translate »
1