2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Leetcode 209. Subarray mit minimaler Länge
Wenn man sich dieses Thema anschaut, fällt einem als Erstes die gewalttätige Aufzählung ein. Versuchen wir also, Folgendes aufzuzählen:
Offensichtlich kommt es bei der Brute-Force-Aufzählungsmethode zu einer Zeitüberschreitung.
Gibt es also eine Möglichkeit, es so zu optimieren, dass es nicht zu einer Zeitüberschreitung kommt? Lassen Sie es uns analysieren:
Bei einer heftigen Aufzählung kehrt unsere Rechte jedes Mal zur nächsten Position der Linken zurück und zählt dann zusammen mit der Linken erneut auf.
Die spezifischen Schritte zur Optimierung der Aufzählung sind wie folgt:
Im obigen Aufzählungsprozess ist unsere blaue Box wie ein Schiebefenster mit nicht festgelegter Größe. Wir nennen diese MethodeSchiebefenster
Bei Schiebefenstern sind es nichts weiter als die folgenden Schritte:
Der Ausgangspunkt jedes Fragefensters und die Position der aktualisierten Ergebnisse sind nicht festgelegt und die spezifische Situation wird von Fall zu Fall analysiert.
Gemäß der Schiebefenstermethode kommt es bei unserem Code nicht zu einer Zeitüberschreitung.
Analysieren Sie kurz die folgende Zeitkomplexität: Aus dem Code geht hervor, dass sie O(n) ist2), aber aufgrund unserer Schiebefenster-Idee bewegen sich die beiden Zeiger in die gleiche Richtung und gehen nicht zurück, wenn der rechte Zeiger endet, also endet die SchleifeDie Zeitkomplexität beträgt 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. Die längste Zeichenfolge ohne wiederholte Zeichen
Die erste Methode, die mir für diese Frage in den Sinn kommt, ist zweifellos die Aufzählung und das anschließende Zählen, wie oft jedes Zeichen vorkommt. Wenn ein Zeichen zweimal vorkommt, ist die Zeichenfolge, die dem aktuellen Zeichen entspricht, die längste Teilzeichenfolge.
Wir haben festgestellt, dass auch die Brute-Force-Aufzählungsmethode erfolgreich sein kann
Gibt es eine bessere Lösung?Lassen Sie es uns analysieren
Ist die obige Lösung nicht nur ein Schiebefenster?
Ist die Zeitkomplexität O(n) zu diesem Zeitpunkt besser als die der gewaltsamen Aufzählung O(n)?2) ist sogar noch besser
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. Maximale Anzahl aufeinanderfolgender Einsen III
Wenn wir das Thema analysieren, können wir das sehenDie Tatsache, dass 0 umgedreht werden kann, bedeutet: 0 kann als 1 verwendet werden . Dann besteht unser Ziel darin, ein Intervall zu finden, das die größte Anzahl an Einsen enthält, und die Anzahl der Nullen in diesem Intervall darf k nicht überschreiten.
Die gewalttätige Aufzählungsmethode für diese Frage wird nicht demonstriert. Gehen wir direkt zum Schiebefenster.
Auf diese Weise wird unser Code übergeben
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. Mindestanzahl von Operationen, um x auf 0 zu reduzieren
Wenn wir die Fragen lesen, können wir feststellen, dass es auf der linken Seite ist und es auf der rechten Seite schwierig ist, es zu kontrollieren.
Das Gegenteil ist der Fall, wenn es schwierig ist
Verwenden Sie wie bei der vorherigen Frage ein Schiebefenster.
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;
}
};
Dieser Titel ist so lang, was bedeutet er?
Es gibt nur zwei Körbe und es können nur zwei Arten von Früchten in den Körben sein, und sie können keine Bäume überqueren. Finden Sie die maximale Anzahl an Bäumen, an denen Sie vorbeikommen können.
Um die Länge eines kontinuierlichen Intervalls zu ermitteln, können wir ein Schiebefenster verwenden
Woher weiß ich also, wie viele Früchte gerade gepflückt werden? ----Hash-Tabellenstatistiken verwenden
Wir können feststellen, dass der Verbrauch bei der Verwendung von Hash-Tabellen immer noch recht hoch ist. Kann er weiter optimiert werden?
Aus den Fragenanforderungen geht hervor, dass die Kategorie kleiner als 10 ist5, sodass wir direkt ein Array + eine Variable (Datensatztyp) verwenden können.
Auf diese Weise hat sich unsere Effizienz erheblich verbessert.
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. Finden Sie alle Buchstabenanagramme in einer Zeichenfolge
Aus der Analyse der Frage können wir ersehen, dass es darum geht, die p-Zeichenfolge in der s-Zeichenfolge zu finden (die Reihenfolge der Zeichen in der p-Zeichenfolge kann gestört sein).
Dann können wirSuchen Sie einfach eine Teilzeichenfolge, deren Länge p entspricht und deren Zeichentyp und Anzahl der p-Zeichenfolge entsprechen.。
Wir können also zwei Hash-Tabellen verwenden, um die Typen und die Anzahl der Zeichen in den Zeichenfolgen p bzw. s zu zählen.
Dann versuchen wir es zunächst mit der gewalttätigen Aufzählung:
Wie werden die beiden Hash-Tabellen verglichen?
- Verwenden Sie zunächst hash1, um die Anzahl der Zeichentypen in der p-Zeichenfolge aufzuzeichnen.
- Durchlaufen Sie s und finden Sie die Teilzeichenfolge, deren Länge p entspricht, und Hash2 speichert das aktuelle Zeichen.
a. Wenn hash2[right] <= hash1[right], erhöht sich die Anzahl der „gültigen Zeichen“.
b. Wenn hash2[right] > hash2[right], bleibt der Typ der „gültigen Zeichen“ unverändert
Die gewaltsame Aufzählungsmethode ist zwar machbar, aber relativ ineffizient.
Können wir ein Schiebefenster verwenden, da wir nach einem kontinuierlichen Intervall suchen?Lass es uns versuchen
Auf diese Weise wird unsere Effizienz viel höher sein
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. Teilzeichenfolgen aller Wörter verketten
Diese Frage ähnelt der vorherigen Frage, außer dass die Zeichen durch Zeichenfolgen ersetzt werden. Daher verwenden wir weiterhin: Schiebefenster + Hash-Tabelle, um das Problem zu lösen.
Schritte zur Problemlösung:
- Verwenden Sie zunächst hash1, um die Zeichenfolgentypen in Wörtern zu zählen
- Verwenden Sie ein Schiebefenster (da die Länge der Zeichenfolge fest ist, können Sie die Länge direkt überspringen)
a. Definitionsanfang: links, rechts
b. Wenn die Zeichenfolge in das Fenster gelangt, müssen Sie sie mit der Zeichenfolgenfunktion substr ausschneiden.
c. Bestimmen Sie die Art der Zeichenfolge
Ob das Fenster verlassen werden soll
Ergebnisse aktualisieren
Bei der Analyse seiner Testfälle wurde jedoch festgestellt, dass nur ein Teil des Codes bestanden hat.
Das ist der 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;
}
};
Leetcode 76. Minimaler abdeckender Teilstring
Die Lösung dieser Frage ähnelt der vorherigen Frage. Es wird auch nach allen Zeichen der Zeichenfolge t in der Zeichenfolge s gesucht, mit der Ausnahme, dass die kleinste der gefundenen Zeichenfolgen zurückgegeben wird.
Wir verwenden immer noch Schiebefenster + Hash-Tabelle, um das Problem zu lösen.
- Verwenden Sie hash1, um den Typ und die Anzahl der Zeichen im T-String zu zählen
- Schiebefenster: Startposition links, rechts definieren
a. Betreten Sie das Fenster
b. Bestimmen Sie, ob ein Fenster angezeigt wird
c. Aktualisieren Sie das Ergebnis (Sie müssen nur die Startposition und Länge der Zeichenfolge aufzeichnen und schließlich die Teilzeichenfolge abschneiden).
Notieren Sie einfach die Startposition und Länge der Zeichenfolge im Code, und schon ist unser Code beendet.
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);
}
};
Er widmet sich seit mehr als 30 Jahren der Technologieforschung und beherrscht verschiedene Sprachen wie Java, Linux, Javascript, PHP, CSS usw. Er hat viele Beiträge im Open-Source-Bereich geleistet Entwicklerdokumentationsstation, um einige Themen in der Technologieentwicklung als zukünftige Referenz zu teilen
