WisarWisar
Dasturlash kitobi/3-QISM — Algoritmlar12 daqiqa

3.2-bob: Massiv va String algoritmlari

3-QISM — Algoritm va ma'lumotlar tuzilmasi · 2-mavzu

1. Kirish va motivatsiya

Big-O 3.1-bob o'lchovini bildik; endi uni amalda qo'llaymiz. Massiv 2.7-bob va string 2.6-bob — dasturlashda eng ko'p uchraydigan ma'lumot. Ular ustidagi klassik algoritm naqshlari (ikki ko'rsatkich, sliding window, prefiks yig'indi) — intervyularning va kundalik ishning asosi.

Bu naqshlar — alohida masalalar emas, balki fikrlash shablonlari 0.6-bob. Bittasini o'zlashtirsangiz, yuzlab masalani yechasiz: "ikki ko'rsatkich" — palindrom, juftliklar, saralangan massivni birlashtirish; "sliding window" — eng katta ketma-ketlik, substring masalalari.

O'xshatish: bu naqshlar — duradgorning asosiy harakatlari (arralash, randalash, biriktirish). Har bir mebel boshqacha, lekin asosiy harakatlar bir xil. Algoritm naqshlarini bilsangiz — yangi masala "tanish" ko'rinadi.

Nega muhim?

  • Massiv/string — har bir dasturda (ro'yxat, matn, ma'lumot qayta ishlash).
  • Bu naqshlar O(n²) yechimni ko'pincha O(n) ga tushiradi 3.1-bob.
  • LeetCode/intervyu masalalarining katta qismi shu naqshlarga tayanadi 3.13-bob.

2. Nazariya — chuqur tushuntirish

2.1. Massiv — xotirada qanday yashaydi (0.1)

Massiv — xotirada ketma-ket joylashgan elementlar (0.1: RAM kataklari). Shuning uchun indeks bo'yicha murojaat O(1) — manzil = boshlanish + indeks × element_hajmi (to'g'ridan-to'g'ri hisoblanadi):

text
  Indeks:   0    1    2    3    4
          ┌────┬────┬────┬────┬────┐
  Massiv: │ 10 │ 20 │ 30 │ 40 │ 50 │    ketma-ket xotirada 0.1-bob
          └────┴────┴────┴────┴────┘
  arr[3]  boshlanish + 3 × hajm  DARROV (O(1))

Lekin o'rtaga qo'shish/o'chirish O(n) — qolgan elementlarni surish kerak (3.1 jadvali).

2.2. Ikki ko'rsatkich (two pointers) naqshi

Ikki ko'rsatkich — massiv/stringda ikkita indeks bilan ishlash; ko'pincha O(n²) ni O(n) ga tushiradi:

  • Qarama-qarshi (ends): biri boshdan, biri oxiridan — markazga qarab (palindrom, juftlik).
  • Bir yo'nalishli (fast/slow): ikkalasi boshdan, har xil tezlikda (dublikat o'chirish).
text
  Palindrom tekshirish (qarama-qarshi):
  "k a n o k"
               chap va o'ng taqqoslanadi, markazga yaqinlashadi
   chap    o'ng
js
function palindromMi(s) {
  let chap = 0, ong = s.length - 1;
  while (chap < ong) {
    if (s[chap] !== s[ong]) return false;   // mos kelmasa — palindrom emas
    chap++; ong--;                           // markazga
  }
  return true;
}
// O(n) vaqt, O(1) xotira (3.1)

2.3. Sliding window (suriluvchi oyna) naqshi

Sliding window — uzluksiz ketma-ketlik (subarray/substring) ustida ishlash; "oyna"ni surib, qayta hisoblamasdan yangilash:

text
  Eng katta 3 ta uzluksiz son yig'indisi:
  [2, 1, 5, 1, 3, 2]
   └─────┘             oyna=8 (2+1+5)
      └─────┘          oyna surildi: -2 +1 = 7
         └─────┘       -1 +3 = 9  eng katta
