Κοινή χρήση τεχνολογίας

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

1. Υποστρώμα με ελάχιστο μήκος

leetcode 209. Subray με ελάχιστο μήκος

Όταν βλέπετε αυτό το θέμα, το πρώτο πράγμα που σας έρχεται στο μυαλό είναι η βίαιη απαρίθμηση, οπότε ας προσπαθήσουμε να απαριθμήσουμε τα εξής:

Προφανώς, η μέθοδος απαρίθμησης ωμής δύναμης θα λήξει.

Υπάρχει λοιπόν κάποιος τρόπος να το βελτιστοποιήσουμε ώστε να μην λήξει; Ας το αναλύσουμε:

Στη βίαιη απαρίθμηση, το δεξί μας θα επιστρέφει στην επόμενη θέση του αριστερού κάθε φορά και στη συνέχεια θα επαναριθμεί μαζί με το αριστερό.

Τα συγκεκριμένα βήματα για τη βελτιστοποίηση της απαρίθμησης είναι τα εξής:

Στην παραπάνω διαδικασία απαρίθμησης, το μπλε κουτί μας είναι σαν ένα συρόμενο παράθυρο με μη καθορισμένο μέγεθοςσυρόμενο παράθυρο

Για τα συρόμενα παράθυρα, δεν είναι τίποτα άλλο από τα ακόλουθα βήματα:

Το σημείο εκκίνησης κάθε παραθύρου ερωτήσεων και η θέση των ενημερωμένων αποτελεσμάτων δεν είναι σταθερά και η συγκεκριμένη κατάσταση θα αναλυθεί κατά περίπτωση.

Σύμφωνα με τη μέθοδο του συρόμενου παραθύρου, ο κωδικός μας δεν θα λήξει.

Αναλύστε συνοπτικά την ακόλουθη χρονική πολυπλοκότητα: από τον κώδικα φαίνεται να είναι O(n²), αλλά λόγω της ιδέας του συρόμενου παραθύρου, οι δύο δείκτες διασχίζουν την ίδια κατεύθυνση και δεν θα πάνε πίσω όταν τελειώσει ο δεξιός δείκτης, τελειώνει ο βρόχοςΗ χρονική πολυπλοκότητα είναι 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. Η μεγαλύτερη υποσυμβολοσειρά χωρίς επαναλαμβανόμενους χαρακτήρες

leetcode 3. Η μεγαλύτερη συμβολοσειρά χωρίς επαναλαμβανόμενους χαρακτήρες

Η πρώτη μέθοδος που έρχεται στο μυαλό για αυτήν την ερώτηση είναι αναμφίβολα η απαρίθμηση και, στη συνέχεια, η μέτρηση του αριθμού των φορών που εμφανίζεται κάθε χαρακτήρας, εάν ένας χαρακτήρας εμφανίζεται δύο φορές, τότε η συμβολοσειρά που αντιστοιχεί στον τρέχοντα χαρακτήρα είναι η μεγαλύτερη υποσυμβολοσειρά.

Βρήκαμε ότι η μέθοδος απαρίθμησης ωμής δύναμης μπορεί επίσης να περάσει

Υπάρχει καλύτερη λύση;Ας το αναλύσουμε

Η παραπάνω λύση δεν είναι απλώς ένα συρόμενο παράθυρο;

Είναι η χρονική πολυπλοκότητα O(n) αυτή τη στιγμή καλύτερη από αυτή της βίαιης απαρίθμησης O(n);²) είναι ακόμα καλύτερο

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. Μέγιστος αριθμός διαδοχικών 1 III

leetcode 1004. Μέγιστος αριθμός διαδοχικών 1 III

Αναλύοντας το θέμα, μπορούμε να το δούμεΤο γεγονός ότι το 0 μπορεί να αναστραφεί σημαίνει: το 0 μπορεί να χρησιμοποιηθεί ως 1 . Τότε ο στόχος μας είναι να βρούμε ένα διάστημα που περιέχει τον μεγαλύτερο αριθμό 1 και ο αριθμός των 0 σε αυτό το διάστημα δεν μπορεί να υπερβαίνει το k.

