Leetcode 3. Longest Substring Without Repeating Characters
Berilgan matndan belgilari takrorlanmaydigan eng uzun qismni topib, uning uzunligini qaytarish kerak bo’ladi.
Leetcode 2. Add two numbers
Ikki bo’sh bo’lmagan, non-negativ sonlarni taqdim qiluvchi linked list’lar berilgan. Listdagi raqamlar teskari tartibda joylashgan, har bir node bitta raqamdan iborat. Ikki sonni qo’shib, javobini linked list’da qaytaring.
Leetcode 1. Two Sum
Leetcode 1. Sonlardan iborat nums array va yig’indisi target berilgan. target’ni nums array’dagi qaysi sonlarning yig’indisidan iborat ekanligini topib, ularning indeksini array ko’rinishida qaytarishimiz kerak.
Minimum edit distance
Minimum tahrirlash masofasi deb be’mani tarjima qilinadigan minimum edit distance (yoki ixtirochisi sharafiga Levenshtein distance) algoritmi ikki so’z o’rtasidagi farqlar sonini aniqlashga yordam beradi.
Ryukzak masalasi (Knapsack problem)
Bizda har biri vaznga va qiymatga ega bo’lgan turli buyumlar bor. Ryukzakga (yoki biror idishga) solish uchun ularni shunday tanlash kerakki, buyumlar ryukzakning maksimum og’irlik limitidan kichkina yoki teng bo’lsin va solingan buyumlarning umumiy qiymati iloji boricha eng kattasi bo’lsin. Ushbu masala ryukzak masalasi, inglizchada knapsack problem deb ataladi.
Dynamic programming
Dynamic programming (DP, dinamik dasturlash) deb muammoni kichik masalalarga ajratib, ularni faqat bir marta yechish va natijani keyingi bir xil tipdagi masalada ishlatish uchun saqlab turish texnikasiga aytiladi.
NFA simulyatsiyasi va API
NFA simulyatsiyasini ko’rib chiqishdan avval NFAning o’zini kodda qanday ifodalashni ko’rib chiqamiz. Avvalgi maqolada aytib o’tilganidek, NFAda 0 dan M gacha state’lar + accept state mavjud. M – bu yerda qavs ichiga olingan regular expression’dagi belgilar soni. Masalan ((A*B|AC)D) regexp uchun NFA state’lari 11 ta (10ta regexp belgi-state + 1 accept state).
Regular Expressions va Nondeterministic Finite Automaton
Regular Expression algoritmiga o’tishdan avval NFA – Nondeterministic Finite Automaton abstrakt hisoblash mashinasi haqida tanishib chiqish kerak bo’ladi.
Regular expressions
Regular expression (yana regex, regexp) – qidirish patternini belgilab beruvchi belgilar ketma-ketligi. Odatda regex’lar matn ichida qidiruv algoritmlarida so’zlarni topish (find), topish va almashtirish (find & replace), hamda kiritilgan ma’lumotni tekshirish uchun ishlatiladi.
Matn ichida qidiruv. Rabin-Karp algoritmi
Matn ichida qidiruv uchun yana bir diqqatga molik algoritmlardan biri – Rabin-Karp algoritmi hashing usuliga asoslanadi. Uning ishlash tartibini batafsil tushuntirishga harakat qilaman.