js
function engKattaOyna(arr, k) {
  let oyna = 0;
  for (let i = 0; i < k; i++) oyna += arr[i];   // birinchi oyna
  let max = oyna;
  for (let i = k; i < arr.length; i++) {
    oyna += arr[i] - arr[i - k];   // yangi kel, eski ket (qayta hisoblamasdan!)
    max = Math.max(max, oyna);
  }
  return max;
}
// O(n) — har element bir marta (ichma-ich tsiklsiz — 3.1)

Nega kuchli: har oynani noldan hisoblasak — O(n×k). Surib yangilash — O(n). Bu — qayta hisoblashdan qochish 3.1-bob.

Kadane algoritmi — eng katta yig'indili uzluksiz subarray (oyna kengligi qat'iy emas, o'zgaruvchan). Har bir indeksda savol: "shu elementni oldingi yig'indiga qo'shamizmi yoki undan yangi boshlaymizmi?" Manfiy sonlar bo'lganda ham ishlaydi:

text
  [-2, 1, -3, 4, -1, 2, 1, -5, 4]
                └──────────┘        eng katta yig'indi = 6 (4-1+2+1)
js
function engKattaYigindi(arr) {
  let joriy = arr[0], max = arr[0];   // bo'sh massivni alohida tekshir (0.6)
  for (let i = 1; i < arr.length; i++) {
    joriy = Math.max(arr[i], joriy + arr[i]);   // yangi boshla yoki davom et
    max = Math.max(max, joriy);                 // eng katta yig'indini yangilab bor
  }
  return max;
}
engKattaYigindi([-2, 1, -3, 4, -1, 2, 1, -5, 4]);   // 6 — O(n), O(1) xotira

G'oya: agar oldingi yig'indi manfiy bo'lsa — uni tashlab, shu elementdan yangi boshlash foydaliroq. Bu — DP ning 3.12-bob eng sodda namunalaridan biri.

2.4. Prefiks yig'indi (prefix sum) naqshi

Oldindan yig'indilarni hisoblab saqlash — keyin istalgan oraliq yig'indisini O(1) da olish:

js
function prefiksYigindi(arr) {
  const prefiks = [0];
  for (let i = 0; i < arr.length; i++)
    prefiks[i + 1] = prefiks[i] + arr[i];   // har joygacha yig'indi
  return prefiks;
}
// [3,1,4,1,5]  prefiks [0,3,4,8,9,14]
// oraliq [i..j] yig'indisi = prefiks[j+1] - prefiks[i]   O(1)!

2.5. Hash map bilan tezlashtirish (2.9)

Ko'p massiv masalasi Map/Set bilan O(n²) dan O(n) ga tushadi (3.1, 2.9):

js
// "Two Sum" — yig'indisi target bo'lgan ikki son indeksi
function twoSum(arr, target) {
  const korilgan = new Map();   // qiymat  indeks
  for (let i = 0; i < arr.length; i++) {
    const kerakli = target - arr[i];
    if (korilgan.has(kerakli))           // juftini ko'rganmizmi? O(1) (2.9)
      return [korilgan.get(kerakli), i];
    korilgan.set(arr[i], i);
  }
  return null;
}
// O(n) — Map bilan (ichma-ich tsikl O(n²) o'rniga — 3.1)

2.6. Asosiy massiv amallari (in-place vs yangi)

  • In-place — asl massivni o'zgartirish (O(1) qo'shimcha xotira), lekin mutatsiya 2.7-bob.
  • Yangi massiv — immutable (2.7, 2.15), lekin O(n) xotira.
js
// In-place ag'darish (ikki ko'rsatkich — 2.2)
function agdar(arr) {
  let l = 0, r = arr.length - 1;
  while (l < r) { [arr[l], arr[r]] = [arr[r], arr[l]]; l++; r--; }  // swap (2.8)
  return arr;
}
// Immutable: [...arr].reverse() yoki arr.map(...) (2.7)

2.7. String algoritmlari (2.6)

String — o'zgarmas 2.6-bob, shuning uchun ko'p amal uchun massivga aylantirib ishlanadi:

js
const harflar = [...s];           // yoki s.split("") (2.6)
const tartiblangan = [...s].sort().join("");   // string saralash (2.6, 2.7)

