Обмен технологиями

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Подмассив минимальной длины.

Leetcode 209. Подмассив минимальной длины.

При просмотре этой темы первое, что приходит на ум, — это насильственное перечисление, поэтому давайте попробуем перечислить следующее:

Очевидно, что метод перебора перебора истечет по тайм-ауту.

Итак, есть ли способ оптимизировать его, чтобы он не истекал по тайм-ауту? Давайте проанализируем это:

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

Конкретные шаги по оптимизации перечисления заключаются в следующем:

В приведенном выше процессе перечисления наш синий ящик похож на скользящее окно с нефиксированным размером. Мы называем этот метод.раздвижное окно

Для раздвижных окон это не что иное, как следующие шаги:

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

Согласно методу скользящего окна, время ожидания нашего кода не истекает.

Кратко проанализируем следующую временную сложность: Судя по коду, это O(n²), но из-за нашей идеи скользящего окна два указателя перемещаются в одном направлении и не вернутся назад, когда правый указатель заканчивается, цикл завершается, поэтому он заканчивается;Временная сложность равна O(n).

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ret = INT_MAX;
        int n = nums.size();
        int sum = 0;
        for(int left = 0, right = 0; right < n; right++)//right后移
        {
            //进窗口
            sum += nums[right];
            //判断窗口
            while(sum >= target)
            {
                //符合条件，更新结果
                ret = min(ret,right - left + 1);
                sum -= nums[left];//出窗口
                left++;
            }  
        }
        if(ret == INT_MAX)
            return 0;
        else
            return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

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

Первый метод, который приходит на ум при ответе на этот вопрос, — это, несомненно, перечисление, а затем подсчет количества раз, когда каждый символ появляется дважды, то строка, соответствующая текущему символу, является самой длинной подстрокой;

Мы обнаружили, что метод перебора методом перебора также может пройти

Есть ли лучшее решение?Давайте проанализируем это

Разве приведенное выше решение не является просто раздвижным окном?

Является ли временная сложность O(n) в данный момент лучше, чем у насильственного перебора O(n)?²) даже лучше

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int hash[128] = { 0 };
        int ret = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            hash[s[right]]++;//入窗口，先记录当前
            while(hash[s[right]] > 1)//若s[right]重复
            {
                hash[s[left]]--;//出窗口
                left++;
            }
            ret = max(ret,right - left + 1);//更新结果
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3. Максимальное количество последовательных единиц III.

Leetcode 1004. Максимальное количество последовательных единиц III.

Из анализа темы мы видим, чтоТот факт, что 0 можно перевернуть, означает: 0 можно использовать как 1. . Тогда наша цель — найти интервал, содержащий наибольшее количество единиц, причем количество нулей в этом интервале не может превышать k.

Насильственный метод перебора для этого вопроса не будет продемонстрирован. Перейдем непосредственно к скользящему окну.


Таким образом, наш код пройдет

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        int zero = 0;//统计0的个数
        int ret = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            //进窗口，判断是否是0
            if(nums[right] == 0)
                zero++;
            //判断0的个数是否大于k
            while(zero > k)
            {
                //判断是否是0出窗口
                if(nums[left] == 0)
                    zero--;
                left++;
            }
            //更新结果
            ret = max(ret,right-left+1);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

4. Минимальное количество операций по уменьшению х до 0.

leetcode 1658. Минимальное количество операций для уменьшения x до 0

Прочитав вопросы, мы можем обнаружить, что оно есть с левой и с правой стороны. Трудно ли его контролировать? Так что же нам делать?
Обратное верно, когда это трудно

• Находим в массиве непрерывный интервал, удаляем содержимое непрерывного интервала в массиве, а оставшееся содержимое в точности равно x, тогда мы нашли ситуацию
• Этот непрерывный интервалСумма элементов массива минус x
• Когда в массиве найден самый длинный непрерывный интервал, мы нашли лучшее решение.

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

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int ret = 0;
        int total = 0;
        int n = nums.size();
        for(auto e : nums)
            total += e; //求数组的和
        int target = total - x; //target为要找的连续区间的总大小

        if(target < 0)//细节
            return -1;
        if(total == x)
            return n;
            
        int sum = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            sum += nums[right];//进窗口
            while(sum > target)
            {
                sum -= nums[left];
                left++;
            }
            if(sum == target)//找到目标区间，取长的一个
                ret = max(ret,right - left + 1);
        }
        if(ret == 0)
            return -1;
        else
            return n - ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

5. Корзины с фруктами

Leetcode 904.Фрукты в корзине

Название такое длинное, что оно означает?

Корзин всего две, в корзинах может быть только два вида фруктов, и они не могут пересекать деревья. Найдите максимальное количество деревьев, через которое вы сможете пройти.
То есть, чтобы найти длину непрерывного интервала, мы можем использовать скользящее окно.

Так как же мне узнать, сколько фруктов сейчас собирают? ----Использовать статистику хэш-таблицы

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

Из требований к вопросу видно, что категория меньше 10.⁵, поэтому мы можем напрямую использовать массив + переменную (тип записи)

Таким образом, наша эффективность значительно повысилась.

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        int ret = 0;
        int hash[100000] = { 0 };
        int kinds = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            if(hash[fruits[right]] == 0)//判断是否是新种类水果
                kinds++;

            hash[fruits[right]]++;//进窗口
            
            while(kinds > 2)//判断总类是否大于2
            {
                hash[fruits[left]]--;//出窗口
                if(hash[fruits[left]] == 0)
                    kinds--;  //去除该种类
                left++;
            }
            ret = max(ret,right - left + 1);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

