Немного сложно, несколько вопросов по алгоритму интервью, связанных со "скользящим окном"

алгоритм

Предисловие к научно-популярному: что такое алгоритм скользящего окна

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

Предположим, есть массив [a b c d e f g h], массив размера 3раздвижное окноПроведите по нему, и у вас есть:

[a b c]
  [b c d]
    [c d e]
      [d e f]
        [e f g]
          [f g h]

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

1. Максимальное значение скользящего окна

Название взято из выпуска № 239 LeetCode: Максимум скользящего окна. Сложность вопроса — Hard, а текущий процент прохождения — 40,5%.

Описание темы

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

Возвращает максимальное значение скользящего окна.

Пример:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Тематический анализ

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

Дополнение: Что такое двусторонняя очередь (Dqueue)

Deque означает «двойная очередь», то есть двусторонняя очередь, которая имеет структуру данных очереди и стека. Как следует из названия, это очередь, которая поддерживает операции вставки и удаления как на внешнем, так и на внутреннем уровне.

Deque наследуется от Queue (очереди), а его непосредственная реализация включает в себя ArrayDeque, LinkedList и т.д.

описание анимации

动画描述 Made by Jun Chen

Код

class Solution {
   public int[] maxSlidingWindow(int[] nums, int k) {
        //有点坑，题目里都说了数组不为空，且 k > 0。但是看了一下，测试用例里面还是有nums = [], k = 0，所以只好加上这个判断
        if (nums == null || nums.length < k || k == 0) return new int[0];
        int[] res = new int[nums.length - k + 1];
        //双端队列
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            //在尾部添加元素，并保证左边元素都比尾部大
            while (!deque.isEmpty() && nums[deque.getLast()] < nums[i]) {
                deque.removeLast();
            }
            deque.addLast(i);
            //在头部移除元素
            if (deque.getFirst() == i - k) {
                deque.removeFirst();
            }
            //输出结果
            if (i >= k - 1) {
                res[i - k + 1] = nums[deque.getFirst()];
            }
        }
        return res;
     }
}

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

Название происходит от вопроса № 3 на LeetCode: Самая длинная подстрока без повторяющихся символов. Сложность вопроса — средняя, ​​а текущий проходной балл — 29,0%.

Описание темы

Дана строка, пожалуйста, найдите ту, которая не содержит повторяющихся символовсамая длинная подстрокадлина.

Пример 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

Тематический анализ

Создайте 256-битный целочисленный массив freg для сопоставления между символами и позициями их появления.

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

  • (1) Если пройденный в настоящее время символ никогда не появлялся, то непосредственно расширяйте правую границу;
  • (2) Если появился пройденный в данный момент символ, сжать окно (левый указатель перемещается вправо), а затем продолжить наблюдение за проходимым в данный момент символом;
  • (3) Повторяйте (1) (2) до тех пор, пока левый указатель больше не сможет двигаться;
  • (4) Сохранение результата res, обновление результата res размером окна, которое появляется каждый раз, и, наконец, возврат res для получения результата.

описание анимации

动画描述

Код

// 滑动窗口
// 时间复杂度: O(len(s))
// 空间复杂度: O(len(charset))
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int freq[256] = {0};
        int l = 0, r = -1; //滑动窗口为s[l...r]
        int res = 0;
        // 整个循环从 l == 0; r == -1 这个空窗口开始
        // 到l == s.size(); r == s.size()-1 这个空窗口截止
        // 在每次循环里逐渐改变窗口, 维护freq, 并记录当前窗口中是否找到了一个新的最优值
        while(l < s.size()){
            if(r + 1 < s.size() && freq[s[r+1]] == 0){
                r++;
                freq[s[r]]++;
            }else {   //r已经到头 || freq[s[r+1]] == 1
                freq[s[l]]--;
                l++;
            }
            res = max(res, r-l+1);
        }
        return res;
    }
};

3. Наличие повторяющегося элемента II

Название взято из выпуска № 219 на LeetCode: повторяющиеся элементы II. Сложность вопроса — «Легко», а текущий проходной балл — 33,9%.

Описание темы

