راه حل های کد Leet را بشمارید


سطح دشواری ساده
اغلب در آمازون سیب یکی از سرمایه گوگل مایکروسافت
هشی کردن ریاضی

در این مسئله ، یک عدد صحیح به ما داده می شود. هدف این است که تعداد اعداد کمتر از N را اعداد اول حساب کنیم. عدد صحیح منفی است.

مثال

7
3
10
4

توضیح

اعداد اول کمتر از 10 ، 2 ، 3 ، 5 و 7 است. بنابراین ، تعداد 4 است.

رویکرد (نیروی بی رحم)

روش کلی این است که برای هر عدد صحیح کمتر از N بررسی شود و اگر اول هستند ، نتیجه را افزایش می دهیم. به عنوان مثال ، N = 10 را در نظر بگیرید. حال ، می توانیم از 2 به N - 1 بررسی کنیم تا ببینیم چند عدد اول در این محدوده وجود دارد. اما ، این روش نیاز به بررسی اصلی در کل طیف دارد ، [2 ، N - 1].  بنابراین ، این کند است.

ما می توانیم برخی از بهینه سازی ها را انجام دهیم:

  1. هر عدد اول غیر از 2 یک عدد صحیح است. بنابراین ، پس از 2, ما فقط می توانیم از نظر عدد صحیح فرد بررسی کنیم.
  2. می توانیم بررسی کنیم که آیا عدد در اول است O (√N) زمان برای بهبود الگوریتم.

با این حال ، ما هنوز روش بهتری داریم که بعداً در این مقاله مورد بحث قرار گرفت.

الگوریتم

  1. اگر تعداد کمتر از باشد 3، برگشت 0, همانطور که 2 کوچکترین پرایم است
  2. یک حلقه را برای بررسی همه اعداد ، از 3 شروع کنید
  3. یک عدد ، N اول است اگر:
    • است عوامل اصلی بین 2 و √N
  4. اگر عدد اول است ، نتیجه را افزایش دهید
  5. نتیجه را چاپ کنید

پیاده سازی راه حل های کد اولیه Leetcode

برنامه C ++

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

bool isPrime(int N)
{
    for(int i = 2 ; i * i <= N ; i++)
        if(N % i == 0)
            return false;
    return true;
}


int countPrimes(int N)
{
    if(N < 3)
        return 0;
    int cnt = 1;
    for(int i = 3 ; i < N ; i += 2)
        if(isPrime(i))
            cnt++;

    return cnt;
}


int main()
{
    int N = 10;
    cout << countPrimes(N) << '\n';
}

برنامه جاوا

class count_primes
{
    static boolean isPrime(int N)
    {
        for(int i = 2 ; i * i <= N ; i++)
            if(N % i == 0)
                return false;

        return true;
    }

    static int countPrimes(int N)
    {
        if(N < 3)
            return 0;
        int cnt = 1;//since number is atleast 3, 2 is a prime less than N
        for(int i = 3 ; i < N ; i += 2)
            if(isPrime(i))
                cnt++;
        return cnt;
    }

    public static void main(String args[])
    {
        int N = 10;
        System.out.println(countPrimes(N));
    }
}

4

تجزیه و تحلیل پیچیدگی تعداد محلول های Leetcode تعداد اولیه

پیچیدگی زمان

ما یک حلقه برای اجرا می کنیم N / 2 بار. در هر چک ، زمان پیچیدگی O (N / 2) (با میانگین به عنوان N / 2) خرج می شود بنابراین ، پیچیدگی زمانی این الگوریتم است O (N√N)

پیچیدگی فضا

O (1)، فقط فضای ثابت برای متغیرهای ثابت استفاده می شود.

رویکرد (روش بهینه)

بگذارید هر عدد اول را در نظر بگیرید 5, پس مطمئن است که همه مضربهای 5 ، غیر از خودش هرگز نمیتوانند برتر باشند زیرا آنها 5 را به عنوان یکی از عوامل اصلی خود دارند. به همین ترتیب ، می توانیم تمام اعداد را کمتر از N و بزرگتر از آن ذخیره کنیم 0

