Leetcode Pattern 2 | Раздвижные окна для строк

Leetcode Pattern 2 | Раздвижные окна для строк

Другой реддитор из / r / cscareerquestions указал мне на эту замечательную ветку в обсуждении leetcode, которая раскрывает шаблон скользящего окна для решения нескольких проблем со строками (подстроками). Сегодня мы исследуем интуицию, лежащую в основе этой мощной техники, и применим ее к некоторым очень известным задачам со струнами. Еще один факт, который я стремлюсь доказать, заключается в том, что некоторые задачи, помеченные как сложные, действительно легко решаются, если мы усвоили требуемый шаблон.

Я твердо верю в обучение на собственном опыте, поэтому давайте рассмотрим очень простой пример, чтобы понять, как работают скользящие окна, а затем вернемся к проблемам с leetcode. Подход со скользящим окном обычно помогает нам уменьшить временную сложность для подходов грубой силы.

Given an array of integers of size ‘n’.
Our aim is to calculate the maximum sum possible for ‘k’ consecutive elements in the array.

Input  : arr[] = {100, 200, 300, 400}
         k = 2
Output : 700

Решить ее с помощью перебора - значит изучить все возможные случаи. На данный момент нас действительно не волнует эффективность, но нам нужны правильные результаты. Таким образом, мы могли запустить вложенный цикл, исследуя все окна длины k в данном массиве, и выбрать максимальную сумму.

// BRUTE FORCE : iterate through all windows of size k
for(int i = 0; i < n-k+1; i++){    
    int current_sum = 0;
     
    for(int j = 0; j < k; j++){        
        current_sum = current_sum + arr[i+j];         
    }
    max_sum = max(current_sum, max_sum);    // pick maximum sum 
}

Теперь обратите внимание, что, вычислив сумму 1-го окна (размер k), чтобы получить сумму следующего перекрывающегося окна, нам просто нужно оставить крайнее левое значение элемента и добавить новое (крайнее правое) значение элемента, поэтому мы, по сути, сохранение пересчета суммы для неизменяющейся части окна.

int max_sum = 0, window_sum = 0; 
/* calculate sum of 1st window */
for (int i = 0; i < k; i++)  window_sum += arr[i]; 
/* slide window from start to end in array. */
 
for (int i = k; i < n; i++){ 
    window_sum += arr[i] - arr[i-k];    // saving re-computation
    max_sum = max(max_sum, window_sum);
}

Вуаля! мы использовали память для экономии времени, как мы увидим, в этом заключается очень классический компромисс в алгоритмах и скользящих окнах. Сложность времени снижена с O (n²) до O (n). Теперь перейдем к актуальным проблемам с leetcode.

76. Минимальная подстрока окна

примечание: эта первая проблема была тщательно проанализирована, поскольку это сложная концепция и составляет основу для решения следующих 5. Освойте эту и попробуйте остальные самостоятельно, это был бы лучший способ научиться.

В предыдущем примере окно было фиксированного размера, но здесь мы используем окно переменного размера, определяемого маркерами begin и end. Подход грубой силы заключался бы в переборе всех возможных подстрок и определении минимального окна, которое содержит все символы T. Как узнать, есть ли в подстроке все символы T? Вы можете использовать частотную таблицу T, в которой символы сохраняются по количеству вхождений следующим образом:

# initialize frequency table
for char c in T do 
    table[c]++;
end
counter = table.size()                 # unique chars in T
for char c in string B do
    if(char c in table){ 
        table[c]--;                    # decrement count for c
        if(table[c] == 0) counter--;
    }
end
if(counter == 0){ # B has every character in T }

Таким образом, мы в основном гарантируем, что каждый уникальный символ в T существует в B столько раз, сколько он существует в T, поддерживая счетчик. Это нормально, если в T 4 'K, а в B 7' K, счетчик таблицы для 'K' просто станет отрицательным, но в какой-то момент до этого он станет 0, доказывая, что строка B имеет не менее 4 'K в нем, удовлетворяя потребность в отношении «K», расширяя логику на другие символы в T, если counter = 0, B имеет все символы в T.

Итак, переходя к части скользящего окна, мы продолжаем сдвигать конец вправо, исследуя каждый новый символ и обновляя счетчик в таблице. Как только мы нажимаем counter = 0, это означает, что у нас есть действительный ответ, поэтому мы пытаемся урезать его, удаляя ненужные символы с самого начала, сдвинув начало вправо. Мы постоянно пытаемся проверить / сделать строку недействительной, манипулируя счетчиками и счетчиками таблиц.

Найдите минутку, разберитесь в этом коде. Пройдитесь по нему на бумаге для этого примера: [S: ADOBECODEBANC | Т: "ABC"]. Не волнуйтесь, код просто сильно аннотирован, на самом деле он очень лаконичен.

Интуиция: лучшей подстрокой для ответа была бы просто перестановка T, если такая подстрока существует в S, но в противном случае мы могли бы иметь бесполезные символы, сидящие между основными символами, которые делают подстроку действительной в качестве ответа. Наша попытка состоит в том, чтобы удалить такие символы без потери необходимых. После максимально возможной обрезки мы продолжаем сдвигать конец вправо и повторять весь процесс.

Каждый раз, когда counter = 0, у нас есть действительный кандидат на наш ответ, но мы обновляем ans, только если он короче, чем ранее записанная минимальная длина ans.

438. Найти все анаграммы в строке

Точно так же, как указано выше, с добавленным условием, что длина подстроки должна быть равна p и что мы должны возвращать индексы всех таких вхождений.

30. Подстрока с объединением всех слов

А вот и мое доказательство того, что не все «сложные» Leetcode действительно сложные, это просто небольшая модификация вышеупомянутой проблемы, которая помечена как «легко». Вместо символов в вышеупомянутом вопросе теперь у нас есть слова, поэтому он стал немного запутаннее.

3. Самая длинная подстрока без повторяющихся символов

Здесь мы строим частотную таблицу из подстроки, которую мы исследовали, так как цель состоит в том, чтобы найти самую длинную Susbstring без каких-либо повторений. Как и в предыдущем случае, мы сдвигаем end и продолжаем строить таблицу, и как только мы нажимаем повторение, то есть end char уже в таблице, мы начинаем сдвигать начать. Мы записываем максимум перед скольжением begin для ans.

159. Самая длинная подстрока, содержащая не более двух разных символов

567. Перестановка в строке

Другие проблемы, которые можно решить аналогично:

340. Самая длинная подстрока, содержащая не более K различных символов , которая буквально совпадает с строкой с K = 2.

424. Замена самого длинного повторяющегося символа

Хорошим упражнением на этом этапе было бы подумать, почему метод скользящего окна на самом деле работает, выявить все возможные случаи для проблемы с минимальной оконной подстрокой, и у вас будет более глубокая интуиция в этой технике.

Несколько интересных фактов:

1. На решение этих проблем у меня ушло меньше времени, чем на то, чтобы придумать, как объяснить это письменно.
2. Сначала я решил проблему, помеченную как hard, а затем соответствующую легкую задачу, поскольку я использую расширение, чтобы скрыть уровни сложности в leetcode loll.
3. Я твердо верю, что понимание того, как программист написал код, более важно, чем сам код, поэтому я работаю над codeback, инструментом воспроизведения кода, позволяющим пользователям останавливать, редактировать и воспроизводить код построчно, а также выполнять код для см. вывод.

Следите за обновлениями и не стесняйтесь связаться со мной на LI: https://www.linkedin.com/in/csgator/