LeetCodin

LeetCode Rewind 2024

@LeetCodin

Hammaga salom!

Kuni kecha Tizimlar dizayni (System Design) kursini sotib oldim.

Uning muallifi Mikhail Smarshchok, staff muhandisi sifatida faoliyat yuritadi. Menga uning YouTube’dagi 5 ta video darslikdan iborat kichik kursi juda yoqqan edi. U mavzularni juda aniq va tushunarli tarzda tushuntiradi.

Aytishadiku, “chaynab og’zimga solib qo’ygan” deb. Bu odam ham xuddi shunday tushuntirar ekan. Eng qizig’i, videolarning tavsiflarida u o’zining to’liq kursiga havola qoldirgan ekan. Va bu kurs, tasavvur qiling-a, LeetCode’da joylashgan ekan.

Men shu vaqtning o’zida:


@LeetCodin

23-noyabrgacha tekin Ma’lumot tuzilmalari va Algoritmlar haqida kurs tayyorlashgan ekan. Juda ham yaxshi chiqibdi. Ingliz tilida.

https://www.jointaro.com/course/crash-course-data-structures-and-algorithms-concepts/course-welcome/

@LeetCodin

Today is the 300th day of the year.

Bugun yilning 300-kuni ekan.

@LeetCodin

🇺🇿
Menga yordamingiz kerak bo’lmoqda:

Qaysi mavzular haqida postlar yozishimni xohlaysiz?

🇺🇸
I need your help:

What topics do you want me to cover in future posts?

Agar narsalarni tartiblashda qiynalayotgan bo'lsangiz, bu 6 ta tartiblash algoritmidan foydalanib ko'ring:

1. Bubble tartiblash usuli. O(N ^ 2).

2. Selection tartiblash usuli. O(N ^ 2).

3. Kiritish orqali tartiblash usuli. O(N ^ 2).

4. Birlashtirish orqali tartiblash usuli. O(N * logN).

5. Tez tartiblash usuli. O(N * logN) dan O(N ^ 2) gacha.

6. Shell tartiblash usuli. O'rtacha - O(N ^ (3/2)).

@LeetCodin

Shell saralash algoritmi.

Salom! Bugun yangi Shell saralash algoritmini ko'rib chiqaman.

😇 Github: ShellSort
⏰ Time complexity:
O'rtacha - O(N ^ (3/2)),
Eng yomon holatda - O(N ^ 2)
🔎 Space complexity: O(1)

🧑‍💻 G'oya 🧑‍💻

Shell sort, uni 1959-yilda kashf etgan, Donald L. Shell-dan nomini olgan. Shell sort Kiritish orqali saralash usulining asosida ishlaydi. Kiritish orqali saralash algoritmida siz elementlarni faqat bir pozitsiyaga sura olasiz. Agar element massivning oxiridan boshiga joylashtirilishi kerak bo'lsa, siz ko'p swap operatsiyasini bajarasiz.

Shell sort algoritmining g'oyasi - bu uzoq masofada joylashgan elementlarni saralash. Bu algoritm orqali siz elementlarni h uzoqlikda saralangan qilasiz. Shu h-ning qiymati 1ga teng bo'lmagunicha uni kamaytiraverasiz. h uzoqlikda saralangan degani bir biridan h uzoqlikda joylashgan elementlarning har bir ro'yxatda saralangan holatda bo'lishi.

🧑‍💻 Algoritm 🧑‍💻

h = h * 3 + 1 -> bu Knuth-ning Interval ketma-ketliklar uchun formulasi.

1. Birinchi while loop berilgan massiv hajmi uchun to'g'ri h-ni topish uchun ishlatasiz.

2. Keyin esa nested loop ishlatasiz.
- Birinchi tashqi while loop-ni h-ning qiymatini formula bo'yicha kamaytirish uchun ishlatasiz.
- Ichki for loop-da esa Kiritish orqali saralash [Insertion sort] algoritmini h uzoqlikda joylashgan elementlar uchun ishlatasiz.
- Ichki while loop Kiritish orqali saralashga o'xshab, h uzoqlikda joylashgan elementlar uchun katta elementlarni o'nga suradi va tanlangan elementni o'z joyiga qo'yadi.

