Berbagi teknologi

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

1. Subarray dengan panjang minimum

leetcode 209. Subarray dengan panjang minimum

Saat melihat topik ini, hal pertama yang terlintas di benak kita adalah enumerasi yang kejam, jadi mari kita coba enumerasi berikut ini:

Jelas, metode enumerasi brute force akan habis waktunya.

Lalu adakah cara untuk mengoptimalkannya agar tidak kehabisan waktu? Mari kita analisa:

Dalam pencacahan kekerasan, hak kita akan kembali ke posisi kiri berikutnya setiap saat, dan kemudian melakukan pencacahan ulang bersama dengan kiri.

Langkah-langkah spesifik untuk mengoptimalkan enumerasi adalah sebagai berikut:

Dalam proses pencacahan di atas, kotak biru kita seperti jendela geser dengan ukuran yang tidak tetap. Kita menyebutnya metode inijendela geser

Untuk jendela geser, tidak lebih dari langkah-langkah berikut:

Titik awal setiap jendela pertanyaan dan posisi hasil yang diperbarui tidak tetap, dan situasi spesifik akan dianalisis berdasarkan kasus per kasus.

Menurut metode jendela geser, waktu kode kita tidak akan habis.

Analisis secara singkat kompleksitas waktu berikut: Dari kode sepertinya O(n²), tetapi karena gagasan jendela geser kita, kedua penunjuk melintasi arah yang sama dan tidak akan kembali; ketika penunjuk kanan berakhir, loop berakhir, jadi begitulahKompleksitas waktunya adalah 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. Substring terpanjang tanpa karakter berulang

leetcode 3. String terpanjang tanpa karakter berulang

Metode pertama yang terlintas dalam pikiran untuk pertanyaan ini tidak diragukan lagi adalah enumerasi, dan kemudian menghitung berapa kali setiap karakter muncul dua kali, maka string yang sesuai dengan karakter saat ini adalah substring terpanjang.

Kami menemukan bahwa metode enumerasi brute force juga bisa lolos

Apakah ada solusi yang lebih baik?Mari kita analisa

Bukankah solusi di atas hanyalah jendela geser?

Apakah kompleksitas waktu O(n) saat ini lebih baik dibandingkan dengan pencacahan kekerasan O(n)?²) bahkan lebih baik

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. Jumlah maksimal 1 berturut-turut III

leetcode 1004. Jumlah maksimum 1 berturut-turut III

Dari analisa topik kita bisa melihat hal ituFakta bahwa 0 dapat dibalik berarti: 0 dapat digunakan sebagai 1 . Maka tujuan kita adalah mencari interval yang berisi bilangan 1 terbesar, dan jumlah 0 dalam interval tersebut tidak boleh melebihi k.

Metode enumerasi yang kejam untuk pertanyaan ini tidak akan diperlihatkan. Mari kita langsung ke jendela geser.


Dengan cara ini kode kita akan lolos

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. Jumlah minimum operasi untuk mengurangi x menjadi 0

leetcode 1658. Jumlah minimum operasi untuk mengurangi x menjadi 0

Dengan membaca soal-soal tersebut, kita dapat mengetahui bahwa itu ada di sisi kiri dan di sisi kanan. Apakah sulit untuk mengontrolnya?
Hal sebaliknya berlaku ketika hal tersebut sulit

• Kami menemukan interval kontinu dalam array, menghapus konten interval kontinu dalam array, dan konten yang tersisa persis sama dengan x, maka kami menemukan situasinya
• Interval kontinu ini adalahJumlah elemen dalam array dikurangi x
• Ketika interval kontinu terpanjang ditemukan dalam array, kita telah menemukan solusi terbaik.

Masih seperti pertanyaan sebelumnya, gunakan jendela geser.

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. Keranjang buah

leetcode 904.Buah-buahan dalam keranjang

Judulnya panjang sekali, apa maksudnya?

Hanya ada dua keranjang, dan hanya boleh ada dua jenis buah di dalam keranjang, dan keduanya tidak dapat melintasi pohon.
Yaitu untuk mencari panjang interval kontinu. Kita dapat menggunakan jendela geser

Jadi bagaimana saya tahu berapa banyak buah yang sedang dipetik? ---- Gunakan statistik tabel hash

Terlihat konsumsi penggunaan tabel hash masih cukup besar.

Terlihat dari syarat soal yang kategorinya kurang dari 10⁵, jadi kita bisa langsung menggunakan array + variabel (tipe record)

Dengan cara ini, efisiensi kami meningkat pesat.

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. Temukan semua anagram huruf dalam string

leetcode 438. Temukan semua anagram huruf dalam sebuah string

Dari analisa soal terlihat bahwa mencari string p pada string s (urutan karakter pada string p dapat terganggu).
Lalu kita bisaTemukan saja substring yang panjangnya sama dengan p, dan tipe karakter serta nomornya sama dengan p string.。

Jadi kita bisa menggunakan dua tabel hash untuk menghitung tipe dan jumlah karakter dalam string p dan string s.

Kalau begitu mari kita coba dulu menggunakan enumerasi kekerasan:

Bagaimana perbandingan kedua tabel hash?

1. Pertama, gunakan hash1 untuk mencatat jumlah tipe karakter dalam string p.
2. Lintasi s dan temukan substring yang panjangnya sama dengan p, dan hash2 menyimpan karakter saat ini.
   a. Jika hash2[kanan] <= hash1[kanan], jenis "karakter yang valid" bertambah
   b. Jika hash2[kanan] > hash2[kanan], jenis "karakter yang valid" tetap tidak berubah

Metode pencacahan dengan kekerasan memang layak dilakukan, namun relatif tidak efisien.
Karena kita mencari interval kontinu, bisakah kita menggunakan jendela geser?mari kita mencobanya

Dengan cara ini efisiensi kita akan jauh lebih tinggi

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. Gabungkan substring dari semua kata

leetcode 30. Menggabungkan substring dari semua kata

Pertanyaan ini mirip dengan pertanyaan sebelumnya, hanya saja karakternya diganti dengan string. Oleh karena itu, kami masih menggunakan: jendela geser + tabel hash untuk menyelesaikan masalah.

Langkah-langkah pemecahan masalah:

1. Pertama gunakan hash1 untuk menghitung jenis string dalam kata-kata
2. Gunakan jendela geser (karena panjang senar tetap, Anda dapat langsung melompati panjangnya)
   a.Definisi awal: kiri, kanan
   b.Saat string memasuki jendela, Anda perlu menggunakan fungsi string substr untuk memotongnya.
   c.Menentukan jenis tali
   Apakah akan keluar dari jendela
   Perbarui hasil

Namun, hanya sebagian dari kode yang lolos.

Itu saja untuk kodenya!

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. Substring penutup minimum

leetcode 76. Substring penutup minimum

Solusi untuk pertanyaan ini mirip dengan pertanyaan sebelumnya. Ia juga mencari semua karakter string t dalam string s, kecuali string terkecil yang ditemukan dikembalikan.

Kami masih menggunakan jendela geser + tabel hash untuk menyelesaikannya.

1. Gunakan hash1 untuk menghitung jenis dan jumlah karakter dalam string t
2. Jendela geser: tentukan posisi awal kiri, kanan
   a.Masuk ke jendela
   b. Tentukan apakah sebuah jendela muncul
   c. Update hasilnya (hanya perlu mencatat posisi awal dan panjang string, dan terakhir memotong substringnya)

Catat saja posisi awal dan panjang string dalam kode, dan kode kita akan lolos.

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