Дан массив целых чисел и целое числоk, чтобы определить, есть ли в массиве два разных индексаiиj, так чтоnums [i] = nums [j],иiиjАбсолютное значение разницы не превышаетk.

Пример 1:

输入: nums = [1,2,3,1], k = 3
输出: true

Пример 2:

输入: nums = [1,0,1,1], k = 1
输出: true

Пример 3:

输入: nums = [1,2,3,1,2,3], k = 2
输出: false

Тематический анализ

Используйте скользящие окна и таблицы поиска для решения.

  • установить таблицу поискаrecord, который используется для сохранения элементов, вставленных при каждом его обходе,recordМаксимальная длинаk
  • перебирать массивnums, каждый раз, когда он проходит,recordНаходит, существует ли тот же элемент, и возвращает, если он существуетtrue, обход заканчивается
  • Если этот обходrecordЕсли не найден, вставьте элемент вrecord, затем посмотрите наrecordДлинаk + 1
  • если в это времяrecordДлинаk + 1, затем удалитеrecordэлемент, значение которогоnums[i - k]
  • Если вы перебираете весь массивnumsВернуть, если не нашлиfalse

описание анимации

动画描述

Код

// 时间复杂度: O(n)
// 空间复杂度: O(k)
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if(nums.size() <= 1)  return false;
        if(k <= 0)  return false;
        unordered_set<int> record;
        for(int i = 0 ; i < nums.size() ; i ++){
            if(record.find(nums[i]) != record.end()){
                return true;
            }
            record.insert(nums[i]);
            // 保持record中最多有k个元素
            // 因为在下一次循环中会添加一个新元素,使得总共考虑k+1个元素
            if(record.size() == k + 1){
                record.erase(nums[i - k]);
            }
        }
        return false;
    }
};

4. Подмассив наименьшей длины

Название взято из выпуска № 209 на LeetCode: Подмассив с наименьшей длиной. Сложность вопроса — средняя, ​​а текущий проходной балл — 37,7%.

Описание темы

учитывая содержаниеnмассив положительных целых чисел и положительное целое число **s ,Найдите в массиве сумму, удовлетворяющую≥ сНаименьший непрерывный подмассив длины. ** Если нет подходящего непрерывного подмассива, вернуть 0.

Пример:

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

Тематический анализ

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

  • (1) Пусть право перемещается вправо до тех пор, пока сумма подмассива не станет больше или равна заданному значению или право не достигнет конца массива;
  • (2) обновить кратчайшее расстояние, переместить левое изображение на один бит вправо и вычесть удаленное значение из суммы;
  • (3) Повторяйте шаги (1) и (2), пока правое не достигнет конца, а левое не достигнет критического положения.

описание анимации

Установите длину скользящего окна на 0 в крайнем левом углу числовой строки.

1. R начинает двигаться с правого конца скользящего окна, пока интервал не удовлетворяет заданному условию, то есть сумма больше 7, затем останавливается на третьем элементе 2, а текущая оптимальная длина равна 4

图 1

2. Левый конец L скользящего окна начинает двигаться, уменьшает размер скользящего окна и останавливается на первом элементе 3. В это время сумма интервалов равна 6, так что сумма интервалов не удовлетворяет заданному условиях (на данный момент не больше 7)

图片 2

3. R ​​продолжает движение в правом конце скользящего окна и останавливается на четвертом элементе 4. В это время сумма равна 10, но оптимальная длина по-прежнему 4

图片 3

Код

// 滑动窗口的思路
// 时间复杂度: O(n)
// 空间复杂度: O(1)
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int l= 0,r = -1;    // nums[l...r]为我们的滑动窗口
        int sum = 0;
        int result = nums.length + 1;
        while (l < nums.length){ // 窗口的左边界在数组范围内,则循环继续

            if( r+1 <nums.length && sum < s){
                r++;
                sum += nums[r];
            }else { // r已经到头 或者 sum >= s
                sum -= nums[l];
                l++;
            }

            if(sum >= s){
                result = (r-l+1) < result ? (r-l+1) : result ;
            }
        }
        if(result==nums.length+1){
            return 0;
        }
        return result;
    }
}

Персональный сайт:www.cxyxiaowu.com

Личный общедоступный номер: изучение алгоритмов за пять минут

Категории