Manbalar:
1. Data Structures and Algorithms in Java. R. Lafore.
2. Geeksforgeeks
3. GIF

Rahmat!
Omad! ✌️😎

@LeetCodin

Tez Tartiblash. Tartiblash algoritmlari.

Salom! Bugun ham katta mavzu - Tez tartiblash [Quick sort].

😇 Github: QuickSort
⏰ Time complexity:
Eng yaxshi holat: O(N * logN),
Eng yomon holat: O(N ^ 2).
🔎 Space complexity: O(1).

🧑‍💻 G'oya 🧑‍💻

Quick sort bu tezligi kvadrat funksiyaga ega bo'lgan tartiblash algoritmlardan [Bubble sort, Selection sort, and Insertion sort] ancha tezroq ishlaydigan algoritm (o'rta holatda).

Bu algoritm uchta qismdan iborat:
- Massivni yoki uning qismini ikki qismga bo'lish. Chap qismida asos qilib olingan sondan kichikroq va o'ng qismida shu sondan kattaroq elementlar joylashtiriladi.
- Huddi shu metodni rekursiv chaqiruv orqali chap qism uchun ishlatish.
- Shu metodni rekursiv chaqiruv orqali bu safar o'ng qism uchun ishlatish.

Massivni kichikroq qismlarga bo'lish deganda massivni ikkita guruhga asos (tayanch) qilib oningan songa qarshi bo'lishni tushunish kerak. Shunda chap guruhdagi sonlar tayanch sondan kichikroq va o'ng guruhdagi sonlar esa shu tayanch sonidan kattaroq bo'lishi lozim.

🧑‍💻 Algoritm 🧑‍💻

Tepada Github-dagi yechimga havola qoldirganman.
Shu yechimda hamma logic QuickSort klassining ichida. Bu klassda array massivi bor. U tartiblash uchun berilgan massivga ko'rsatgichni saqlaydi.
QuickSort klassida yana 4 metod bor. Bular quickSort(), recursiveQuickSort(), partitionIt() va swap().

👩‍💻 quickSort()
Klassga tegishli massiv o'zgaruvchisiga berilgan massivni yozib qo'yadi. Keyin esa recursiveQuickSort() rekursiv metodini 0 va oxirgi indekslar uchun chaqiradi.

👩‍💻 recursiveQuickSort()
- Boshida rekursiya uchun asosiy holat tekshiriladi.
- else blokining ichida quyidagi 4ta harakat bajariladi:
1. Tayanch sonini tanlaysiz. Buning uchun berilgan diapazondan oxirgi elementni tanlaysiz.
2. partitionIt() metodini chaqirish orqali shu tayanch sonining indeksi aniqlanadi. Bu metod tayanchdan kichik sonlarni chapga va kattaroq sonlarni o'nga joylashtiradi.
3. Keyin rekursiv chaqiruv orqali recursiveQuickSort() metodini chap guruh uchun chaqirasiz.
4. Bundan keyin rekursiv chaqiruv orqali recursiveQuickSort() metodini o'ng guruh uchun chaqirasiz.

👩‍💻 partitionIt()
Metodning boshlanishida berilgan diapazon [left - right] ichida bosh va oxirgi indekslar uchun alohida int o'zgaruvchilarini yaratasiz.
Bulardan keyin bitta tashqi va ikkita ichki while loop-lar joylashgan.
- Birinchi ichki while loop tayanch sondan katta bo'lgan birinchi sonning indeksini topib beradi.
- Ikkinchi ichki while loop esa tayanch sondan kichik bo'lgan oxirgi sonning indeksini topadi.
- Agar shu ikkita indeks teng bo'lsa yoki leftPointer rightPointer-dan kattaroq bo'lsa, unda berilgan diapazondagi sonlar tayanch songa nisbatan to'g'ri taqsimlangan. Bu holatda tashqi loop-dan chiqib ketiladi.
- Agar chap ko'rsatgich indeks o'ng ko'rsatgich indeksdan kichik bo'lsa, biz shu indeks ostida joylashgan elementlarning swap() orqali joylarini almashtiramiz.
Bu harakatlar orqali siz tayanch sondan kichik sonlarni chapga va undan katta sonlarni unga nisbatan o'nga joylashtirasiz.

