Partage de technologie

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

1. Sous-tableau avec une longueur minimale

leetcode 209. Sous-tableau avec une longueur minimale

En voyant ce sujet, la première chose qui nous vient à l’esprit est l’énumération violente, essayons donc d’énumérer ce qui suit :

De toute évidence, la méthode d’énumération par force brute expirera.

Alors, existe-t-il un moyen de l'optimiser pour qu'il n'expire pas ? Analysons-le :

Lors d'un dénombrement violent, notre droite reviendra à chaque fois à la position suivante de gauche, puis re-énumérera avec la gauche.

Les étapes spécifiques pour optimiser le dénombrement sont les suivantes :

Dans le processus d'énumération ci-dessus, notre boîte bleue est comme une fenêtre coulissante de taille non fixe. Nous appelons cette méthode.fenêtre coulissante

Pour les fenêtres coulissantes, il suffit de suivre les étapes suivantes :

Le point de départ de chaque fenêtre de questions et la position des résultats mis à jour ne sont pas fixes, et la situation spécifique sera analysée au cas par cas.

Selon la méthode de la fenêtre glissante, notre code n'expirera pas.

Analysez brièvement la complexité temporelle suivante : d'après le code, il semble que ce soit O(n²), mais en raison de notre idée de fenêtre coulissante, les deux pointeurs se déplacent dans la même direction et ne reviendront pas en arrière lorsque le pointeur droit se termine, la boucle se termine, donc c'est le cas ;La complexité temporelle est 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 sous-chaîne la plus longue sans caractères répétés

leetcode 3. La chaîne la plus longue sans caractères répétés

La première méthode qui vient à l'esprit pour cette question est sans aucun doute l'énumération, puis le comptage du nombre de fois où chaque caractère apparaît ; si un caractère apparaît deux fois, alors la chaîne correspondant au caractère actuel est la sous-chaîne la plus longue ;

Nous avons constaté que la méthode d'énumération par force brute peut également passer

Existe-t-il une meilleure solution ?Analysons-le

La solution ci-dessus n’est-elle pas simplement une fenêtre coulissante ?

La complexité temporelle O(n) à ce moment-là est-elle meilleure que celle du dénombrement violent O(n) ?²) c'est encore mieux

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. Nombre maximum de 1 consécutifs III

leetcode 1004. Nombre maximum de 1 consécutifs III

En analysant le sujet, nous pouvons voir queLe fait que 0 puisse être inversé signifie : 0 peut être utilisé comme 1 . Notre objectif est ensuite de trouver un intervalle contenant le plus grand nombre de 1, et le nombre de 0 dans cet intervalle ne peut pas dépasser k.

La méthode d’énumération violente pour cette question ne sera pas démontrée. Passons directement à la fenêtre glissante.


De cette façon, notre code passera

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. Nombre minimum d'opérations pour réduire x à 0

leetcode 1658. Nombre minimum d'opérations pour réduire x à 0

En lisant les questions, on constate qu'il est du côté gauche et du côté droit. Est-il difficile de le contrôler ? Alors que faire ?
Le contraire est vrai quand c'est difficile

• Nous trouvons un intervalle continu dans le tableau, supprimons le contenu de l'intervalle continu dans le tableau et le contenu restant est exactement égal à x, alors avons-nous trouvé une situation ?
• Cet intervalle continu estSomme des éléments du tableau moins x
• Lorsque l’intervalle continu le plus long est trouvé dans le tableau, nous avons trouvé la meilleure solution.

Toujours comme la question précédente, utilisez une fenêtre coulissante.

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. Corbeilles de fruits

leetcode 904.Fruits dans le panier

Ce titre est si long, qu'est-ce qu'il signifie ?

Il n'y a que deux paniers, et il ne peut y avoir que deux sortes de fruits dans les paniers, et ils ne peuvent pas traverser les arbres. Trouvez le nombre maximum d'arbres que vous pouvez dépasser.
C'est pour trouver la longueur d'un intervalle continu. Nous pouvons utiliser une fenêtre glissante.

