Condivisione della tecnologia

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

1. Sottoarray con lunghezza minima

leetcode 209. Sottoarray con lunghezza minima

Quando si vede questo argomento, la prima cosa che viene in mente è l'enumerazione violenta, quindi proviamo a enumerare quanto segue:

Ovviamente, il metodo di enumerazione della forza bruta scadrà.

Quindi esiste un modo per ottimizzarlo in modo che non scada? Analizziamolo:

Nell'enumerazione violenta, la nostra destra tornerà ogni volta alla posizione successiva di sinistra, quindi enumererà nuovamente insieme alla sinistra.

I passaggi specifici per ottimizzare l'enumerazione sono i seguenti:

Nel processo di enumerazione precedente, la nostra casella blu è come una finestra scorrevole con una dimensione non fissa. Chiamiamo questo metodofinestra scorrevole

Per le finestre scorrevoli, non è altro che i seguenti passaggi:

Il punto di partenza di ciascuna finestra di domanda e la posizione dei risultati aggiornati non sono fissi e la situazione specifica verrà analizzata caso per caso.

Secondo il metodo della finestra scorrevole, il nostro codice non scade.

Analizzare brevemente la seguente complessità temporale: Dal codice sembra essere O(n²), ma a causa della nostra idea di finestra scorrevole, i due puntatori si spostano nella stessa direzione e non tornano indietro quando termina il puntatore destro, il ciclo termina, quindi è così;La complessità temporale è 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 sottostringa più lunga senza caratteri ripetuti

leetcode 3. La stringa più lunga senza caratteri ripetuti

Il primo metodo che mi viene in mente per questa domanda è senza dubbio l'enumerazione, e quindi il conteggio del numero di volte in cui ogni carattere appare due volte, allora la stringa corrispondente al carattere corrente è la sottostringa più lunga;

Abbiamo scoperto che anche il metodo di enumerazione della forza bruta può passare

C'è una soluzione migliore?Analizziamolo

La soluzione di cui sopra non è solo una finestra scorrevole?

La complessità temporale O(n) in questo momento è migliore di quella dell'enumerazione violenta O(n)?²) è ancora meglio

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. Numero massimo di 1 consecutivi III

leetcode 1004. Numero massimo di 1 consecutivi III

Dall’analisi dell’argomento, lo vediamoIl fatto che 0 possa essere invertito significa che 0 può essere utilizzato come 1 . Quindi il nostro obiettivo è trovare un intervallo che contenga il maggior numero di 1 e il numero di 0 in questo intervallo non può superare k.

Il metodo di enumerazione violenta per questa domanda non verrà dimostrato. Andiamo direttamente alla finestra scorrevole.


In questo modo il nostro codice passerà

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. Numero minimo di operazioni per ridurre x a 0

leetcode 1658. Numero minimo di operazioni per ridurre x a 0

Leggendo le domande, possiamo scoprire che è sul lato sinistro e sul lato destro. È difficile controllarlo. Allora cosa dovremmo fare?
È vero il contrario quando è difficile

• Troviamo un intervallo continuo nell'array, rimuoviamo il contenuto dell'intervallo continuo nell'array e il contenuto rimanente è esattamente uguale a x, quindi abbiamo trovato una situazione
• Questo intervallo continuo èSomma degli elementi nell'array meno x
• Quando nell'array viene trovato l'intervallo continuo più lungo, abbiamo trovato la soluzione migliore.

Ancora come la domanda precedente, usa una finestra scorrevole.

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. Cesti di frutta

leetcode 904.Frutta nel cestino

Questo titolo è troppo lungo, cosa significa?

Ci sono solo due cesti e possono esserci solo due tipi di frutta nei cesti e non possono attraversare gli alberi. Trova il numero massimo di alberi che puoi superare.
Cioè per trovare la lunghezza di un intervallo continuo possiamo usare una finestra scorrevole

Allora come faccio a sapere quanti frutti vengono attualmente raccolti? ----Utilizza le statistiche della tabella hash

Possiamo scoprire che il consumo dell'utilizzo delle tabelle hash è ancora piuttosto elevato. È possibile ottimizzarlo ulteriormente?

Dai requisiti della domanda si può vedere che la categoria è inferiore a 10⁵, quindi possiamo usare direttamente un array + una variabile (tipo record)

In questo modo, la nostra efficienza è migliorata molto.

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. Trova tutti gli anagrammi di lettere nella stringa

leetcode 438. Trova tutti gli anagrammi di lettere in una stringa

Dall'analisi della domanda, possiamo vedere che si tratta di trovare la stringa p nella stringa s (l'ordine dei caratteri nella stringa p può essere interrotto).
Allora possiamoBasta trovare una sottostringa la cui lunghezza sia uguale a p e il cui tipo e numero di carattere siano uguali a p stringa.。

Quindi possiamo usare due tabelle hash per contare rispettivamente i tipi e i numeri di caratteri nella stringa p e nella stringa s.

Quindi proviamolo prima utilizzando l'enumerazione violenta:

Come vengono confrontate le due tabelle hash?

1. Innanzitutto, usa hash1 per registrare il numero di tipi di caratteri nella stringa p.
2. Attraversa s e trova la sottostringa la cui lunghezza è uguale a p, e hash2 memorizza il carattere corrente.
   a.Se hash2[right] <= hash1[right], i tipi di "caratteri validi" aumentano
   b. Se hash2[right] > hash2[right], il tipo di "caratteri validi" rimane invariato

Il metodo di enumerazione violenta è effettivamente fattibile, ma è relativamente inefficiente.
Poiché stiamo cercando un intervallo continuo, possiamo utilizzare una finestra scorrevole?Proviamolo

In questo modo la nostra efficienza sarà molto più elevata

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. Concatena le sottostringhe di tutte le parole

leetcode 30. Concatena le sottostringhe di tutte le parole

Questa domanda è simile alla domanda precedente, tranne per il fatto che i caratteri vengono sostituiti da stringhe. Pertanto, utilizziamo ancora: finestra scorrevole + tabella hash per risolvere il problema.

Passaggi per la risoluzione del problema:

1. Per prima cosa usa hash1 per contare i tipi di stringhe in parole
2. Usa una finestra scorrevole (poiché la lunghezza della corda è fissa, puoi saltare direttamente la lunghezza)
   a. Inizio definizione: sinistra, destra
   b. Quando la stringa entra nella finestra, è necessario utilizzare la funzione stringa substr per tagliarla.
   c. Determinare il tipo di stringa
   Se uscire dalla finestra
   Aggiorna i risultati

Tuttavia, solo una parte del codice è stata superata. L'analisi dei casi di test ha rilevato che,

Questo è tutto per il codice!

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. Sottostringa di copertura minima

leetcode 76. Sottostringa di copertura minima

La soluzione a questa domanda è simile alla domanda precedente. Cerca anche tutti i caratteri della stringa t nella stringa s, tranne che viene restituita la più piccola delle stringhe trovate.

Utilizziamo ancora la finestra scorrevole + tabella hash per risolverlo.

1. Usa hash1 per contare il tipo e il numero di caratteri nella stringa t
2. Finestra scorrevole: definisce la posizione iniziale sinistra, destra
   a. Entra nella finestra
   b. Determinare se viene visualizzata una finestra
   c. Aggiorna il risultato (è sufficiente registrare la posizione iniziale e la lunghezza della stringa e infine tagliare la sottostringa)

Basta registrare la posizione iniziale e la lunghezza della stringa nel codice e il nostro codice passerà.

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