6. Найдите в строке все анаграммы букв.

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

Из анализа вопроса мы видим, что речь идет о поиске строки p в строке s (порядок символов в строке p может быть нарушен).
Тогда мы сможемПросто найдите подстроку, длина которой равна p, а тип и номер символа равны строке p.。

Таким образом, мы можем использовать две хэш-таблицы для подсчета типов и количества символов в строке p и строке s соответственно.

Тогда давайте сначала попробуем это сделать, используя принудительное перечисление:

Как сравниваются две хэш-таблицы?

1. Сначала используйте hash1, чтобы записать количество типов символов в строке p.
2. Пройдите s и найдите подстроку, длина которой равна p, а hash2 сохранит текущий символ.
   а Если hash2[right] <= hash1[right], количество «допустимых символов» увеличивается.
   б. Если hash2[right] > hash2[right], тип «допустимых символов» остается неизменным.

Метод насильственного перебора действительно возможен, но он относительно неэффективен.
Поскольку мы ищем непрерывный интервал, можем ли мы использовать скользящее окно?давай попробуем

Таким образом, наша эффективность будет намного выше.

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int len = p.size();
        int hash1[128] = { 0 };
        for(auto e: p)
            hash1[e]++;//统计p串的种类
        int n = s.size();
        int hash2[128] = { 0 };//统计子串种类
        int kinds = 0;
        int tmp = 0;
        for(int left = 0,right = 0; right < n ; right++)
        {
            hash2[s[right]]++; //进窗口
            tmp++;//子串长度增加
            if(hash2[s[right]] <= hash1[s[right]])
                kinds++;//"有效字符"种类增加
            if(tmp > len)
            {
                if(hash2[s[left]] <= hash1[s[left]])
                    kinds--;//left位置为“有效字符”，种类减少
                hash2[s[left]]--;
                tmp--;
                left++;
            }
            if(tmp == len)
                if(kinds == len)
                    ret.push_back(left);
        }
        return ret;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

7. Объединить подстроки всех слов.

leetcode 30. Объединить подстроки всех слов.

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

Этапы решения проблемы:

1. Сначала используйте hash1 для подсчета типов строк в словах.
2. Используйте скользящее окно (поскольку длина строки фиксирована, вы можете напрямую изменить длину)
   а. Начало определения: слева, справа.
   б. Когда строка попадает в окно, вам нужно использовать строковую функцию substr, чтобы обрезать ее.
   в. Определить тип строки.
   Стоит ли выходить из окна
   Обновить результаты

Однако прошла только часть кода. Анализ тестовых примеров показал, что:

Вот и все, что касается кода!

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string,int> hash1;
        for(auto& e : words)
            hash1[e]++;//统计要求的字符串种类
        int n = s.size();
        int len = words[0].size();//固定的字符串长度
        int m = words.size();//数组长度
        for(int i=0; i < len; i++)
        {
            unordered_map<string,int> hash2;
            int count = 0;
            for(int left = i, right = i; right <= n -len; right+= len)
            {
                string in = s.substr(right,len);//裁剪字符串
                hash2[in]++;//进窗口
                if(hash2[in] <= hash1[in])
                    count++;//统计当前字符串数量
                if(right - left + 1 > m*len)//判断字符串数量是否大于字符数组
                {
                    string out = s.substr(left,len);
                    if(hash2[out] <= hash1[out])
                        count--;
                    hash2[out]--;//出窗口
                    left += len;
                }
                if(count == m)
                    ret.push_back(left);
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

8. Минимальная покрывающая подстрока

Leetcode 76. Минимальная покрывающая подстрока

Решение этого вопроса аналогично предыдущему вопросу. Он также ищет все символы строки t в строке s, за исключением того, что возвращается наименьшая из найденных строк.

Для решения этой проблемы мы по-прежнему используем скользящее окно + хэш-таблицу.

1. Используйте hash1 для подсчета типа и количества символов в строке t.
2. Скользящее окно: определите исходное положение слева, справа
   а. Войдите в окно
   б. Определите, появляется ли окно.
   в. Обновить результат (нужно только записать начальную позицию и длину строки и, наконец, вырезать подстроку).

Просто запишите в коде начальную позицию и длину строки, и наш код пройдет.

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 };
        for(auto e : t)
            hash1[e]++;//统计t串的字符种类和数量
        int m = t.size();
        int n = s.size();
        int hash2[128] = { 0 };
        int count = 0;
        int start = 0;
        int len = INT_MAX;
        for(int left = 0, right = 0; right < n; right++)
        {
            hash2[s[right]]++;//进窗口
            if(hash2[s[right]] <= hash1[s[right]])//是否更新有效字符
                count++;
            while(count >= m)//是否出窗口
            {
                if(count == m)//找到符合种类的子串
                {
                    //取长度小的一个
                    int curlen = right - left + 1;
                    if(curlen < len)
                    {
                        start = left;
                        len = curlen;
                    }
                }
                //出窗口
                if(hash2[s[left]] <= hash1[s[left]])
                    count--;
                hash2[s[left]]--;
                left++;
            }
        }
        if(len == INT_MAX)
            return "";
        else
            return s.substr(start,len);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42