Compartir tecnología

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

1. Subarreglo con longitud mínima

leetcode 209. Submatriz con longitud mínima

Al ver este tema, lo primero que me viene a la mente es una enumeración violenta, así que intentemos enumerar lo siguiente:

Obviamente, el método de enumeración de fuerza bruta expirará.

Entonces, ¿hay alguna forma de optimizarlo para que no se agote el tiempo de espera? Analicémoslo:

En una enumeración violenta, nuestra derecha volverá a la siguiente posición de la izquierda cada vez y luego volverá a enumerarse junto con la izquierda.

Los pasos específicos para optimizar la enumeración son los siguientes:

En el proceso de enumeración anterior, nuestro cuadro azul es como una ventana deslizante con un tamaño no fijo. Llamamos a este método.ventana deslizante

Para ventanas correderas, no son más que los siguientes pasos:

El punto de partida de cada ventana de preguntas y la posición de los resultados actualizados no son fijos, y la situación específica se analizará caso por caso.

Según el método de ventana deslizante, nuestro código no expirará.

Analice brevemente la siguiente complejidad temporal: según el código parece ser O (n²), pero debido a nuestra idea de ventana deslizante, los dos punteros atraviesan en la misma dirección y no retrocederán cuando finalice el puntero derecho, el ciclo finaliza, por lo que es;La complejidad del tiempo es 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. La subcadena más larga sin caracteres repetidos.

leetcode 3. La cadena más larga sin caracteres repetidos

El primer método que me viene a la mente para esta pregunta es, sin duda, la enumeración y luego contar el número de veces que aparece cada carácter. Si un carácter aparece dos veces, entonces la cadena correspondiente al carácter actual es la subcadena más larga;

Descubrimos que el método de enumeración de fuerza bruta también puede pasar

¿Existe una solución mejor?analicémoslo

¿No es la solución anterior sólo una ventana corredera?

¿Es la complejidad temporal O (n) en este momento mejor que la de la enumeración violenta O (n)?²) es aún mejor

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 unos consecutivos III

leetcode 1004. Número máximo de unos consecutivos III

Analizando el tema podemos ver queEl hecho de que 0 se pueda invertir significa que 0 se puede utilizar como 1 . Entonces nuestro objetivo es encontrar un intervalo que contenga el mayor número de unos, y el número de ceros en este intervalo no puede exceder k.

No se demostrará el método de enumeración violenta para esta pregunta. Vayamos directamente a la ventana deslizante.


De esta manera nuestro código pasará

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 operaciones para reducir x a 0

leetcode 1658. Número mínimo de operaciones para reducir x a 0

Al leer las preguntas, podemos encontrar que está en el lado izquierdo y en el lado derecho. ¿Es difícil controlarlo? Entonces, ¿qué debemos hacer?
Lo contrario ocurre cuando es difícil.

• Encontramos un intervalo continuo en la matriz, eliminamos el contenido del intervalo continuo en la matriz y el contenido restante es exactamente igual a x, entonces, ¿hemos encontrado una situación?
• Este intervalo continuo esSuma de elementos en matriz menos x
• Cuando se encuentra el intervalo continuo más largo en la matriz, hemos encontrado la mejor solución.

Aún así como en la pregunta anterior, use una ventana corrediza.

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 en cesta

Este título es tan largo, ¿qué significa?

Sólo hay dos cestas, y sólo puede haber dos tipos de frutas en las cestas, y no pueden cruzar árboles. Encuentra el número máximo de árboles que puedes pasar.
Es decir, para encontrar la longitud de un intervalo continuo. Podemos usar una ventana deslizante.

Entonces, ¿cómo sé cuántas frutas se están recolectando actualmente? ----Usar estadísticas de tabla hash

Podemos encontrar que el consumo de uso de tablas hash sigue siendo bastante grande. ¿Se puede optimizar aún más?

Se puede ver en los requisitos de la pregunta que la categoría es inferior a 10.⁵, entonces podemos usar directamente una matriz + una variable (tipo de registro)

De esta forma, nuestra eficiencia ha mejorado mucho.

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. Encuentra todos los anagramas de letras en la cadena.

leetcode 438. Encuentra todos los anagramas de letras en una cadena

Del análisis de la pregunta, podemos ver que se trata de encontrar la cadena p en la cadena s (el orden de los caracteres en la cadena p puede alterarse).
Entonces podemosSimplemente busque una subcadena cuya longitud sea igual a p, y cuyo tipo de carácter y número sean iguales a p cadena.。

Entonces podemos usar dos tablas hash para contar los tipos y números de caracteres en la cadena p y la cadena s respectivamente.

Entonces intentémoslo primero usando enumeración violenta:

¿Cómo se comparan las dos tablas hash?

1. Primero, use hash1 para registrar la cantidad de tipos de caracteres en la cadena p.
2. Atraviese sy encuentre la subcadena cuya longitud sea igual a p, y hash2 almacena el carácter actual.
   a. Si hash2[right] <= hash1[right], los tipos de "caracteres válidos" aumentan.
   b. Si hash2[derecha] > hash2[derecha], el tipo de "caracteres válidos" permanece sin cambios.

El método de enumeración violenta es realmente factible, pero relativamente ineficiente.
Dado que buscamos un intervalo continuo, ¿podemos usar una ventana deslizante?Vamos a intentarlo

De esta manera nuestra eficiencia será mucho mayor.

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 subcadenas de todas las palabras.

leetcode 30. Concatenar subcadenas de todas las palabras

Esta pregunta es similar a la pregunta anterior, excepto que los caracteres se reemplazan por cadenas. Por lo tanto, todavía usamos: ventana deslizante + tabla hash para resolver el problema.

Pasos para resolver el problema:

1. Primero use hash1 para contar los tipos de cadenas en palabras
2. Utilice una ventana deslizante (dado que la longitud de la cuerda es fija, puede saltar la longitud directamente)
   a. Inicio de la definición: izquierda, derecha.
   b Cuando la cadena ingresa a la ventana, debe usar la función de cadena substr para cortarla.
   c. Determinar el tipo de cuerda.
   Ya sea para salir de la ventana
   Actualizar resultados

Sin embargo, solo se aprobó una parte del código. Al analizar sus casos de prueba, se encontró que:

¡Este es el 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. Subcadena de cobertura mínima

leetcode 76. Subcadena de cobertura mínima

La solución a esta pregunta es similar a la pregunta anterior. También busca todos los caracteres de la cadena t en la cadena s, excepto que se devuelve la más pequeña de las cadenas encontradas.

Seguimos usando ventana deslizante + tabla hash para resolverlo.

1. Utilice hash1 para contar el tipo y la cantidad de caracteres en la cadena t
2. Ventana deslizante: define la posición inicial izquierda, derecha
   a. Ingrese a la ventana
   b. Determinar si aparece una ventana
   c. Actualice el resultado (solo es necesario registrar la posición inicial y la longitud de la cadena y finalmente cortar la subcadena)

Simplemente registre la posición inicial y la longitud de la cadena en el código, y nuestro código terminará.

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