Сложность: 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 {
public int compress(char[] chars) {
int i = 0;
int res = 0;
while (i < chars.length) {
int groupLength = 1;
while (i + groupLength < chars.length && chars[i + groupLength] == chars[i]) {
groupLength++;
}
chars[res++] = chars[i];
if (groupLength > 1) {
String strRepr = Integer.toString(groupLength);
for (char ch : strRepr.toCharArray()) {
chars[res++] = ch;
}
}
i += groupLength;
}
return res;
}
}Ставь 👍 и забирай 📚 Базу знаний