Teknologian jakaminen

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

1. Alaryhmä minimipituudella

leetcode 209. Subarray minimipituudella

Tätä aihetta nähdessäsi tulee ensimmäisenä mieleen väkivaltainen luettelointi, joten yritetään luetella seuraavaa:

On selvää, että raa'an voiman laskentamenetelmä aikakatkaistaan.

Onko siis mitään tapaa optimoida sitä niin, ettei se aikakatkaisu? Analysoidaan sitä:

Väkivaltaisessa luetteloinnissa oikeistomme palaa joka kerta seuraavaan vasemman asentoon ja luettelee sitten uudelleen yhdessä vasemman kanssa.

Tarkat vaiheet laskennan optimoimiseksi ovat seuraavat:

Yllä olevassa luettelointiprosessissa sininen laatikkomme on kuin liukuva ikkuna, jonka koko on kiinteä. Kutsumme tätä menetelmääLiukuikkuna

Liukuikkunoissa se ei ole muuta kuin seuraavat vaiheet:

Kunkin kysymysikkunan lähtökohta ja päivitettyjen tulosten sijainti eivät ole kiinteitä, vaan konkreettinen tilanne analysoidaan tapauskohtaisesti.

Liukuikkunamenetelmän mukaan koodimme ei aikakatkaisu.

Analysoi lyhyesti seuraavaa aikamonimutkaisuutta: koodista se näyttää olevan O(n²).Aikamonimutkaisuus on 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. Pisin osamerkkijono ilman toistuvia merkkejä

leetcode 3. Pisin merkkijono ilman toistuvia merkkejä

Ensimmäinen menetelmä, joka tulee mieleen tässä kysymyksessä, on epäilemättä luettelointi ja sen jälkeen kunkin merkin esiintymiskertojen laskeminen, jos merkki esiintyy kahdesti, niin nykyistä merkkiä vastaava merkkijono on pisin.

Huomasimme, että myös raa'an voiman laskentamenetelmä voi mennä läpi

Onko parempaa ratkaisua?Analysoidaan se

Eikö yllä oleva ratkaisu ole vain liukuikkuna?

Onko aikakompleksisuus O(n) tällä hetkellä parempi kuin väkivaltaisen laskennan O(n)?²) on vielä parempi

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. Maksimimäärä peräkkäisiä ykkösiä III

leetcode 1004. Peräkkäisten ykkösten enimmäismäärä III

Aihetta analysoimalla voimme nähdä senSe, että 0 voidaan kääntää, tarkoittaa: 0:ta voidaan käyttää 1:nä . Sitten tavoitteemme on löytää väli, joka sisältää suurimman määrän ykkösiä ja jossa nollien määrä ei saa olla suurempi kuin k.

Tämän kysymyksen väkivaltaista luettelointimenetelmää ei esitetä. Siirrytään suoraan liukuvaan ikkunaan.


Näin koodimme kulkee

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. Toimintojen vähimmäismäärä x:n pienentämiseksi nollaan

leetcode 1658. Toimintojen vähimmäismäärä x:n pienentämiseksi nollaan

Kysymyksiä lukemalla voimme havaita, että se on vasemmalla ja oikealla puolella. Onko sitä vaikea hallita?
Päinvastoin, kun se on vaikeaa

• Löydämme taulukosta jatkuvan intervallin, poistamme jatkuvan aikavälin sisällön taulukosta ja jäljellä oleva sisältö on täsmälleen yhtä suuri kuin x, niin olemmeko löytäneet tilanteen?
• Tämä jatkuva väli onElementtien summa taulukossa miinus x
• Kun taulukosta löytyy pisin jatkuva väli, olemme löytäneet parhaan ratkaisun.

Edellisen kysymyksen tapaan käytä liukuvaa ikkunaa.

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. Hedelmäkorit

leetcode 904. Hedelmät korissa

Tämä otsikko on niin pitkä, mitä se tarkoittaa?

Koreja on vain kaksi, ja koreissa voi olla vain kahdenlaisia ​​hedelmiä, eivätkä ne voi ylittää puita. Löydä enimmäismäärä puita, joita voit ohittaa.
Tämä tarkoittaa jatkuvan aikavälin pituuden löytämistä. Voimme käyttää liukuvaa ikkunaa