Tashqi while loop-dan chiqqaningizda swap() orqali tayanch sonini o'z o'rniga qo'yasiz.
Oxirida esa shu sonning indeksini qaytarasiz.

👩‍💻 swap()
Bu oddiy ikkita elementni indekslari bo'yicha joylarini almashtiruvchi metod.

Manbalar:
1. Data Structures and Algorithms in Java. R. Lafore.
2. Quick Sort in 4 minutes
3. Quick Sort gif

Bugunga shu.
Agar xatolar topsangiz yoki qaysidir qism bo'yicha savollaringiz bo'lsa, comments-da yozing.

Omad! ✌️😎

@LeetCodin

Merge sort. Birlashtirish orqali massivni tartiblash.

Salom! Bugun ancha qiyinroq mavzu - Birlashtirish orqali massivni tartiblash. Keling birgalashib, massivni tartibga solib qo'yamiz. 😁😄😁

😇 Github: MergeSort
⏰ Time complexity: O(N * logN)
🔎 Space complexity: O(N)

🧑‍💻 G'oya 🧑‍💻

Birlashtirish orqali massivni tartiblash algoritmi berilgan massivni kichikroq massivlarga bo'lish va har bir kichik massivni tartiblash, keyin shu tartiblangan kichik massivlardan katta massivni birlashtirish orqali ishlaydi.

Boshqa so'z bilan aytganda, siz berilgan massivni ikkita teng massivga bo'lasiz, har birini tartiblaysiz va keyin ularni bir qayta birlashtirasiz. Bu jarayonni to'la massiv tartibga solingani qadar bajarasiz.

Nimaga bu algoritm zo'r? Chunki uning tezligi boshqa o'tilgan algoritmlardan [Bubble tartiblash, Selection tartiblash va Kiritish orqali tartiblash] ancha tezroq. Chiziqli funksiya logarifmlik funksiyaga ko'paytirilgan funksiyani kvadrat funksiya bilan taqqoslashtiring.

🧑‍💻 Algorithm 🧑‍💻

Agar code-ga qarasangiz, siz 3ta metodni ko'rasiz. Bular mergeSort(), recursiveMergeSort() va merge().

Ahamiyat bering: Men ishlatgan usulda yangi kichik massivlarni yaratilmaydi. Buning o'rniga bitta uzunligi teng massiv yaratiladi va u elementlarni vaqtincha saqlab turish uchun ishlatiladi. Bunga elementlarning indekslarini chegaralar sifatida ishlatilish orqali erishiladi.

👩‍💻 mergeSort():
- workSpace massivini elementlarni vaqtincha saqlash uchun ishlatasiz.
- recursiveMergeSort() metodini chaqirasiz va unga parametrlar sifatida workSpace, chap chegara va o'ng chegaralarni berib yuborasiz.

👩‍💻 recursiveMergeSort():
Bu metod berilgan massivni teng qismlarga bo'lib chiqish va keyin ularni ulash uchun ishlatiladi.
- Agar chap va o'ng chegaralar teng bo'lsa, metod hozirgi bajarilishini to'xtatasiz.
- Aksincha massivning o'rta indeksini topasiz. Bundan so'ng rekursiv tarzda shu metodni chap qism va o'ng qism uchun bajarasiz. Keyin esa ikkita qism birlashtiriladi.

👩‍💻 merge():
Bu metod ikkita (yarim) qismni birlashtirish uchun ishlatiladi.

- Sizda chap chegara va chap chegara yana alohida ko'rsatgich bo'ladi. Chap chegara ko'rsatgichi bu vaqtincha massivga chap tarafdan qo'shiladigan elementning ko'rsatgichidir. Sizda yana o'ng chegara va o'ng qismning boshini ko'rsatuvchi o'zgaruvchi bo'ladi. Bular o'ng tarafda qo'shiladigan elementlarning chegaralarni ko'rsatuvchi sonlar.

