精华内容
下载资源
问答
  • C++滑动窗口算法目的实例实例1题目描述解题思路代码实例2题目描述解题思路代码总结 目的 如何将嵌套for循环在少数问题中转换为单个for循环,从而减少了时间的复杂性。 实例 实例1 题目描述 给一组大小为n的整数数组...

    目的

    如何将嵌套for循环在少数问题中转换为单个for循环,从而减少了时间的复杂性。

    实例

    实例1

    题目描述

    给一组大小为n的整数数组,计算长度为k的子数组的最大值。

    Input  : arr[] = {100, 200, 300, 400}
             k = 2
    Output : 700
    
    Input  : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}
             k = 4 
    Output : 39
    We get maximum sum by adding subarray {4, 2, 10, 23} of size 4.
    
    Input  : arr[] = {2, 3}
             k = 3
    Output : Invalid
    There is no subarray of size 3 as size of whole array is 2.
    

    解题思路

    (1)使用线性循环计算n个项中前k个元素的总和,并将总和存储在变量window_sum中。
    (2)在阵列上应用滑动窗口技术线性滑动直至达到最终并同时追踪最大和。
    (3)要获得k个元素块的当前总和,只需从前一个块中减去第一个元素并添加当前块的最后一个元素即可。

    代码

    int maxSum(int arr[], int n, int k)
    {
        if (n < k)
        {
            cout << "Invaild";
            return -1;
        }
        int max_sum = 0;
        for (int i=0; i<k; i++)
        {
            max_sum += arr[i];
        }
        int windows_sum = max_sum;
        for (int i=k; i<n; i++)
        {
            windows_sum += arr[i] - arr[i - k];
            max_sum = max(max_sum, windows_sum);
        }
        return max_sum;
    }
    

    实例2

    题目描述

    给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。
    字符串只包含小写英文字母,并且字符串 s 和 p 的长度都不超过 20100。
    说明:
    字母异位词指字母相同,但排列不同的字符串。不考虑答案输出的顺序。
    示例 1:
    输入:
    s: “cbaebabacd” p: “abc”
    输出:
    [0, 6]
    解释:
    起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。
    起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。

    解题思路

    (1)使用线性循环识别s的前p.length()个字符和p的所有字符并分别记录于sSave、pSave。
    (2)判断子串是否与p是字母异位词。
    (3)在字符串s上应用滑动窗口技术线性滑动直至达到字符串结束,每滑动一步都进行子串是否与p是字母异位词判断。

    代码

    vector<int> findAnagrams(string s, string p) {
    	vector<int>answer;
    	string s_sub;
    	if (p.length() > s.length()) {
    		return answer;
    	}
    	vector<int>sSave(26, 0), pSave(26, 0);
    	for (int i = 0; i < p.length(); i++) {
    		pSave[p[i] - 'a']++;
    		sSave[s[i] - 'a']++;
    	}
    	int index = 0;
    	if (pSave == sSave) {
    		// 判断子串是否与p是字母异位词
    		s_sub = s.substr(index, p.length());
    		if (s_sub != p) {
    			answer.push_back(index);
    		}
    	}
    	for (index = 1; index <(int)s.length() - (int)p.length() + 1; index++) {
    		sSave[s[index - 1] - 'a']--;
    		sSave[s[index + p.length() - 1] - 'a']++;
    		if (pSave == sSave) {
    			// 判断子串是否与p是字母异位词
    			s_sub = s.substr(index, p.length());
    			if (s_sub != p) {
    				answer.push_back(index);
    			}
    		}
    	}
    	return answer;
    }
    

    总结

    现在,很明显时间复杂性是线性的,因为我们可以看到只有一个循环运行在我们的代码中。因此,我们的时间复杂度是O(n)。
    我们可以使用这种技术来查找最大/最小k-子阵列,XOR,乘积,总和等

    展开全文
  • C++滑动窗口笔记

    2021-04-21 11:18:02
    学习了大佬的滑动窗口讲解,做个笔记。 大佬传送门 LeetCode76.最小覆盖子串 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。...

    学习了大佬的滑动窗口讲解,做个笔记。
    大佬传送门

    先找一个从左到右的符合题目意思的解,一个窗口
    然后通过right指针往前走,改变left,中间不断记录更加优秀的答案
    最后得到最好的解

    LeetCode76.最小覆盖子串

    给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。
    
    注意:如果 s 中存在这样的子串,我们保证它是唯一的答案。
    
     
    
    示例 1:
    
    输入:s = "ADOBECODEBANC", t = "ABC"
    输出:"BANC"
    示例 2:
    
    输入:s = "a", t = "a"
    输出:"a"
     
    
    提示:
    
    1 <= s.length, t.length <= 105
    s 和 t 由英文字母组成
    

    解法:

    class Solution {
    public:
    string minWindow(string s, string t) {
        // 记录最短子串的开始位置和长度
        int start = 0, minLen = INT_MAX;
        int left = 0, right = 0;
        
        unordered_map<char, int> window;
        unordered_map<char, int> needs;
        for (char c : t) needs[c]++;
        
        int match = 0;
        
        while (right < s.size()) {
            char c1 = s[right];
            if (needs.count(c1)) {
                window[c1]++;
                if (window[c1] == needs[c1]) 
                    match++;
            }
            right++;
            
            while (match == needs.size()) {
                if (right - left < minLen) {
                    // 更新最小子串的位置和长度
                    start = left;
                    minLen = right - left;
                }
                char c2 = s[left];
                if (needs.count(c2)) {
                    window[c2]--;
                    if (window[c2] < needs[c2])
                        match--;
                }
                left++;
            }
        }
        return minLen == INT_MAX ?"" : s.substr(start, minLen);
    }
    };
    

    LeetCode567. 字符串的排列

    给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
    
    换句话说,第一个字符串的排列之一是第二个字符串的 子串 。
    
     
    
    示例 1:
    
    输入: s1 = "ab" s2 = "eidbaooo"
    输出: True
    解释: s2 包含 s1 的排列之一 ("ba").
    示例 2:
    
    输入: s1= "ab" s2 = "eidboaoo"
    输出: False
     
    
    提示:
    
    输入的字符串只包含小写字母
    两个字符串的长度都在 [1, 10,000] 之间
    

    解法1:

    class Solution {
    public:
        bool checkInclusion(string s1, string s2) {
            unordered_map<char, int> needs;
            unordered_map<char, int> window;
            for (char c : s1) needs[c]++;
    
            int left = 0, right = 0, match = 0;
            while (right < s2.size())
            {
                char c1 = s2[right];
                if (needs.count(c1)) {
                    window[c1]++;
                    if (window[c1] == needs[c1])
                        match++;
                }
                
                while (match == needs.size())
                {
                    if (right - left + 1 == s1.size())  return true;
                    char c2 = s2[left];
                    if (needs.count(c2)) {
                        window[c2]--;
                        if (window[c2] < needs[c2]) match--;
                    }
                    left++;
                }
                right++;
            }
            return false;
        }
    };
    

    解法2:

    #include<iostream>
    #include<map>
    #include<vector>
    using namespace std;
    
    class Solution {
    public:
        bool check(int cnt1[], int cnt2[]) {//先写个check函数,检查两个数组是不是一样的
            for (int i = 0; i < 26; i++) {
                if (cnt1[i] != cnt2[i]) return false;
            }
            return true;
        }
        bool checkInclusion(string s1, string s2) {
            
            int n = s1.size(), m = s2.size();
            if (n > m) return false;
            int cnt1[26] = { 0 }, cnt2[26] = { 0 };
            for (int i = 0; i < n; i++)//找第一个是不是一样的
            {
                ++cnt1[s1[i] - 'a'];
                ++cnt2[s2[i] - 'a'];
            }
            if (check(cnt1,cnt2)) return true;
            for (int i = n; i < m; i++)//往后面滑动,这个滑动窗口的长度是固定的
            {
                ++cnt2[s2[i] - 'a'];
                --cnt2[s2[i-n] - 'a'];
                if (check(cnt1, cnt2)) return true;
            }
            return false;
        }
    };
    
    int main()
    {
        string s1 = "ab";
        string s2 = "eidbaooo";
        Solution s;
        cout << s.checkInclusion(s1, s2) << endl;
        return 0;
    }
    

    LeetCode438找到字符串中所有字母异位词

    给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。
    
    字符串只包含小写英文字母,并且字符串 s 和 p 的长度都不超过 20100。
    
    说明:
    
    字母异位词指字母相同,但排列不同的字符串。
    不考虑答案输出的顺序。
    示例 1:
    
    输入:
    s: "cbaebabacd" p: "abc"
    
    输出:
    [0, 6]
    
    解释:
    起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
    起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
     示例 2:
    
    输入:
    s: "abab" p: "ab"
    
    输出:
    [0, 1, 2]
    
    解释:
    起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
    起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
    起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
    

    解法:

    class Solution {
    public:
        vector<int> findAnagrams(string s, string p) {
            unordered_map<char, int> needs;
            unordered_map<char, int> window;
            vector<int> res;
            for (char c : p)needs[c]++;
            int left = 0, right = 0, match = 0;
            while (right < s.size())
            {
                char c1 = s[right];
                if (needs.count(c1)) {
                    window[c1]++;
                    if (window[c1] == needs[c1])
                        match++;
                }
                right++;
                while (match == needs.size()) {
                    if (right - left == p.size()) res.push_back(left);
                    char c2 = s[left];
                    if (needs.count(c2)) {
                        window[c2]--;
                        if (window[c2] < needs[c2])
                            match--;
                    }
                    left++;
                }
            }
            return res;
    
        }
    };
    

    LeetCode3 无重复字符的最长子串

    给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
    
     
    
    示例 1:
    
    输入: s = "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
    示例 2:
    
    输入: s = "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
    示例 3:
    
    输入: s = "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
         请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
    示例 4:
    
    输入: s = ""
    输出: 0
    

    解法:

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            unordered_map<char, int> window;
            int left = 0, right = 0,res = 0;
            while (right < s.size())
            {
                char c1 = s[right];
                window[c1]++;
                right++;
                while (window[c1] > 1)
                {
                    char c2 = s[left];
                    window[c2]--;
                    left++;
                }
                res = max(res, right - left);
            }
            return res;
        }
    };
    

    209. 长度最小的子数组

    给定一个含有 n 个正整数的数组和一个正整数 target 。

    找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

    示例 1:

    输入:target = 7, nums = [2,3,1,2,4,3]
    输出:2
    解释:子数组 [4,3] 是该条件下的长度最小的子数组。
    示例 2:

    输入:target = 4, nums = [1,4,4]
    输出:1
    示例 3:

    输入:target = 11, nums = [1,1,1,1,1,1,1,1]
    输出:0

    提示:

    1 <= target <= 109
    1 <= nums.length <= 105
    1 <= nums[i] <= 105

    代码:

    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int result = INT32_MAX;
            int sum = 0; // 滑动窗口数值之和
            int i = 0; // 滑动窗口起始位置
            int subLength = 0; // 滑动窗口的长度
            for (int j = 0; j < nums.size(); j++) {
                sum += nums[j];
                // 注意这里使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件
                while (sum >= s) {
                    subLength = (j - i + 1); // 取子序列的长度
                    result = result < subLength ? result : subLength;
                    sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)
                }
            }
            // 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列
            return result == INT32_MAX ? 0 : result;
        }
    };
    
    展开全文
  • C++滑动窗口模板

    2020-08-12 10:30:18
    滑动窗口模板: 题目是力扣76题 class Solution { public: string minWindow(string s, string t) { unordered_map<char,int> window,need; for(auto c : t) need[c]++; int left = 0,right = 0; int ...

    滑动窗口模板:
    题目是力扣76题

    class Solution {
    public:
        string minWindow(string s, string t) {
            unordered_map<char,int> window,need;
            for(auto c : t) need[c]++;
            int left = 0,right = 0;
            int valid = 0;
            int start = 0,len = INT_MAX;
            while(right < s.size()){
                char c = s[right];
                right++;
                if(need.count(c)){
                    window[c]++;
                    if(window[c] == need[c])
                        valid++;
                }
    
    
                //判断是否需要缩小窗口
                while(valid == need.size()){
                    if(right - left < len){
                        start = left;
                    len = right - left;
                    }   
    
                    //移除窗口
                    char d = s[left];
                    left++;
                    if(need.count(d)){
                        if(window[d] == need[d]){
                            valid--;
                        }
                        window[d]--;
                    }
                }
            }
            return len == INT_MAX ? "" : s.substr(start,len);
        }
    };
    
    展开全文
  • C++滑动窗口算法

    2021-02-05 10:11:17
    滑动窗口算法在一个特定大小的字符串或数组上进行操作,而不在整个字符串和数组上操作,这样就降低了问题的复杂度,从而也达到降低了循环的嵌套深度。 如下题 给你两个长度相同的字符串,s 和 t。 将 s 中的第 i 个...

    滑动窗口算法在一个特定大小的字符串或数组上进行操作,而不在整个字符串和数组上操作,这样就降低了问题的复杂度,从而也达到降低了循环的嵌套深度。

    如下题

    给你两个长度相同的字符串,s 和 t。
    将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销(开销可能为 0),也就是两个字符的
    ASCII 码值的差的绝对值。

    用于变更字符串的最大预算是 maxCost。在转化字符串时,总开销应当小于等于该预算,这也意味着字符串的转化可能是不完全的。

    如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串,则返回可以转化的最大长度。

    如果 s 中没有子字符串可以转化成 t 中对应的子字符串,则返回 0。

    示例 1:

    输入:s = “abcd”, t = “bcdf”, cost = 3 输出:3 解释:s 中的 “abc” 可以变为 “bcd”。开销为
    3,所以最大长度为 3。 示例 2:

    输入:s = “abcd”, t = “cdef”, cost = 3 输出:1 解释:s 中的任一字符要想变成 t
    中对应的字符,其开销都是 2。因此,最大长度为 1。 示例 3:

    字符串s 字符串t 开销 最大长度
    [a] b c d [b] c d f 1 1
    [a b] c d [b c] d f 2 2
    [a b c] d [b c d] f 3 3
    a [b c d] b [c d f] 4 3

    只需要返回窗口的大小就是该开销可以转化的最大长度

    代码如下

    class Solution {
    public:
        int equalSubstring(string s, string t, int maxCost) 
        {
            int left = 0;   // 窗口左边界
            int cost = 0;   // 当前窗口消耗
            // i作为窗口右边界
            for (int i = 0; i < s.size(); i++)
            {
                cost += std::abs(s[i] - t[i]);
                // 如果当前窗口消耗大于总开销,则左边界++,缩减窗口
                if (cost > maxCost)
                {
                    cost -= std::abs(s[left] - t[left]);
                    left++;
                }
            }
            return s.size() - left;
        }
    };
    
    展开全文
  • 题意:给定一个数组,给你一个长度为k的窗口窗口每次向右滑动一个位置,求每次滑动窗口里最大/最小的数。 示例: 思路1:优先队列 最大值:维护一个长度为k的优先队列(pair类型,pair类型的优先队列排序是先...
  • C++ 滑动窗口典型题解

    2021-03-29 16:20:55
    LeetCode 438 找到字符串中所有异位词 给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。 字符串只包含小写英文字母,并且字符串 s 和 p 的长度都不超过 20100...
  • c++滑动窗口最大值

    2020-07-04 18:33:46
    前提:数组长度为n,窗口大小为k。 暴力的时间复杂度是O(nk) vector<int> comp(vector<int> v) { vector<int> ans; for(int i = 0; i+1 < v.size(); i++) ans.push_back(max(v[i],v[i+1])...
  • 首先放上滑动窗口解决,原理比较简单: 对于序列中每一个元素 x 左侧的至多 k个元素,如果这 k 个元素中存在一个元素落在区间 [x - t, x + t]中,我们就找到了一对符合条件的元素。注意到对于两个相邻的元素,它们...
  • 示例 4: 输入: s = “” 输出: 0 思路: 这道题主要用到思路是:滑动窗口 什么是滑动窗口? 其实就是一个队列,比如例题中的 abcabcbb,进入这个队列(窗口)为 abc 满足题目要求,当再进入 a,队列变成了 abca,这...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 619
精华内容 247
关键字:

c++滑动窗口

c++ 订阅