La غربال اراتوستن الگوریتمی باستانی و کارآمد برای یافتن اعداد اول کمتر از N است N به اندازه کافی کوچک است تا بتواند O (N) را اختصاص دهد فضای حافظه با علامت گذاری ترکیبی ، تمام اعداد غیر اول را به طور تکراری از بین می برد. پس از علامت گذاری تمام کامپوزیت ها ، اعدادی که علامت گذاری نشده اند ، اولین ها هستند.

همچنین ، ما باید یک بولین را ذخیره کنیم صف برای بررسی اینکه آیا عددی علامت گذاری شده است یا خیر ، که استفاده از حافظه را تأمین می کند. بنابراین ، این موردی است که ما در آن هستیم حافظه تجاری خاموش به به موقع پیشرفت کنید.

راه حل های کد Leet را بشمارید

الگوریتم

  1. یک آرایه بولی را حفظ کنید نخست از اندازه برابر است با N - 1
  2. نخست [] برای علامت گذاری کامپوزیت ها و بررسی اعداد اول در انتها استفاده می شود
  3. مقدار اولیه هر عدد صحیح را به صورت اولیه بدست آورید درست. مجموعه های الگوریتم غلط به هر عدد غیر اول
  4. یک حلقه از اعداد صحیح متوالی را اجرا کنید ، از 2 شروع کنید تا اولین مضرب عدد صحیح است کمتر از N:
    • برای هر عدد صحیح x ، اگر حرف [x] صحیح دارد ، تمام مضرب آن را به صورت علامت گذاری کنید غلط
    • مضرب هر عدد صحیح در اینجا از شروع می شود x * x زیرا سایر مضربهای x دیگر علامت گذاری نخواهند شد.
  5. در آخر بررسی کنید که چند عدد در محدوده [2 ، N - 1] وجود دارد درست در جدول اول
  6. نتیجه را چاپ کنید

پیاده سازی راه حل های کد اولیه Leetcode

برنامه C ++

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

int sieve(int N)
{
    if(N < 3)
        return 0;

    int cnt = 0;
    bool prime[N];
    for(int i = 2 ; i < N ; i++)
        prime[i] = true;

    for(int i = 2 ; i * i < N ; i++)
    {
        if(prime[i])
            for(int j = i * i ; j < N ; j += i)
                prime[j] = false;
    }

    for(int i = 2 ; i < N ; i++)
        if(prime[i])
            cnt++;

    return cnt;
}

int countPrimes(int N)
{
    if(N < 3)
        return 0;
    return sieve(N);
}


int main()
{
    int N = 10;
    cout << countPrimes(N) << '\n';
}

برنامه جاوا

class count_primes
{
    static int sieve(int N)
    {
        if(N < 3)
            return 0;

        int cnt = 0;
        boolean[] prime= new boolean[N];
        for(int i = 2 ; i < N ; i++)
            prime[i] = true;

        for(int i = 2 ; i * i < N ; i++)
        {
            if(prime[i])
                for(int j = i * i ; j < N ; j += i)
                    prime[j] = false;
        }

        for(int i = 2 ; i < N ; i++)
            if(prime[i])
                cnt++;

        return cnt;
    }

    static int countPrimes(int N)
    {
        if(N < 3)
            return 0;
        return sieve(N);
    }

    public static void main(String args[])
    {
        int N = 10;
        System.out.println(countPrimes(N));
    }
}

4

تجزیه و تحلیل پیچیدگی تعداد محلول های Leetcode تعداد اولیه

پیچیدگی زمان

پیچیدگی الگوریتم است O (Nlog (logN)). این را می توان به عنوان زیر ثابت کرد:

برای هر عدد صحیح ، X ، ما زمانی را صرف می کنیم N / X از بین بردن تمام مضرب های آن.

بنابراین ، زمان صرف شده در کل: N / 2 + N / 3 + N / 5 + N / 7 +

مصرف N به عنوان معمول ، T (N) = N (1/2 + 1/3 + 1/5 + 1/7 +…). مجموع مجموعه ها (1/2 + 1/3 + 1/5 + 1/7 +…) را می توان به عنوان ثابت کرد log (logN)

از این رو، T (N) = Nlog (logN)

پیچیدگی فضا

بر)، همانطور که ما یک جدول هش ایجاد می کنیم تا اگر عدد اول است یا نه ، ذخیره شود.