Еще неделя, другой алгоритм…
Привет, друзья! На этой неделе у меня была оценка CoderByte для другого заявления о приеме на работу, которое немного запутало меня: кодирование длин серий. Я никогда не слышал об этой концепции, поэтому решил, что другим будет полезно разобрать ее вместе с проблемой и моим решением.
*** Полное раскрытие и напоминание о том, что это ни в коем случае не ИДЕАЛЬНОЕ решение этого алгоритма, и я уверен, что в Интернете есть более «правильные» и более эффективные ответы; это как раз то, как я смог логически решить это в своем мозгу с временными ограничениями!***
ПРОБЛЕМА
Для входной строки напишите функцию, которая возвращает сжатую версию строки, используя алгоритм кодирования длин серий. Этот алгоритм работает, беря вхождения каждого повторяющегося символа и выводя это число вместе с одним символом повторяющейся последовательности. Например: «wwwggopp» вернет 3w2g1o2p. Строка не будет содержать цифр, знаков препинания или символов.
РАЗБИВКА КОДИРОВАНИЯ ДЛИНЫ СЕРИИ
Первое, о чем я подумал, когда прочитал эту задачу, было: «Что, черт возьми, такое кодирование длин серий?» У меня не было никакой подсказки, и я никогда не слышал об этом понятии в моей жизни. Итак, что может быть лучше, чем сейчас, чтобы учиться?
Мне нравится определение Википедии:
Run-length encoding (RLE) is a form of lossless data compression in which runs of data (sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run.
На первый взгляд это кажется глупой и бесполезной концепцией, но в ситуациях, когда есть очень и очень большие серии персонажей, я вижу, где это может сделать вещи более эффективными.
МОЕ РЕШЕНИЕ
https://replit.com/@thequeenbeebs/RunLengthEncoding
МЕТОД МОЕГО БЕЗУМИЯ
Создание исходных переменных
let count = 1 let finalString = string[0]
Первое, о чем я подумал, когда увидел эту проблему, это то, что мне нужно будет перебрать каждый символ в строке и создать какой-то счетчик для определения количества каждого символа. Я создал переменную под названием «count», которая сообщала нам количество каждого символа и увеличивалась по мере того, как мы перебирали строку.
Я также хотел создать строку, содержащую всю окончательную информацию, которую мы в конечном итоге вернем. Причина, по которой я не начал с создания пустой строки, заключалась в том, что я знал, что нам понадобится что-то для сравнения при циклическом просмотре входной строки, поэтому я добавил первый символ из строки. Итак, прямо сейчас, используя приведенный выше пример, finalString будет просто «w», а счетчик будет равен 1, чтобы представить 1 символ, который мы уже прошли.
Перебор каждого символа в строке
for (let i = 1; i < string.length; i++) {
...
}
Для этого цикла я решил использовать этот стиль итерации вместо ситуации for/in, потому что я знал, что на самом деле хочу просто начать со второго символа в строке и сравнить его с первым символом уже в нашей переменной finalString. .
Условное: Часть 1
if (string[i] === finalString[finalString.length - 1]) {
count += 1
}
Итак, что делает это условное выражение, так это проверяет и видит, совпадает ли текущий символ в цикле с символом перед ним, который мы добавили в нашу finalString и который в настоящее время является последним символом.
Если мы по-прежнему используем наш пример из приведенного выше, строка[1] будет «w», а finalString[0] также будет «w». Итак, это условное выражение возвращает true, и мы добавляем еще одно к счету.
Условное: Часть 2
else {
finalString = finalString.slice(0, finalString.length - 1) +
count + finalString.slice(finalString.length - 1) + string[i]
count = 1
}
Это та часть, которая становится немного сложной. Что происходит, когда мы переходим от одного символа к другому, когда нажимаем четвертый символ в строке «g»?
Я уверен, что есть более элегантный способ найти решение, но я нашел способ разрезать finalString следующим образом:
all the characters in the finalString except the last one + the counter we have been adding to + the character we have been comparing the other characters with + the new character that we have come across, that we will now be using to compare against other characters
Это немного сбивает с толку, но это даст вам точный формат, необходимый для этой задачи. В этой ситуации, если мы поместим console.log() внутри этого условия else, первое из них будет отображаться как «3wg». На данный момент в finalString есть только один символ, поэтому перед счетчиком, равным 3, ничего нет. После этого у нас есть «w», на который мы ссылались все время, а затем «g», на который мы будем ссылка после этого.
Последнее, что вам нужно сделать, это сбросить переменную count в 1, так как мы начинаем заново и подсчитываем экземпляры нового символа.
Прибавляя окончательный счет
finalString = finalString.slice(0, finalString.length - 1) + count + finalString.slice(finalString.length - 1)
Единственное, что этот цикл не выполняет, — это то, что останется еще один счетчик, который необходимо прикрепить к finalString после того, как мы закончим итерацию. Как и в приведенном выше условном выражении else, мы помещаем счетчик внутрь фрагментов finalString, чтобы он находился именно в том месте, которое нам нужно. Единственное отличие состоит в том, что мы не добавляем еще один символ в конец finalString, потому что мы прошлись по ним всем и больше не с чем сравнивать!
Поместите этот код вне условных выражений и цикла, чтобы он выполнялся только один раз, прямо перед тем, как мы вернем finalString.
Вернуть финальную строку
return finalString
Вот и все! Готово!
Мне действительно интересно увидеть решения этой проблемы другими людьми, поэтому не стесняйтесь комментировать и сообщать вам, как вы справитесь с кодированием длин серий. Удачного кодирования!
