ນັບ Solutions Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ Capital One ກູໂກ Microsoft
ແຮກ ຄະນິດສາດ

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບເລກເຕັມ, N. ເປົ້າ ໝາຍ ແມ່ນການຄິດໄລ່ ຈຳ ນວນນ້ອຍກ່ວາ 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. ດໍາເນີນການ loop ກວດເບິ່ງຕົວເລກທັງຫມົດ, ເລີ່ມຈາກ 3
  3. ໝາຍ ເລກ ໜຶ່ງ, N ແມ່ນ ສຳ ຄັນຖ້າ:
    • ມັນ​ມີ ປັດໄຈຕົ້ນຕໍລະຫວ່າງ 2 ແລະ √N
  4. ຖ້າຫາກວ່າຕົວເລກແມ່ນ ສຳ ຄັນ, ຜົນການເພີ່ມຂື້ນ
  5. ພິມຜົນໄດ້ຮັບ

ການປະຕິບັດການແກ້ໄຂບັນຫາຂອງ Primes 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';
}

ໂຄງການ Java

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

ຄວາມສັບສົນເວລາ

ພວກເຮົາດໍາເນີນການ loop ສໍາລັບ N / 2 ເວລາ. ໃນທຸກໆການກວດກາ, ເວລາທີ່ສັບສົນ O (N / 2) (ໃຊ້ເວລາສະເລ່ຍເທົ່າກັບ N / 2) ໃຊ້ຈ່າຍແລ້ວ. ດັ່ງນັ້ນ, ຄວາມສັບສົນຂອງເວລາຂອງລະບົບ algorithm ນີ້ແມ່ນ O (N√N).

ຄວາມສັບສົນໃນອະວະກາດ

O (1), ມີພຽງແຕ່ພື້ນທີ່ຄົງທີ່ເທົ່ານັ້ນທີ່ໃຊ້ ສຳ ລັບຕົວແປທີ່ຄົງທີ່.

ວິທີການ (ວິທີການທີ່ດີທີ່ສຸດ)

ພິຈາລະນາ ຈຳ ນວນທີ່ ສຳ ຄັນທີ່ສຸດ, ໃຫ້ເວົ້າ 5, ຫຼັງຈາກນັ້ນມັນແນ່ໃຈວ່າຄູນທັງ ໝົດ ຂອງ 5, ນອກ ເໜືອ ຈາກຕົວມັນເອງບໍ່ສາມາດເປັນສິ່ງ ສຳ ຄັນທີ່ພວກເຂົາຈະມີ 5 ເປັນ ໜຶ່ງ ໃນປັດໃຈຫຼັກຂອງພວກມັນ. ເຊັ່ນດຽວກັນ, ພວກເຮົາສາມາດເກັບຮັກສາຕົວເລກທັງ ໝົດ ນ້ອຍກວ່າ N ແລະສູງກວ່າ 0

ໄດ້ Sieve ຂອງ Eratosthenes ເປັນສູດການຄິດໄລ່ແບບບູຮານແລະມີປະສິດທິພາບໃນການຊອກຫາເວລານ້ອຍກວ່າ N ເມື່ອ N ມີຂະ ໜາດ ນ້ອຍພໍໃນການຈັດສັນ O (N) ຊ່ອງໃນຄວາມຊົງ ຈຳ. ມັນລົບລ້າງຕົວເລກທີ່ບໍ່ແມ່ນຕົວເລກທັງ ໝົດ ໂດຍ ໝາຍ ໃສ່ພວກມັນເປັນສ່ວນປະກອບ. ຫຼັງຈາກສ່ວນປະກອບທັງ ໝົດ ຖືກ ໝາຍ ໄວ້, ຕົວເລກທີ່ບໍ່ໄດ້ ໝາຍ ແມ່ນ XNUMX.

ພ້ອມກັນນີ້, ພວກເຮົາ ຈຳ ເປັນຕ້ອງເກັບຮັກສາບາໂວນ array ເພື່ອກວດເບິ່ງວ່າມີເລກໃດທີ່ ໝາຍ ໄວ້ຫຼືບໍ່, ເຊິ່ງບັນຊີ ສຳ ລັບການ ນຳ ໃຊ້ຫນ່ວຍຄວາມ ຈຳ. ດັ່ງນັ້ນ, ນີ້ແມ່ນກໍລະນີທີ່ພວກເຮົາ ຄວາມຊົງ ຈຳ ດ້ານການຄ້າ ໄປ ປັບປຸງໃຫ້ທັນເວລາ.

ນັບ Solutions Leetcode

ລະບົບວິເຄາະ

  1. ຮັກສາອາລູບາ ນາຍົກລັດຖະ ຂອງຂະຫນາດເທົ່າກັບ N - 1
  2. ນາຍົກລັດຖະ [] ຖືກ ນຳ ໃຊ້ເພື່ອ ໝາຍ ເອົາສ່ວນປະກອບແລະກວດສອບ primes ໃນຕອນທ້າຍ
  3. ນາຍົກລັດຖະມົນຕີຂອງທຸກໆເລກເຕັມເປັນ ທີ່ແທ້ຈິງ. ຊຸດສູດການຄິດໄລ່ ທີ່ບໍ່ຖືກຕ້ອງ ທຸກໆ ຈຳ ນວນທີ່ບໍ່ແມ່ນ ສຳ ຄັນ
  4. ດໍາເນີນການ loop ຂອງເລກເຕັມຕິດຕໍ່ກັນ, ເລີ່ມຈາກ 2 ຈົນກ່ວາຕົວຄູນທໍາອິດຂອງຈໍານວນແມ່ນ ຫນ້ອຍກ່ວາ N:
    • ສຳ ລັບເລກເຕັມທຸກ x, ຖ້າວ່າມັນມີຕົວເລກ [x] ເປັນຄວາມຈິງ, ໃຫ້ ໝາຍ ໃສ່ທັງ ໝົດ ຂອງມັນເທົ່າກັບ ທີ່ບໍ່ຖືກຕ້ອງ
    • ຕົວຄູນຂອງທຸກໆເລກເຕັມຢູ່ທີ່ນີ້ເລີ່ມຈາກ x * x ເປັນຕົວຄູນອື່ນໆທັງ ໝົດ ຂອງ x ຈະຖືກ ໝາຍ ໄວ້ແລ້ວ.
  5. ສຸດທ້າຍກວດເບິ່ງວ່າມີຈັກເລກຢູ່ໃນຂອບເຂດ [2, N - 1] ມີ ທີ່ແທ້ຈິງ ໃນຕາຕະລາງທີ່ ສຳ ຄັນ
  6. ພິມຜົນໄດ້ຮັບ

ການປະຕິບັດການແກ້ໄຂບັນຫາຂອງ Primes 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';
}

ໂຄງການ Java

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)

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (N), ດັ່ງທີ່ພວກເຮົາສ້າງຕາຕະລາງ hash ໃນການເກັບຮັກສາຖ້າຫາກວ່າຕົວເລກແມ່ນ ສຳ ຄັນຫຼືບໍ່.