기술나눔

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

1. 최소 길이의 하위 배열

letcode 209. 최소 길이의 하위 배열

이 주제를 볼 때 가장 먼저 떠오르는 것은 폭력적인 열거이므로 다음을 열거해 보겠습니다.

분명히 무차별 열거 방법은 시간 초과됩니다.

그렇다면 시간 초과가 발생하지 않도록 최적화할 수 있는 방법이 있습니까? 분석해보자:

폭력적인 열거에서는 오른쪽이 매번 왼쪽의 다음 위치로 돌아가고 왼쪽과 함께 다시 열거됩니다.

열거를 최적화하는 구체적인 단계는 다음과 같습니다.

위의 열거 프로세스에서 파란색 상자는 크기가 고정되지 않은 슬라이딩 창과 같습니다. 이 메서드를 호출합니다.슬라이딩 윈도우

슬라이딩 창의 경우 다음 단계에 지나지 않습니다.

각 질문 창의 시작점과 업데이트된 결과의 위치는 고정되어 있지 않으며, 구체적인 상황은 사례별로 분석됩니다.

슬라이딩 윈도우 방식에 따르면 코드는 시간 초과되지 않습니다.

다음과 같은 시간 복잡도를 간략하게 분석해 보세요. 코드에서 보면 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. 문자열에서 모든 문자 철자 바꾸기 찾기

질문을 분석해 보면 s 문자열에서 p 문자열을 찾는 것임을 알 수 있습니다(p 문자열에서 문자 순서가 흐트러질 수 있음).
그러면 우리는 할 수 있다길이가 p와 같고 문자 유형과 숫자가 p 문자열과 같은 하위 문자열을 찾으세요.。

따라서 두 개의 해시 테이블을 사용하여 문자열 p와 문자열 s에 있는 문자의 유형과 수를 각각 계산할 수 있습니다.

그런 다음 폭력적인 열거를 사용하여 먼저 시도해 보겠습니다.

두 해시 테이블을 어떻게 비교하나요?

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. 최소 포함 하위 문자열

letcode 76. 최소 포함 하위 문자열

이 질문에 대한 해결책은 이전 질문과 유사합니다. 또한 발견된 문자열 중 가장 작은 문자가 반환된다는 점을 제외하면 문자열 s에서 문자열 t의 모든 문자를 검색합니다.

우리는 여전히 슬라이딩 윈도우 + 해시 테이블을 사용하여 이 문제를 해결합니다.

1. hash1을 사용하여 t 문자열의 문자 유형과 수를 계산합니다.
2. 슬라이딩 윈도우: 왼쪽, 오른쪽 시작 위치 정의
   가. 창에 들어가라.
   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