Klassik string masalalari: palindrom 2.2-bob, anagram (harf sanog'i), substring qidirish, belgi chastotasi (Map — 2.9).

js
// Anagram tekshirish — harf chastotasi (Map — 2.9)
function anagramMi(a, b) {
  if (a.length !== b.length) return false;   // chegaraviy holat (0.6)
  const sanoq = {};
  for (const ch of a) sanoq[ch] = (sanoq[ch] || 0) + 1;
  for (const ch of b) {
    if (!sanoq[ch]) return false;
    sanoq[ch]--;
  }
  return true;
}
// O(n) — chastotani Map'da sanash (saralash O(n log n) o'rniga)

3. Asosiy naqshlar — tez ma'lumotnoma

text
IKKI KO'RSATKICH   — palindrom, juftlik, saralangan birlashtirish (O(n))
SLIDING WINDOW     — uzluksiz subarray/substring (O(n))
KADANE             — eng katta yig'indili uzluksiz subarray (O(n))
PREFIX SUM         — oraliq yig'indilari (hisob O(n), so'rov O(1))
HASH MAP/SET       — qidiruv/dublikat/chastota O(n) ga tushirish 2.9-bob
IN-PLACE SWAP      — ag'darish/tartiblash O(1) xotira

4. Batafsil kod namunalari

Misol 1 — Ikki ko'rsatkich: saralangan massivda juftlik (2.2)

js
// Saralangan massivda yig'indisi target bo'lgan juftlik
function juftlikTopib(arr, target) {
  let l = 0, r = arr.length - 1;       // qarama-qarshi (2.2)
  while (l < r) {
    const yigindi = arr[l] + arr[r];
    if (yigindi === target) return [arr[l], arr[r]];
    yigindi < target ? l++ : r--;      // kichik bo'lsa chapni surib, katta bo'lsa o'ngni
  }
  return null;
}
juftlikTopib([1, 3, 5, 7, 9], 12);   // [3, 9] — O(n), O(1) xotira

Misol 2 — Sliding window: takrorsiz eng uzun substring (2.3)

js
function engUzunTakrorsiz(s) {
  const korilgan = new Set();   // oynadagi belgilar (2.9)
  let chap = 0, max = 0;
  for (let ong = 0; ong < s.length; ong++) {
    while (korilgan.has(s[ong])) {     // takror bo'lsa — chapni surib torayt
      korilgan.delete(s[chap]); chap++;
    }
    korilgan.add(s[ong]);
    max = Math.max(max, ong - chap + 1);   // oyna kengligi
  }
  return max;
}
engUzunTakrorsiz("abcabcbb");   // 3 ("abc") — O(n)

Misol 3 — Hash map: chastota va eng ko'p uchragan (2.5, 2.9)

js
function engKopUchragan(arr) {
  const sanoq = new Map();
  for (const x of arr)
    sanoq.set(x, (sanoq.get(x) || 0) + 1);   // chastota (2.9)

  let max = null, maxSon = 0;
  for (const [qiymat, son] of sanoq)          // eng ko'rini top
    if (son > maxSon) { max = qiymat; maxSon = son; }
  return max;
}
engKopUchragan([1, 3, 1, 3, 1]);   // 1 — O(n)

Misol 4 — In-place: noldan keyin surish (2.6)

js
// Barcha 0 larni oxiriga surish (in-place, tartibni saqlab)
function nollarniSur(arr) {
  let yoz = 0;                          // nol bo'lmaganlarni yozish indeksi
  for (let i = 0; i < arr.length; i++)
    if (arr[i] !== 0) arr[yoz++] = arr[i];   // nol bo'lmaganni oldinga
  while (yoz < arr.length) arr[yoz++] = 0;   // qolganini nol bilan to'ldir
  return arr;
}
nollarniSur([0, 1, 0, 3, 12]);   // [1, 3, 12, 0, 0] — O(n), O(1) xotira

5. To'g'ri va noto'g'ri holatlar

