2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
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(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;
}
};
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)?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;
}
};
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;
}
};
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
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;
}
};
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 105, 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;
}
};
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?
- Ensinnäkin käytä hash1:tä tallentaaksesi p-merkkijonon merkkityyppien lukumäärän.
- 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;
}
};
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:
- Käytä ensin hash1:tä laskeaksesi merkkijonotyypit sanoissa
- 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;
}
};
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.
- Käytä hash1:tä laskeaksesi t-merkkijonon merkkien tyypin ja määrän
- 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);
}
};