WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

Leetcode 6. Zigzag Conversion

"PAYPALIŞIRING" matni berilgan qatorlar soni böyiça zigzag körinişida yozilgan. Uni qatorma-qator öqib oliş va qatorlar soni 3 bölganda "PAHNAPLSIIGYIR" körinişida çiqariş kerak.

P A H N A P L S I I G Y I R

Yoziladigan funksiya quyidagiça:

string convert(string s, int numRows);

Işlaş tartibi

Albatta intuitiv usul - bu matnni ikki ölçamli massivga zigzag körinişida töldirib çiqiş böladi. Lekin bunday holatda işlaş vaqti O(n2 + n) körinişiga keladi, sababi massivni töldiriş O(n2) keyin undan string yasaş kerak.

Yana bir - O(n) bilan bitadigan usuli ham bor. Biz uni körib çiqamiz.

  1. Matn uzunligiga qadar işlaydigan for siklini oçamiz.
  2. sikl qadami böyiça qator qadamini topamiz. U 0 va numRows orasida bölişi mumkin.
  3. Qatorlarni matn harflari bilan töldirib boramiz.
for (let i = 0; i < str.length; i++) {
  // Pozitsiya 0 va numRows oraliğidagi son.
  // U 0, 1, 2, ..., numRows, 0, 1, 2, ..., numRows körinişida özgarib boradi.
  const pos = i % (2 * numRows - 2);

  // Qator raqamini topiş
  const j = pos < numRows ? pos : 2 * numRows - 2 - pos;

  // Harflarni qator böyiça yiğib boramiz.
  strNew[j] = strNew[j] ? strNew[j] + str[i] : str[i];
}

Natijada bizda bir ölçamli strNew massivi hosil böladi. Uni stringga ötkazib, qaytaramiz.