1) Ichma-ich tsikl (naqsh o'rniga)

js
//  O(n²) — har juftlikni tekshirish (3.1)
for (let i = 0; i < arr.length; i++)
  for (let j = i + 1; j < arr.length; j++)
    if (arr[i] + arr[j] === target) return [i, j];

//  O(n) — hash map (2.5)
const m = new Map();
for (let i = 0; i < arr.length; i++) {
  if (m.has(target - arr[i])) return [m.get(target - arr[i]), i];
  m.set(arr[i], i);
}

2) Stringni tsiklda += bilan qurish (katta hajmda)

js
//  string o'zgarmas — har += yangi string (sekin — 2.6)
let r = "";
for (const ch of s) r += ch.toUpperCase();

//  massivga yig'ib, join (2.7)
const r = [...s].map(ch => ch.toUpperCase()).join("");

3) Sliding window'ni har safar noldan hisoblash

js
//  O(n×k) — har oynani qayta yig'ish
//  surib yangilash: +yangi -eski (O(n) — 2.3)
oyna += arr[i] - arr[i - k];

4) Chegaraviy holatlarni unutish (0.6)

js
//  bo'sh massiv, bitta element, uzunlik teng emas — tekshirilmagan
//  boshida tekshir
if (arr.length === 0) return null;
if (a.length !== b.length) return false;   // anagram (2.7)

6. Keng tarqalgan xatolar va yechimlari

Xato 1 — Off-by-one (chegara xatosi)

Sababi: < vs <=, indeks chegarasi (0.6, 2.2). Yechimi: qo'lda kichik misolda tekshiring; ikki ko'rsatkichda while (l < r) (teng bo'lganda to'xtaydi).

Xato 2 — undefined element (chegaradan tashqari)

Sababi: arr[i] mavjud bo'lmagan indeks 2.7-bob. Yechimi: indeks arr.length ichida ekanini tekshiring; sliding window'da i - k >= 0.

Xato 3 — String'ni massiv kabi o'zgartirish

js
s[0] = "X";   //  ishlamaydi — string o'zgarmas (2.6)

Sababi: string immutable 2.6-bob. Yechimi: [...s] (massivga), o'zgartiring, join 2.7-bob.

Xato 4 — Katta nda O(n²) muzlash

Sababi: ichma-ich tsikl 3.1-bob. Yechimi: ikki ko'rsatkich/sliding window/hash map naqshi (3-bo'lim).

Xato 5 — Mutatsiya kutilmagan natija

Sababi: in-place algoritm asl massivni o'zgartirdi 2.7-bob. Yechimi: nusxa kerak bo'lsa [...arr]; ataylab in-place bo'lsa hujjatlang.

7. Integratsiya — bu mavzu stack'ning qayerida uchraydi

  • Big-O 3.1-bob: bu naqshlar O(n²) ni O(n) ga tushiradi.
  • Array/String/Map/Set (2.6, 2.7, 2.9): asosiy vositalar.
  • Saralash/qidiruv (3.9, 3.10): ko'p naqsh saralangan massivga tayanadi.
  • Masala yechish 3.13-bob: LeetCode masalalarining asosi shu naqshlar.
  • Backend ma'lumot qayta ishlash (5, 6): DB natijalarini filtrlash/tahlil.
  • DP 3.12-bob: prefiks yig'indi DP ning kirishi.

8. Eng yaxshi amaliyotlar (best practices)

  • Naqshni taning: uzluksiz oraliq sliding window; saralangan/juftlik ikki ko'rsatkich; qidiruv/dublikat hash map.
  • Avval Big-O ni o'ylang 3.1-bob — ichma-ich tsikldan qoching.
  • Chegaraviy holatlarni boshida tekshiring 0.6-bob: bo'sh, bitta, teng emas.
  • String uchun massivga aylantiring ([...s]), tsiklda += qilmang 2.6-bob.
  • In-place vs immutable ni ongli tanlang 2.7-bob.
  • Qo'lda kichik misolda yuring 0.6-bob — off-by-one'ni topadi.
  • Hash map — eng kuchli qurol ko'p massiv masalasida 2.9-bob.

9. Amaliy loyiha: "Algoritm Naqshlari To'plami"