Η μέθοδος βίαιης απαρίθμησης για αυτήν την ερώτηση δεν θα αποδειχθεί. Ας πάμε απευθείας στο συρόμενο παράθυρο.


Έτσι θα περάσει ο κωδικός μας

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. Ελάχιστος αριθμός πράξεων για μείωση του x σε 0

leetcode 1658. Ελάχιστος αριθμός πράξεων για μείωση του x σε 0

Διαβάζοντας τις ερωτήσεις, μπορούμε να βρούμε ότι είναι στην αριστερή πλευρά και στη δεξιά πλευρά; Είναι δύσκολο να το ελέγξουμε;
Το αντίθετο συμβαίνει όταν είναι δύσκολο

• Βρίσκουμε ένα συνεχές διάστημα στον πίνακα, αφαιρούμε το περιεχόμενο του συνεχούς διαστήματος στον πίνακα και το υπόλοιπο περιεχόμενο είναι ακριβώς ίσο με x, τότε έχουμε βρει μια κατάσταση;
• Αυτό το συνεχές διάστημα είναιΆθροισμα στοιχείων στον πίνακα μείον x
• Όταν βρεθεί το μεγαλύτερο συνεχές διάστημα στον πίνακα, έχουμε βρει την καλύτερη λύση.

Όπως και στην προηγούμενη ερώτηση, χρησιμοποιήστε ένα συρόμενο παράθυρο.

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. Καλάθια με φρούτα

leetcode 904. Φρούτα σε καλάθι

Αυτός ο τίτλος είναι τόσο μεγάλος, τι σημαίνει;

Υπάρχουν μόνο δύο καλάθια και μπορεί να υπάρχουν μόνο δύο είδη φρούτων στα καλάθια και δεν μπορούν να διασταυρώσουν τα δέντρα Βρείτε τον μέγιστο αριθμό δέντρων που μπορείτε να περάσετε.
Δηλαδή για να βρούμε το μήκος ενός συνεχούς διαστήματος Μπορούμε να χρησιμοποιήσουμε ένα συρόμενο παράθυρο

Πώς μπορώ λοιπόν να ξέρω πόσα φρούτα μαζεύονται αυτήν τη στιγμή; ----Χρησιμοποιήστε στατιστικά πίνακα κατακερματισμού

Μπορούμε να διαπιστώσουμε ότι η κατανάλωση των πινάκων κατακερματισμού εξακολουθεί να είναι αρκετά μεγάλη. Μπορεί να βελτιστοποιηθεί περαιτέρω;

Από τις απαιτήσεις της ερώτησης φαίνεται ότι η κατηγορία είναι μικρότερη από 10⁵, ώστε να μπορούμε να χρησιμοποιήσουμε απευθείας έναν πίνακα + μια μεταβλητή (τύπος εγγραφής)

Με αυτόν τον τρόπο, η αποτελεσματικότητά μας έχει βελτιωθεί πολύ.

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. Βρείτε όλους τους αναγραμματισμούς γραμμάτων στη συμβολοσειρά

leetcode 438. Βρείτε όλους τους αναγραμματισμούς γραμμάτων σε μια συμβολοσειρά

Από την ανάλυση της ερώτησης, μπορούμε να δούμε ότι είναι να βρεθεί η συμβολοσειρά p στη συμβολοσειρά s (η σειρά των χαρακτήρων στη συμβολοσειρά p μπορεί να διαταραχθεί).
Τότε μπορούμεΑπλώς βρείτε μια υποσυμβολοσειρά της οποίας το μήκος είναι ίσο με p, και της οποίας ο τύπος και ο αριθμός χαρακτήρων είναι ίσοι με τη συμβολοσειρά p.。

Έτσι μπορούμε να χρησιμοποιήσουμε δύο πίνακες κατακερματισμού για να μετρήσουμε τους τύπους και τους αριθμούς των χαρακτήρων στη συμβολοσειρά p και συμβολοσειρά s αντίστοιχα.

Στη συνέχεια, ας το δοκιμάσουμε πρώτα χρησιμοποιώντας βίαιη απαρίθμηση:

Πώς συγκρίνονται οι δύο πίνακες κατακερματισμού;

