Сложность: medium
Дан массив символов chars, сжать его, используя следующий алгоритм:
Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars:
Если длина группы равна 1, добавьте символ к строке s.
В противном случае добавьте символ, а за ним длину группы.
Сжатая строка s не должна возвращаться отдельно, а вместо этого должна быть сохранена в входном массиве символов chars. Обратите внимание, что длины групп, которые равны 10 или более, будут разделены на несколько символов в chars.
После того как вы закончите модификацию входного массива, верните новую длину массива.
Вы должны написать алгоритм, который использует только постоянное дополнительное пространство.
Пример:
Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".
👨💻 Алгоритм:
1⃣Объявите переменные i – первый индекс текущей группы, и res – длина ответа (сжатой строки). Инициализируйте i = 0, res = 0.
2⃣Пока i меньше длины chars: Найдите длину текущей группы последовательных повторяющихся символов groupLength. Добавьте chars[i] к ответу (chars[res++] = chars[i]). Если groupLength > 1, добавьте строковое представление groupLength к ответу и увеличьте res соответственно. Увеличьте i на groupLength и перейдите к следующей группе.
3⃣Верните res.
😎 Решение:
class Solution:
def compress(self, chars: List[str]) -> int:
i = 0
res = 0
while i < len(chars):
group_length = 1
while (i + group_length < len(chars) and chars[i + group_length] == chars[i]):
group_length += 1
chars[res] = chars[i]
res += 1
if group_length > 1:
str_repr = str(group_length)
chars[res:res+len(str_repr)] = list(str_repr)
res += len(str_repr)
i += group_length
return res
Ставь 👍 и забирай 📚 Базу знаний