技術共有

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

1. 最小長のサブアレイ

leetcode 209. 最小長のサブ配列

このトピックを見ると、まず乱暴な列挙が思い浮かびますが、次のことを列挙してみましょう。

明らかに、総当たり列挙メソッドはタイムアウトになります。

それでは、タイムアウトしないように最適化する方法はあるのでしょうか?それを分析してみましょう:

暴力的な数え上げでは、右は毎回左の次の位置に戻り、左と合わせて再度数え直します。

列挙を最適化する具体的な手順は次のとおりです。

上記の列挙プロセスでは、青いボックスはサイズが固定されていないスライディング ウィンドウのようなものであり、これをメソッドと呼びます。スライドウィンドウ

スライディング ウィンドウの場合は、次の手順を実行するだけです。

各質問ウィンドウの開始点と更新結果の位置は固定されておらず、具体的な状況はケースバイケースで分析されます。

スライディング ウィンドウ法によれば、コードはタイムアウトしません。

次の時間計算量を簡単に分析します。コードからは、O(n²) しかし、スライディング ウィンドウのアイデアにより、2 つのポインターは同じ方向に移動し、右のポインターが終了するとループが終了します。時間計算量は 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. 繰り返し文字を含まない最長の文字列

この質問に対して最初に思い浮かぶ方法は間違いなく列挙であり、各文字が出現する回数を数えます。文字が 2 回出現する場合、現在の文字に対応する文字列が最長の部分文字列になります。

総当たり列挙法でも合格できることがわかりました。

もっと良い解決策はありますか?分析してみましょう

上記の解決策は単なるスライディング ウィンドウではありませんか?

このときの時間計算量 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の最大連続数Ⅲ

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. フルーツバスケット

リートコード 904.かごの中の果物

タイトルが長いのですが、どういう意味なのでしょうか？

かごは 2 つしかなく、かごの中には 2 種類の果物しか入れられず、木を越えることはできません。通過できる木の最大数を求めてください。
つまり、連続した間隔の長さを見つけるには、スライディング ウィンドウを使用できます。

では、現在収穫されている果物の数をどうやって知ることができるのでしょうか? ----ハッシュテーブル統計を使用する

ハッシュ テーブルの使用による消費量はまだかなり大きいことがわかります。さらに最適化することはできますか?

質問要件からカテゴリが 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. 文字列内のすべての文字のアナグラムを検索します。

質問の分析から、s 文字列の中で p 文字列を見つけることであることがわかります (p 文字列内の文字の順序は崩れる可能性があります)。
そうすれば、私たちはできる長さが p に等しく、文字の種類と数が p string に等しい部分文字列を見つけるだけです。。

したがって、2 つのハッシュ テーブルを使用して、文字列 p と文字列 s の文字の種類と数をそれぞれカウントできます。

それでは、まず暴力的な列挙を使用して試してみましょう。

2 つのハッシュ テーブルはどのように比較されますか?

1. まず、hash1 を使用して、p 文字列内の文字の種類の数を記録します。
2. s を走査して、長さが p に等しい部分文字列を見つけ、hash2 に現在の文字を格納します。
   a. hash2[right] <= hash1[right]の場合、「有効な文字」の種類が増加します
   b. 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. スライディングウィンドウを使用する（文字列の長さが固定されているため、長さを直接ジャンプできます）
   a. 定義開始: 左、右
   b. 文字列がウィンドウに入ったら、文字列関数 substr を使用して文字列を切り取る必要があります。
   c. 文字列のタイプを決定します。
   ウィンドウを終了するかどうか
   結果を更新する

ただし、テスト ケースを分析したところ、合格したコードは一部のみでした。

これがコードです！

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. 最小カバー部分文字列

この質問の解決策は、文字列 s 内の文字列 t のすべての文字を検索する点が異なりますが、見つかった文字列の中で最も小さいものが返される点が異なります。

それを解決するために、私たちは今でもスライディング ウィンドウ + ハッシュ テーブルを使用しています。

1. hash1 を使用して、t 文字列内の文字の種類と数をカウントします。
2. スライディング ウィンドウ: 開始位置の左、右を定義します
   a. 窓に入る
   b. ウィンドウが表示されるかどうかを確認します。
   c. 結果を更新します (文字列の開始位置と長さを記録するだけでよく、最後に部分文字列を切り取ります)。

コード内の文字列の開始位置と長さを記録するだけでコードは完了です。

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