Massiv/string naqshlarini amalda mustahkamlovchi masalalar to'plami.

Maqsad

Ikki ko'rsatkich, sliding window, prefiks yig'indi va hash map naqshlarini qo'llab, har masala uchun Big-O ni aniqlash 3.1-bob.

Talablar (requirements)

Har masala uchun: pseudokod 0.6-bob, yechim, Big-O tahlili, chegaraviy holatlar:

  1. Palindrom (ikki ko'rsatkich — 2.2): bo'sh/bitta belgi, bo'shliq/registr.
  2. Two Sum (hash map — 2.5): juftlik yo'q holat.
  3. Eng uzun takrorsiz substring (sliding window — Misol 2).
  4. Anagram (chastota — 2.7): uzunlik teng emas.
  5. Eng katta k-uzunlikdagi yig'indi (sliding window — 2.3).
  6. Eng katta yig'indili subarray (Kadane — 2.3): manfiy sonli holat.
  7. Oraliq yig'indisi (prefiks sum — 2.4): bir nechta so'rov.
  8. Nollarni surish (in-place — Misol 4).
  9. Eng ko'p uchragan element (Map — Misol 3).
  10. Har yechim uchun O(n²) "sodda" versiya bilan solishtiring (qaysi tezroq va nega).

Maslahatlar (hint)

  • Avval pseudokod, keyin kod 0.6-bob.
  • Ikki ko'rsatkich: while (l < r); sliding window: Set/yig'indi yangilash.
  • Two Sum/anagram: Map/object chastota 2.9-bob.
  • Chegaraviy holatlarni boshida 0.6-bob.
  • Har masala uchun "n 10x vaqt necha barobar?" 3.1-bob.

"Tayyor" mezonlari (acceptance criteria)

  • 9 masala ishlaydi, har biri pseudokod bilan.
  • To'g'ri naqsh ishlatilgan (ikki ko'rsatkich/window/hash map).
  • Har yechim O(n) yoki O(n log n) (sodda O(n²) emas).
  • Chegaraviy holatlar tekshirilgan.
  • Big-O tahlili har masala uchun yozilgan.
  • In-place masala asl massivni to'g'ri o'zgartiradi.

Yechim kodi ataylab berilmagan — bu loyihani o'zingiz yozib ko'ring.

10. Xulosa va keyingi bobga ko'prik

Bu bobda massiv va string ustidagi klassik algoritm naqshlarini o'rgandik:

  • Massiv — xotirada ketma-ket 0.1-bob; indeks O(1), o'rta qo'shish/o'chirish O(n).
  • Ikki ko'rsatkich — qarama-qarshi yoki fast/slow; palindrom, juftlik (O(n), O(1) xotira).
  • Sliding window — uzluksiz oraliq; surib yangilash (qayta hisoblamasdan, O(n)).
  • Kadane — eng katta yig'indili subarray; manfiy sonli holatda ham O(n).
  • Prefiks yig'indi — oraliq so'rovlari O(1).
  • Hash map/set 2.9-bob — qidiruv/dublikat/chastotani O(n) ga tushiradi.
  • Best: naqshni taning, Big-O ni o'ylang, chegaraviy holatlarni tekshiring.

Keyingi bob — 3.3-bob: Linked List. Massiv — ketma-ket xotira (indeks tez, o'rta o'zgartirish sekin). Linked List — boshqa yondashuv: elementlar xotirada tarqoq, lekin "ko'rsatkich" bilan bog'langan; bosh/o'rtaga qo'shish/o'chirish O(1). Bu — birinchi "ko'rsatkichli" ma'lumotlar tuzilmasi.

Foydalanilgan rasmiy/ishonchli manbalar

  • bigocheatsheet.com — massiv operatsiyalari murakkabligi
  • MDN Web Docs — Array, String metodlari (2.6, 2.7)
  • Universal CS — two pointers, sliding window, prefix sum naqshlari

Izohlar (0)

Izoh yozish uchun kiring.

  • Hozircha izoh yo'q. Birinchi bo'ling!
3.2-bob: Massiv va String algoritmlari — Wisar