Alors, comment puis-je savoir combien de fruits sont actuellement cueillis ? ----Utiliser les statistiques de la table de hachage

Nous pouvons constater que la consommation liée à l'utilisation des tables de hachage est encore assez importante. Peut-elle être davantage optimisée ?

Il ressort des exigences de la question que la catégorie est inférieure à 10⁵, on peut donc utiliser directement un tableau + une variable (type d'enregistrement)

De cette façon, notre efficacité s’est considérablement améliorée.

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. Recherchez toutes les anagrammes de lettres dans la chaîne

leetcode 438. Rechercher toutes les anagrammes de lettres dans une chaîne

De l'analyse de la question, nous pouvons voir qu'il s'agit de trouver la chaîne p dans la chaîne s (l'ordre des caractères dans la chaîne p peut être perturbé).
Alors nous pouvonsTrouvez simplement une sous-chaîne dont la longueur est égale à p et dont le type de caractère et le numéro sont égaux à la chaîne p.。

Nous pouvons donc utiliser deux tables de hachage pour compter respectivement les types et le nombre de caractères dans la chaîne p et la chaîne s.

Alors essayons d’abord en utilisant une énumération violente :

Comment les deux tables de hachage sont-elles comparées ?

1. Tout d’abord, utilisez hash1 pour enregistrer le nombre de types de caractères dans la chaîne p.
2. Parcourez s et recherchez la sous-chaîne dont la longueur est égale à p, et hash2 stocke le caractère actuel.
   a. Si hash2[right] <= hash1[right], les types de « caractères valides » augmentent
   b. Si hash2[right] > hash2[right], le type de "caractères valides" reste inchangé.

La méthode de dénombrement violente est certes réalisable, mais elle est relativement inefficace.
Puisque nous recherchons un intervalle continu, pouvons-nous utiliser une fenêtre glissante ?essayons

De cette façon, notre efficacité sera beaucoup plus élevée

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. Concaténer les sous-chaînes de tous les mots

leetcode 30. Concaténer les sous-chaînes de tous les mots

Cette question est similaire à la question précédente, sauf que les caractères sont remplacés par des chaînes. Par conséquent, nous utilisons toujours : fenêtre coulissante + table de hachage pour résoudre le problème.

Étapes de résolution de problèmes :

1. Utilisez d'abord hash1 pour compter les types de chaînes dans les mots
2. Utilisez une fenêtre coulissante (la longueur de la corde étant fixe, vous pouvez sauter directement la longueur)
   a. Début de la définition : gauche, droite
   b. Lorsque la chaîne entre dans la fenêtre, vous devez utiliser la fonction de chaîne substr pour la couper.
   c. Déterminer le type de chaîne
   S'il faut quitter la fenêtre
   Mettre à jour les résultats

Cependant, seule une partie du code a été réussie. L'analyse de ses cas de test a révélé que :

C'est le code !

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. Sous-chaîne de couverture minimale

leetcode 76. Sous-chaîne de couverture minimale

La solution à cette question est similaire à la question précédente. Elle recherche également tous les caractères de la chaîne t dans la chaîne s, sauf que la plus petite des chaînes trouvées est renvoyée.

Nous utilisons toujours une fenêtre coulissante + une table de hachage pour le résoudre.

1. Utilisez hash1 pour compter le type et le nombre de caractères dans la chaîne t
2. Fenêtre coulissante : définir la position de départ à gauche, à droite
   a. Entrez dans la fenêtre
   b. Déterminez si une fenêtre apparaît
   c. Mettez à jour le résultat (il suffit d'enregistrer la position de départ et la longueur de la chaîne, et enfin de couper la sous-chaîne)

Enregistrez simplement la position de départ et la longueur de la chaîne dans le code, et notre code sera terminé.

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