Введение
Эй, читатель, возникли проблемы с решением этой проблемы с кодом? Возможно, все это слишком чертовски пугающе? Или, может быть, вам нужно другое решение для быстрой справки. Не беспокойтесь, вы пришли в нужное место. Давайте погрузимся в эту проблему среднего уровня, используя Javascript.
Подсказка
The string"PAYPALISHIRING"is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line:"PAHNAPLSIIGYIR"Write the code that will take a string and make this conversion given a number of rows: string convert(string s, int numRows);
Пример 1:
Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"
Пример 2:
Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G Y A H R P I
Пример 3:
Input: s = "A", numRows = 1 Output: "A"
Мысли
Эта задача читается довольно легко. Нет ничего слишком «математического» или многословного, что может быть приятно. Иногда некоторые слова звучат странно, например «фиксированный шрифт», но если вы продолжите читать и посмотрите на предоставленные примеры, все станет ясно. Мне нравится читать подсказку и примеры несколько раз, и стоит потратить время, чтобы полностью понять, о чем просит автор.
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
Первый бит кажется довольно простым. Нам дана строка, которая написана в виде зигзага.
P A H N A P L S I I G Y I R
Это будет тот образец. Заметили здесь какие-либо закономерности?3, 1,3,1,3,1,2. Подожди минутку…
length of 3 characters... P A Y also a length of 3 characters... A P Y Ahhh.... I see... P A A P Y ...zigzag pattern... P A H N A P L S I I G Y I R ... got it !!!
Если не считать последних двух символов, похоже, что зигзагообразный паттерн имеет длину 3 (по диагонали или по вертикали). Похоже, в конце мы получили значение 2. Возможно, это связано с тем, что у нас недостаточно символов для заполнения строки 3. Давайте продолжим читать, чтобы получить больше подсказок.
And then read line by line: "PAHNAPLSIIGYIR"
Интересно, что мы читаем слева направо и сверху вниз, но написали строку по определенному шаблону (зигзагообразный узор в рядах по 3).
Write the code that will take a string and make this conversion given a number of rows: string convert(string s, int numRows);
Последнее здесь кажется мне довольно разумным. Автор говорит, что нам дается ввод строки и размер каждой строки.
Подождите... Давайте взглянем на эти примеры...
Example 1: Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"
Круто, почти то же самое, что мы сломали.
Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G Y A H R P I
Если мы увеличим размер каждой строки в нашем зигзагообразном узоре, это должно выглядеть так. Круто, это проверено!
Input: s = "A", numRows = 1 Output: "A"
Похоже, это базовый случай. Если нам дана строка с одним символом, верните входную строку как есть!
Резюме
- Входные данные: строка
- Входные данные: размер строк в каждом зигзагообразном или загнувшемся узоре.
- Выходные данные. Строка, представляющая собой входную строку в виде зигзага. Читаем эту схему слева направо и сверху вниз.
- Базовый регистр: возвращает строку, если она состоит из одного символа.
Разработка
Прямо за воротами, давайте позаботимся об этом базовом случае. Я буду использовать условный оператор и проверю две вещи. Мы также будем использовать оператор "или", потому что мы хотим вернуть строку в любом из этих случаев.
Во-первых, длина строки должна быть равна 0 или 1.
Второе — это то, что требует немного больше размышлений. Что произойдет, если строка имеет тот же размер, что и значение numRows или первый зиг. Не будет ли это просто линией? Если это так, не могли бы мы просто вернуть строку? Поскольку мы читаем слева направо и сверху вниз… да! Мы бы прочитали эту строчку. Так давайте вернем.
const convert = function(s, numRows) {
if(numRows <= 1 || s.length <= numRows) return s;
};
Хорошо, здесь мы получаем немного мета. Объявляя переменные, вы должны объявлять только то, что вам нужно. Тем не менее, вы часто будете делать слишком мало или слишком много... Уловка 22. Так что начните с того, что, как вы точно знаете, вам понадобится.
Что теперь? Как насчет того, чтобы еще раз взглянуть на этот образец.
Посмотрим, сможем ли мы извлечь какие-либо идеи из его структуры…
How do I build this... then read it in a different way... P A H N A P L S I I G Y I R what about some arrays... [P A H N] [A P L S I I G] [Y I R] What if I nested them... like a grid or matrix... [ [P,A,H,N], [A,P,L,S,I,I,G], [Y,I,R] ] ... we can build one way, and read another way.
Итак, как нам заполнить эту сетку/матрицу? Мне придется построить его, заполнить зигзагообразным узором, а затем прочитать по-другому. Похоже, нам понадобится пустой массив, который мы можем построить с помощью наших numRows input и цикла for. .
if(numRows <= 1 || s.length <= numRows) return s;
let rows = []; <-- empty array
for (let i = 0; i < numRows; i++) { <-- for loop + numRows
rows[i] = []; <-- Build grid/matrix with empty arrays
}
};
Далее нам нужно подумать о том, как мы будем заполнять эту матрицу. Как нам заставить зигзагообразный узор совпадать с нашей пустой матрицей? Допустим, мы использовали цикл for и могли перебирать входную строку…
for (let i = 0; i < s.length; i++) { <-- for loop + input string
}
Что, если бы мы использовали входную длину numRow, чтобы определить, когда и где мы добавляем/вставляем значения в массив? Мы могли бы использовать другой цикл for, но он не будет вставлять значения в желаемый зигзагообразный шаблон. Это также немного неуклюже. Что, если вместо этого мы попытаемся использовать счетчик. Это дешевле во время выполнения, и мы можем немного поработать над этой идеей.
Используя скобки, мы можем получить доступ к вложенному массиву в нашей переменной rows. Если мы поместим это внутрь нашего второго цикла, мы сможем вставлять значения в эту структуру.
let rows = [];
let counter = 0; <--- counter
for (let i = 0; i < numRows; i++) {
rows[i] = [];
}
for (let i = 0; i < s.length; i++) {
rows[counter].push(s[i]); <--- will insert via counter!
...
Комбинация Row + Counter очень мощная. При этом мы можем контролировать, какую строку мы вставляем в нашу матрицу. Тем не менее, когда мы .push() в массив, мы вставляем значение в его конец. Итак, если мы думаем о строках и столбцах в матрице, она вставляется слева направо. Мы можем воспользоваться этим, вставив символы нашей входной строки в зигзагообразный узор. Итак, как нам заставить это работать?
Как насчет логического значения? Давайте зададим для переменной значение false и назовем ее 'reverse'. Это позволит нам обратить или отклонить то, как мы вставляем наши символы в эту матрицу. Мы увеличиваем или уменьшаем этот счетчик на основе ввода numRow или длины нашего зигзага. Если это правда, это зигзаг; если ложно, то забивается?
const convert = function(s, numRows) {
if(numRows <= 1 || s.length <= numRows) return s;
let rows = [];
let counter = 0;
let reverse = false;
for (let i = 0; i < numRows; i++) {
rows[i] = [];
}
for (let i = 0; i < s.length; i++) {
rows[counter].push(s[i]); <-- Note: we insert first !!!
if (reverse === false) { <-- Now we check the counter!!!
counter++;
} else {
counter--;
}
Добавим к этому немного логики. Используя условный оператор, давайте проверим наш счетчик. У нас есть 2 случая для проверки: если мы увеличим и достигнем нашего значения numRow или если мы уменьшим и достигнем 0 >. В любом случае переменная будет перевернута с помощью оператора взрыва или «!».
for (let i = 0; i < s.length; i++) {
rows[counter].push(s[i]);
if (reverse === false) {
counter++;
} else {
counter--;
}
if (counter === numRows - 1 || counter === 0) {
reverse = !reverse;
}
}
Почти готово, но нужно будет вернуть этот ответ в виде одной выходной строки. Давайте создадим возвращаемую переменную, пройдемся по нашей матрице (строкам) с помощью .forEach() и воспользуемся .join(), чтобы связать все эти символы в строку.
... let rows = []; <-- matrix should be stored in here
let counter = 0;
let reverse = false;
let result = '';
...
rows.forEach((row) => {
result += row.join("");
});
Давайте вернем эту переменную после выполнения .forEach(). Запустите свой код, и все должно пройти тесты!
rows.forEach((row) => {
result += row.join("");
});
return result;
Решение
const convert = function(s, numRows) {
if(numRows <= 1 || s.length <= numRows) return s;
let rows = [];
let counter = 0;
let reverse = false;
let result = '';
for (let i = 0; i < numRows; i++) {
rows[i] = [];
}
for (let i = 0; i < s.length; i++) {
rows[counter].push(s[i]);
if (reverse === false) {
counter++;
} else {
counter--;
}
if (counter === numRows - 1 || counter === 0) {
reverse = !reverse;
}
}
rows.forEach((row) => {
result += row.join("");
});
return result;
};
Заключение
Важным выводом для меня было то, как двигаться по зигзагообразному шаблону в итерации, используя логическое значение и счетчик. Мы с Mind Blown многому научились благодаря этой проблеме.
Тем из вас, кто понял это во время чтения статьи, респект! Если нет, не беспокойтесь. Продолжайте в том же духе, но потратьте время на то, чтобы понять свои зависания. Это настоящее сокровище 💎 !
Огромный привет Алисе Байрамович, чей блог помог мне разобраться в этой проблеме более подробно. Вы найдете ссылку ниже, это стоит прочитать! Продолжайте учиться и удачного кодирования!
Ссылки
- The ZigZag Conversion Problem by Alisa Bajramovic: https://dev.to/alisabaj/the-zigzag-conversion-problem-3nne - Leetcode: leetcode.com
