Teknologian jakaminen

【leetcode】 Liukuikkunan aihe

2024-07-12

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

Lisää kuvan kuvaus tähän

1. Alaryhmä minimipituudella

Lisää kuvan kuvaus tähän
leetcode 209. Subarray minimipituudella

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

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

Lisää kuvan kuvaus tähän

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.

Lisää kuvan kuvaus tähän
Tarkat vaiheet laskennan optimoimiseksi ovat seuraavat:

Lisää kuvan kuvaus tähän

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:
Lisää kuvan kuvaus tähän
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.
Lisää kuvan kuvaus tähän
Analysoi lyhyesti seuraavaa aikamonimutkaisuutta: koodista se näyttää olevan O(n2).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ä

Lisää kuvan kuvaus tähän
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.
Lisää kuvan kuvaus tähän
Huomasimme, että myös raa'an voiman laskentamenetelmä voi mennä läpi
Lisää kuvan kuvaus tähän

Onko parempaa ratkaisua?Analysoidaan se
Lisää kuvan kuvaus tähän
Eikö yllä oleva ratkaisu ole vain liukuikkuna?
Lisää kuvan kuvaus tähän

Onko aikakompleksisuus O(n) tällä hetkellä parempi kuin väkivaltaisen laskennan O(n)?2) 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

Lisää kuvan kuvaus tähän
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.
Lisää kuvan kuvaus tähän
Lisää kuvan kuvaus tähän
Näin koodimme kulkee
Lisää kuvan kuvaus tähän

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

Lisää kuvan kuvaus tähän
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.

Lisää kuvan kuvaus tähän
Edellisen kysymyksen tapaan käytä liukuvaa ikkunaa.

Lisää kuvan kuvaus tähän

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

Lisää kuvan kuvaus tähän
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

Lisää kuvan kuvaus tähän
Mistä tiedän, kuinka monta hedelmää poimitaan parhaillaan? ---- Käytä hash-taulukon tilastoja
Lisää kuvan kuvaus tähän
Voimme havaita, että hash-taulukoiden käyttö on edelleen melko suuri. Voiko sitä optimoida edelleen?

Kysymysvaatimuksista näkyy, että luokka on alle 105, joten voimme käyttää suoraan taulukkoa + muuttujaa (tietuetyyppi)
Lisää kuvan kuvaus tähän

Tällä tavalla tehokkuutemme on parantunut paljon.
Lisää kuvan kuvaus tähän

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

Lisää kuvan kuvaus tähän

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:
Lisää kuvan kuvaus tähän
Lisää kuvan kuvaus tähän

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] &lt;= hash1[oikea], "kelvollisten merkkien" tyypit lisääntyvät
    b. Jos hash2[oikea] &gt; hash2[oikea], "kelvollisten merkkien" tyyppi pysyy muuttumattomana

Lisää kuvan kuvaus tähän
Väkivaltainen laskentamenetelmä on todellakin käyttökelpoinen, mutta se on suhteellisen tehoton.
Koska etsimme jatkuvaa intervallia, voimmeko käyttää liukuvaa ikkunaa?kokeillaan
Lisää kuvan kuvaus tähän
Näin tehokkuutemme on paljon suurempi
Lisää kuvan kuvaus tähän

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

Lisää kuvan kuvaus tähän

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.
Lisää kuvan kuvaus tähän

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

Lisää kuvan kuvaus tähän
Kuitenkin vain osa koodista läpäisi sen testitapauksia analysoimalla havaittiin, että
Lisää kuvan kuvaus tähän
Tämä on koodi!

Lisää kuvan kuvaus tähän

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

Lisää kuvan kuvaus tähän
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)

Lisää kuvan kuvaus tähän

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

Lisää kuvan kuvaus tähän

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