- Birinchi while loop ichida siz ikkita qismdan eng kichik elementdan boshlab, eng katta elementgacha workSpace massiviga kiritib chiqasiz.

- Ikkinchi while loop ichida chap qismdan qolib ketgan elementlarni workSpace-ga qo'shib chiqasiz.

- Uchinchi while loop ichida esa o'ng qismdan qolib ketgan elementlarni workSpace-ga qo'shib chiqasiz.

- for loop ichida biz merge() metodining hozirgi bajarilishida tartiblangan elementlarni berilgan massivga yozib qo'yamiz.

☝️ Manbalar:
1. Data Structures and Algorithms in Java. R. Lafore.
2. Geeksforgeeks
3. Wikipedia

Bugunga shu.
Agar qaysidir qism bo'yicha savollaringiz bo'lsa, comments-da yozing.

Omad! ✌️😎

@LeetCodin

Insertion Sort
[Kiritish orqali tartiblash usuli]

Salom! Bugun kiritish orqali tartiblash usulini ko'rib chiqaman.

😇 Github: Insertion sort
⏰ Time complexity: O(N ^ 2)
🔎 Space complexity: O(1)

🧑‍💻 Izoh 🧑‍💻

1. 🧐 Indeksi 1ga teng bo'lgan elementdan boshlaysiz. Bu elementning qiymatini temp [vaqtincha] o'zgaruvchisiga saqlaysiz.

2. 🧐 Temp-dan chapda turgan va undan katta bo'lgan elementlarni o'ngga surasiz.

3. 🧐 temp-ni surilgan elementlarning boshiga kiritasiz.

3. ✅ Shu harakatlarni indeks berilgan massivning uzunligiga teng bo'lmagunicha takrorlaysiz.

Manbalar:
1. Insertion Sort

Omad! ✌️😎

@LeetCodin

🇺🇿 Selection tartiblash usuli.

Salom! Bugun tartiblash algoritmlar mavzusini davom etaman. Selection sort-ni ko'rib chiqaman.

😇 Github: Selection sort
⏰ Time complexity: O(N ^ 2)
🔎 Space complexity: O(1)

🧑‍💻 Izoh 🧑‍💻
1. Massivda eng kichik elementni topasiz 🧐 va uni 1-pozitsiya ostida turgan element bilan joylarini almashtirasiz.

2. Endi massivni keyingi elementdan [2, n] boshlab aylanib, eng kichik elementni topib 🧐, uni 2-pozitsiyada turgan element bilan joylarini almashtirasiz. Bundan so'ng bizda ikkita o'sish tartibda joylashgan element bo'ladi.

3. ✅ Massivni oxirgacha tartiblash uchun bu harakatlarni n-1 marta takrorlaysiz.

Manbalar:
1. Selection sort in C

Omad! ✌️😎

@LeetCodin

🇺🇿 Bubble tartiblash usuli.

🐙 Github: BubbleSort
🕙 Time complexity: O (N ^ 2)

👨‍💻 Izoh
1. 0 indeksli elementdan boshlaysiz. Shu elementni keyingi element bilan solishtirasiz. Agar arr[0] > arr[1] bo'lsa, joylarini almashirasiz. Endi keyingi indeksga o'tib, arr[1] va arr[2] solishtirasiz. Agar arr[1] > arr[2] bo'lsa, joylarini almashtirasiz. Shu harakatlarni massivning oxirigacha bajarasiz. Natijada, eng katta element massivning oxirgi indeksida joylashgan bo'ladi. Shu jarayon pass deyiladi. Birinchi pass-da, biz 0-dan n-1 indeksli elementlarni tekshirib chiqasiz.

2. Tepadagi harakatlarni qaytarasiz, lekin bu safar faqat 0-dan n-2-gacha indekslarga ega bo'lgan elementlar uchun, chunki oxirgi arr[n-1] element o'z joyida joylashgan. Bu bosqichdan keyin ikkita eng katta element massivning oxirigi ikkita indeks ostida joylashadi.

3. Bu jarayonni n-1 marta qaytarasiz.

Manbalar:
1. Bubble sort in C

Omad! ✌️🤓

My LeetCode Journey:
From 1 to 1000 Problems Solved

@LeetCodin