Постановка задачи:

Данный массив символов chars сжимает его, используя следующий алгоритм:

• Начните с пустой строки s.
• Для каждой группы последовательно повторяющихся символов в символах:
  • Если длина группы равна 1, добавьте символ к s.
  • В противном случае добавьте символ, а затем длину группы.

Сжатая строка s не должна возвращаться отдельно, а храниться во входном массиве символов chars. Обратите внимание, что длина группы, равная 10 или более, будет разбита на несколько символов в виде символов.

После завершения изменения входного массива верните новую длину массива.

Вы должны написать алгоритм, который использует только постоянное дополнительное пространство.

Пример 1:

• Ввод: символы = ["a","a","b","b","c","c","c"]
• Вывод: возврат 6, первые 6 символов входного массива должны быть: ["a","2","b","2","c","3"]
• Объяснение: Это группы «aa», «bb» и «ccc». Это сжимается до "a2b2c3".

Пример 2:

• Ввод: символы = ["a"]
• Вывод: возврат 1, первый символ входного массива должен быть: ["a"]
• Объяснение: Единственная группа — это «a», которая остается несжатой, поскольку представляет собой один символ.

Пример 3:

• Ввод: символы = ["a","b","b","b","b","b","b","b","b","b","b ","б","б"]
• Вывод: возврат 4, первые 4 символа входного массива должны быть: ["a","b","1","2"]
• Пояснение: Это группы «a» и «bbbbbbbbbbbb». Это сжимается до «ab12».

Ограничения:

• 1
• chars[i] — это строчная английская буква, прописная английская буква, цифра или символ.

Первоначальный мыслительный процесс:

Чтобы решить эту проблему, нам нужно перебирать массив, отслеживая текущий символ и его количество. Когда мы встречаем новый символ, мы добавляем в массив текущий символ и его счетчик (если он больше 1). Нам необходимо убедиться, что мы делаем это на месте, чтобы удовлетворить требования к сложности пространства.

Базовое решение (грубая сила):

Решение методом перебора предполагает создание нового массива для хранения сжатой версии входного массива. Это не экономит пространство, но помогает нам понять необходимые шаги.

Код:

function compressBruteForce(chars: string[]): number {
    const n = chars.length;
    let compressed: string[] = [];
    let i = 0;

    while (i  1) {
            compressed.push(...count.toString().split(''));
        }
    }

    for (let j = 0; j 




  
  
  Анализ временной сложности:

• Временная сложность: O(n), где n — длина массива. Мы проходим по массиву один раз для подсчета символов и один раз для записи результата.
• Пространственная сложность: O(n), поскольку мы используем дополнительное пространство для сжатого массива.

Ограничения:

Решение методом грубой силы не эффективно использует пространство и не удовлетворяет ограничению использования только постоянного дополнительного пространства.

Оптимизированное решение:

Оптимизированное решение предполагает изменение входного массива для хранения сжатой версии. Мы используем два указателя: один для чтения входного массива и один для записи сжатого вывода.

Код:

function compress(chars: string[]): number {
    let writeIndex = 0;
    let i = 0;

    while (i  1) {
            let countStr = count.toString();
            for (let j = 0; j 




  
  
  Анализ временной сложности:

• Временная сложность: O(n), где n — длина массива. Мы проходим по массиву один раз для подсчета символов и один раз для записи результата.
• Пространственная сложность: O(1), поскольку мы используем только постоянное количество дополнительного пространства для переменных.

Улучшения по сравнению с базовым решением:

• Оптимизированное решение снижает сложность пространства до O(1) за счет изменения входного массива на месте.

Краевые случаи и тестирование:

Краевые случаи:

1. Массив содержит только один символ.
2. Массив не содержит последовательных повторяющихся символов.
3. Массив содержит большое количество последовательно повторяющихся символов.

Тестовые случаи:

console.log(compressBruteForce(["a","a","b","b","c","c","c"])); // 6, ["a","2","b","2","c","3"]
console.log(compressBruteForce(["a"])); // 1, ["a"]
console.log(compressBruteForce(["a","b","b","b","b","b","b","b","b","b","b","b","b"])); // 4, ["a","b","1","2"]
console.log(compressBruteForce(["a","a","a","a","a","a","a","a","a","a"])); // 3, ["a","1","0"]
console.log(compressBruteForce(["a","b","c"])); // 3, ["a","b","c"]

console.log(compress(["a","a","b","b","c","c","c"])); // 6, ["a","2","b","2","c","3"]
console.log(compress(["a"])); // 1, ["a"]
console.log(compress(["a","b","b","b","b","b","b","b","b","b","b","b","b"])); // 4, ["a","b","1","2"]
console.log(compress(["a","a","a","a","a","a","a","a","a","a"])); // 3, ["a","1","0"]
console.log(compress(["a","b","c"])); // 3, ["a","b","c"]

Общие стратегии решения проблем:

1. Понимание проблемы: Внимательно прочтите формулировку проблемы, чтобы понять требования и ограничения.
2. Определите ключевые операции: Определите необходимые ключевые операции, такие как подсчет последовательных символов и изменение массива на месте.
3. Оптимизация для повышения эффективности: Используйте эффективные алгоритмы и структуры данных для минимизации временных и пространственных сложностей.
4. Тщательное тестирование: Проверьте решение в различных случаях, включая крайние случаи, чтобы убедиться в правильности.

Выявление подобных проблем:

1. Манипуляция строками:

   • Проблемы, при которых необходимо изменить строки в зависимости от определенных условий.
   • Пример: удаление дубликатов из строки.

2. Алгоритмы на месте:

   • Проблемы, при которых операции необходимо выполнять на месте с ограниченным дополнительным пространством.
   • Пример: удаление элементов из массива без дополнительного места.

Заключение:

• Проблему сжатия массива символов можно эффективно решить, используя как метод грубой силы, так и оптимизированный подход на месте.
• Очень важно понять проблему и разбить ее на управляемые части.
• Использование эффективных алгоритмов обеспечивает оптимальность решения для больших входных данных.
• Тестирование с различными крайними случаями обеспечивает надежность.
• Распознавание закономерностей в проблемах может помочь применить аналогичные решения к другим проблемам.

Практикуя такие задачи и стратегии, вы сможете улучшить свои навыки решения проблем и лучше подготовиться к различным задачам кодирования.