1. Αρχικά, χρησιμοποιήστε το hash1 για να καταγράψετε τον αριθμό των τύπων χαρακτήρων στη συμβολοσειρά p.
2. Διασχίστε το s και βρείτε την υποσυμβολοσειρά της οποίας το μήκος είναι ίσο με p και το hash2 αποθηκεύει τον τρέχοντα χαρακτήρα.
   a Αν hash2[right] <= hash1[right], οι τύποι των "έγκυρων χαρακτήρων" αυξάνονται
   β) Εάν hash2[right] > hash2[right], ο τύπος των "έγκυρων χαρακτήρων" παραμένει αμετάβλητος.

Η μέθοδος της βίαιης απαρίθμησης είναι πράγματι εφικτή, αλλά είναι σχετικά αναποτελεσματική.
Εφόσον ψάχνουμε για ένα συνεχές διάστημα, μπορούμε να χρησιμοποιήσουμε ένα συρόμενο παράθυρο;ας το προσπαθήσουμε

Έτσι η αποτελεσματικότητά μας θα είναι πολύ μεγαλύτερη

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. Συνδέστε τις υποσυμβολοσειρές όλων των λέξεων

leetcode 30. Συνδέστε τις υποσυμβολοσειρές όλων των λέξεων

Αυτή η ερώτηση είναι παρόμοια με την προηγούμενη ερώτηση, με τη διαφορά ότι οι χαρακτήρες αντικαθίστανται από συμβολοσειρές. Επομένως, εξακολουθούμε να χρησιμοποιούμε: συρόμενο παράθυρο + πίνακας κατακερματισμού για να λύσουμε το πρόβλημα.

Βήματα επίλυσης προβλημάτων:

1. Χρησιμοποιήστε πρώτα το hash1 για να μετρήσετε τους τύπους συμβολοσειρών σε λέξεις
2. Χρησιμοποιήστε ένα συρόμενο παράθυρο (καθώς το μήκος της χορδής είναι σταθερό, μπορείτε να πηδήσετε απευθείας το μήκος)
   α. Ορισμός έναρξη: αριστερά, δεξιά
   β Όταν η συμβολοσειρά εισέλθει στο παράθυρο, πρέπει να χρησιμοποιήσετε τη συνάρτηση συμβολοσειράς substr για να την κόψετε.
   γ. Προσδιορίστε τον τύπο της συμβολοσειράς
   Είτε θα βγείτε από το παράθυρο
   Ενημέρωση αποτελεσμάτων

Ωστόσο, μόνο ένα μέρος του κώδικα πέρασε Αναλύοντας τις περιπτώσεις δοκιμής του.

Αυτός είναι ο κωδικός!

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. Ελάχιστο καλυπτικό υποχορδόνι

leetcode 76. Ελάχιστη καλυπτική υποσυμβολοσειρά

Η λύση σε αυτήν την ερώτηση είναι παρόμοια με την προηγούμενη ερώτηση Επίσης αναζητά όλους τους χαρακτήρες της συμβολοσειράς t στη συμβολοσειρά s, εκτός από το ότι επιστρέφεται η μικρότερη από τις συμβολοσειρές που βρέθηκαν.

Εξακολουθούμε να χρησιμοποιούμε συρόμενο παράθυρο + πίνακα κατακερματισμού για να το λύσουμε.

1. Χρησιμοποιήστε το hash1 για να μετρήσετε τον τύπο και τον αριθμό των χαρακτήρων στη συμβολοσειρά t
2. Συρόμενο παράθυρο: ορίστε τη θέση έναρξης αριστερά, δεξιά
   α. Μπείτε στο παράθυρο
   β. Προσδιορίστε εάν εμφανίζεται ένα παράθυρο
   γ. Ενημερώστε το αποτέλεσμα (χρειάζεται μόνο να καταγράψετε την αρχική θέση και το μήκος της συμβολοσειράς και τελικά να κόψετε την υποχορδή)

Απλώς καταγράψτε την αρχική θέση και το μήκος της συμβολοσειράς στον κώδικα και ο κωδικός μας θα τελειώσει.

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