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.
Dasturchi, frilanser, gik va introvert
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 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.
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 (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 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 Expression algoritmiga o’tishdan avval NFA – Nondeterministic Finite Automaton abstrakt hisoblash mashinasi haqida tanishib chiqish kerak bo’ladi.
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 uchun yana bir diqqatga molik algoritmlardan biri – Rabin-Karp algoritmi hashing usuliga asoslanadi. Uning ishlash tartibini batafsil tushuntirishga harakat qilaman.
Avvalgi mavzuda o’tganimiz – Knuth-Morris-Pratt algoritmi yordamida biz matn ichida qidiruvni O(N + M) vaqt ichida bajara olamiz. Navbatdagi algoritm – Boyer-Moore algoritmi bizga O(N) ni kafolatlay olmasada, amaliyotda KMPdan samaraliroq ishlaydi. O’rganishga ham osonroq 😉
Matn ichida qidiruv uchun brute-force yondashuvining kamchiligi – pattern’dagi belgilardan biri qidiruvda mos kelmay qolganda, qidiruvni boshqatdan boshlashi kerak. Shuning uchun worst case O(N*M) bo’lib ketadi.