Mistä tiedän, kuinka monta hedelmää poimitaan parhaillaan? ---- Käytä hash-taulukon tilastoja

Voimme havaita, että hash-taulukoiden käyttö on edelleen melko suuri. Voiko sitä optimoida edelleen?

Kysymysvaatimuksista näkyy, että luokka on alle 10⁵, joten voimme käyttää suoraan taulukkoa + muuttujaa (tietuetyyppi)

Tällä tavalla tehokkuutemme on parantunut paljon.

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. Etsi kaikki kirjainanagrammit merkkijonosta

leetcode 438. Etsi kaikki kirjainanagrammit merkkijonosta

Kysymyksen analyysistä voimme nähdä, että se on löytää p-merkkijono s-merkkijonosta (p-merkkijonon merkkien järjestys voi olla häiriintynyt).
Sitten voimmeEtsi vain osamerkkijono, jonka pituus on yhtä suuri kuin p ja jonka merkkityyppi ja numero ovat yhtä kuin p-merkkijono.。

Joten voimme käyttää kahta hash-taulukkoa laskeaksemme merkkijonon p ja merkkijonon s merkkien tyypit ja lukumäärät.

Kokeillaan sitten ensin käyttämällä väkivaltaista luettelointia:

Miten kahta hash-taulukkoa verrataan?

1. Ensinnäkin käytä hash1:tä tallentaaksesi p-merkkijonon merkkityyppien lukumäärän.
2. Kulje s ja etsi osamerkkijono, jonka pituus on yhtä suuri kuin p, ja hash2 tallentaa nykyisen merkin.
   a. Jos hash2[oikea] <= hash1[oikea], "kelvollisten merkkien" tyypit lisääntyvät
   b. Jos hash2[oikea] > hash2[oikea], "kelvollisten merkkien" tyyppi pysyy muuttumattomana

Väkivaltainen laskentamenetelmä on todellakin käyttökelpoinen, mutta se on suhteellisen tehoton.
Koska etsimme jatkuvaa intervallia, voimmeko käyttää liukuvaa ikkunaa?kokeillaan

Näin tehokkuutemme on paljon suurempi

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. Liitä kaikkien sanojen osamerkkijonot

leetcode 30. Liitä kaikkien sanojen osamerkkijonot

Tämä kysymys on samanlainen kuin edellinen kysymys, paitsi että merkit korvataan merkkijonoilla. Siksi käytämme edelleen: liukuva ikkuna + hash-taulukko ongelman ratkaisemiseksi.

Ongelmanratkaisuvaiheet:

1. Käytä ensin hash1:tä laskeaksesi merkkijonotyypit sanoissa
2. Käytä liukuvaa ikkunaa (koska merkkijonon pituus on kiinteä, voit hypätä pituutta suoraan)
   a. Määritelmän alku: vasen, oikea
   b. Kun merkkijono tulee ikkunaan, sinun on käytettävä merkkijonofunktiota substr sen leikkaamiseen.
   c. Määritä merkkijonon tyyppi
   Poistuako ikkunasta
   Päivitä tulokset

Kuitenkin vain osa koodista läpäisi sen testitapauksia analysoimalla havaittiin, että

Tämä on koodi!

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. Pienin peittävä osamerkkijono

leetcode 76. Vähintään kattava osamerkkijono

Ratkaisu tähän kysymykseen on samanlainen kuin edellinen. Se etsii myös kaikki merkkijonon t merkit merkkijonosta s, paitsi että pienin löydetyistä merkkijonoista palautetaan.

Käytämme edelleen liukuvaa ikkunaa + hash-taulukkoa sen ratkaisemiseen.

1. Käytä hash1:tä laskeaksesi t-merkkijonon merkkien tyypin ja määrän
2. Liukuikkuna: määritä aloitusasento vasemmalle, oikealle
   a. Siirry ikkunaan
   b. Selvitä, tuleeko ikkuna näkyviin
   c. Päivitä tulos (täytyy tallentaa vain merkkijonon aloituspaikka ja pituus ja lopuksi leikata osamerkkijono)

Kirjoita vain merkkijonon aloituspaikka ja pituus koodiin, niin koodimme on ohi.

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