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.
- Matn uzunligiga qadar işlaydigan for siklini oçamiz.
- sikl qadami böyiça qator qadamini topamiz. U 0 va numRows orasida bölişi mumkin.
- 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.