Compartilhamento de tecnologia

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

1. Subarray com comprimento mínimo

leetcode 209. Subarray com comprimento mínimo

Ao ver este tópico, a primeira coisa que vem à mente é a enumeração violenta, então vamos tentar enumerar o seguinte:

Obviamente, o tempo limite do método de enumeração de força bruta expirará.

Então, existe alguma maneira de otimizá-lo para que não expire? Vamos analisar:

Na enumeração violenta, nossa direita retornará sempre à próxima posição de esquerda e depois renumerará junto com a esquerda.

As etapas específicas para otimizar a enumeração são as seguintes:

No processo de enumeração acima, nossa caixa azul é como uma janela deslizante de tamanho não fixo. Chamamos esse método.janela deslizante

Para janelas deslizantes nada mais é do que os seguintes passos:

O ponto de partida de cada janela de perguntas e a posição dos resultados atualizados não são fixos, sendo a situação específica analisada caso a caso.

De acordo com o método da janela deslizante, nosso código não atingirá o tempo limite.

Analise brevemente a seguinte complexidade de tempo: Pelo código parece ser O(n²), mas devido à nossa ideia de janela deslizante, os dois ponteiros percorrem na mesma direção e não voltam quando o ponteiro direito termina, o loop termina, então é;A complexidade do tempo é 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. A substring mais longa sem caracteres repetidos

leetcode 3. A string mais longa sem caracteres repetidos

O primeiro método que vem à mente para esta questão é, sem dúvida, a enumeração e, em seguida, contar o número de vezes que cada caractere aparece duas vezes, então a string correspondente ao caractere atual é a substring mais longa;

Descobrimos que o método de enumeração de força bruta também pode passar

Existe uma solução melhor?Vamos analisar isso

A solução acima não é apenas uma janela deslizante?

A complexidade de tempo O(n) neste momento é melhor do que a da enumeração violenta O(n)?²) é ainda melhor

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. Número máximo de 1’s III consecutivos

leetcode 1004. Número máximo de 1's III consecutivos

A partir da análise do tema, podemos perceber queO fato de 0 poder ser invertido significa: 0 pode ser usado como 1 . Então nosso objetivo é encontrar um intervalo que contenha o maior número de 1's, e o número de 0's neste intervalo não pode exceder k.

O método de enumeração violenta para esta questão não será demonstrado. Vamos diretamente para a janela deslizante.


Desta forma nosso código passará

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. Número mínimo de operações para reduzir x a 0

leetcode 1658. Número mínimo de operações para reduzir x a 0

Ao ler as perguntas, podemos descobrir que está no lado esquerdo e no lado direito. É difícil controlá-lo?
O oposto é verdadeiro quando é difícil

• Encontramos um intervalo contínuo na matriz, removemos o conteúdo do intervalo contínuo na matriz e o conteúdo restante é exatamente igual a x, então encontramos uma situação
• Este intervalo contínuo éSoma dos elementos da matriz menos x
• Quando o intervalo contínuo mais longo é encontrado na matriz, encontramos a melhor solução.

Ainda como na pergunta anterior, use uma janela deslizante.

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. Cestas de frutas

leetcode 904.Frutas na cesta

Este título é tão longo, o que significa?

Existem apenas duas cestas, e só pode haver dois tipos de frutas nas cestas, e elas não podem cruzar árvores. Encontre o número máximo de árvores pelas quais você pode passar.
Ou seja, para encontrar a duração de um intervalo contínuo, podemos usar uma janela deslizante.

Então, como posso saber quantas frutas estão sendo colhidas atualmente? ----Use estatísticas de tabela hash

Podemos descobrir que o consumo do uso de tabelas hash ainda é muito grande. Pode ser otimizado ainda mais?

Pode-se observar pelos requisitos da pergunta que a categoria é inferior a 10⁵, então podemos usar diretamente um array + uma variável (tipo de registro)

Dessa forma, nossa eficiência melhorou muito.

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. Encontre todos os anagramas de letras na string

leetcode 438. Encontre todos os anagramas de letras em uma string

A partir da análise da questão, podemos ver que se trata de encontrar a string p na string s (a ordem dos caracteres na string p pode ser interrompida).
Então nós podemosBasta encontrar uma substring cujo comprimento seja igual a p e cujo tipo de caractere e número sejam iguais à string p.。

Portanto, podemos usar duas tabelas hash para contar os tipos e números de caracteres na string p e na string s, respectivamente.

Então vamos tentar primeiro usando enumeração violenta:

Como as duas tabelas hash são comparadas?

1. Primeiro, use hash1 para registrar o número de tipos de caracteres na string p.
2. Percorra s e encontre a substring cujo comprimento é igual a p, e hash2 armazena o caractere atual.
   a. Se hash2[right] <= hash1[right], os tipos de "caracteres válidos" aumentam
   b. Se hash2[right] > hash2[right], o tipo de "caracteres válidos" permanece inalterado.

O método de enumeração violenta é de facto viável, mas é relativamente ineficiente.
Como procuramos um intervalo contínuo, podemos usar uma janela deslizante?vamos tentar

Assim nossa eficiência será muito maior

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. Concatenar substrings de todas as palavras

leetcode 30. Concatenar substrings de todas as palavras

Esta questão é semelhante à anterior, exceto que os caracteres são substituídos por strings. Portanto, ainda usamos: janela deslizante + tabela hash para resolver o problema.

Etapas de resolução de problemas:

1. Primeiro use hash1 para contar os tipos de strings em palavras
2. Use uma janela deslizante (como o comprimento da corda é fixo, você pode pular o comprimento diretamente)
   a. Início da definição: esquerda, direita
   b.Quando a string entra na janela, você precisa usar a função de string substr para cortá-la.
   c. Determine o tipo de string
   Se deve sair da janela
   Atualizar resultados

No entanto, apenas parte do código foi aprovada. A análise de seus casos de teste descobriu que,

É isso para o código!

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. Substring de cobertura mínima

leetcode 76. Substring de cobertura mínima

A solução para esta questão é semelhante à questão anterior. Ela também procura todos os caracteres da string t na string s, exceto que a menor das strings encontradas é retornada.

Ainda usamos janela deslizante + tabela hash para resolver isso.

1. Use hash1 para contar o tipo e o número de caracteres na string t
2. Janela deslizante: defina a posição inicial esquerda, direita
   a. Entre na janela
   b. Determine se uma janela aparece
   c. Atualize o resultado (só é necessário registrar a posição inicial e o comprimento da string e, finalmente, cortar a substring)

Basta registrar a posição inicial e o comprimento da string no código e nosso código será aprovado.

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