当前位置:   article > 正文

【C++刷题】优选算法——滑动窗口_c++ 滑窗算法题

c++ 滑窗算法题

滑动窗口算法是在可以利用单调性使用“同向双指针”来解决问题时使用。

  1. 长度最小的子数组
int minSubArrayLen(int target, vector<int>& nums)
{
    size_t left = 0;
    size_t right = 0;
    long long sum = 0;
    int len = nums.size() + 1;
    while(right < nums.size())
    {
        sum += nums[right]; // 进窗口
        while (sum >= target)
        {
            // 更新结果
            if (right - left + 1 < len)
            {
                len = right - left + 1;
            }
            sum -= nums[left++]; // 出窗口
        }
        ++right;
    }
    return len == nums.size() + 1 ? 0 : len;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  1. 无重复字符的最长子串
int lengthOfLongestSubstring(string s)
{
    char arr[256];
    memset(arr, 0, 256);
    size_t len = 0;
    for(size_t left = 0, right = 0; right < s.size(); ++right)
    {
        ++arr[s[right]]; // 进窗口
        while(arr[s[right]] > 1) // 判断
        {
            --arr[s[left++]]; // 出窗口
        }
        if(right - left + 1 > len ) len = right - left + 1; // 更新结果
    }
    return len;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  1. 最大连续1的个数 III
int longestOnes(vector<int>& nums, int k)
{
    size_t left = 0;
    size_t right = 0;
    size_t len = 0;
    while(right < nums.size())
    {
        if(nums[right] != 0)
        {
            if(len < right - left + 1) len = right - left + 1;
        }
        else
        {
            if(k > 0)
            {
                if(len < right - left + 1) len = right - left + 1;
                --k;
            }
            else
            {
                while (nums[left++] != 0);
            }
        }
        ++right;
    }
    return 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
  1. 将 x 减到 0 的最小操作数
    转化为找出中间的一个连续的区域,使该区域的和等于整个数组的和与x的差。
int minOperations(vector<int>& nums, int x)
{
    size_t sum = 0;
    for(int e : nums) sum += e;
    x = sum - x;
    if(x == 0) return nums.size();

    size_t left = 0;
    size_t right = 0;
    sum = 0;
    size_t len = 0;
    while(right < nums.size())
    {
        sum += nums[right]; // 进窗口
        while(sum > x) // 判断
        {
            sum -= nums[left];
            ++left; // 出窗口
        }
        if(sum == x && len < right - left + 1) len = right - left + 1; // 更新结果
        ++right;
    }        
    return len == 0 ? -1 : nums.size() - 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
  1. 水果成篮
struct Basket
{
    int type = -1;
    int num = 0;
};

class Solution {
public:
    int totalFruit(vector<int>& fruits)
    {
        size_t left = 0;
        size_t right = 0;
        int max = 0;
        Basket basket[2];
        while(right < fruits.size())
        {
            // 如果有空篮子或水果类型相同,就入窗口
            if(basket[0].type == -1 || basket[0].type == fruits[right])
            {
                basket[0].type = fruits[right];
                basket[0].num++;
                if(max < basket[0].num + basket[1].num) max = basket[0].num + basket[1].num;
            }
            else if(basket[1].type == -1 || basket[1].type == fruits[right])
            {
                basket[1].type = fruits[right];
                basket[1].num++;
                if(max < basket[0].num + basket[1].num) max = basket[0].num + basket[1].num;
            }
            else
            {
                while(true)
                {
                    if(basket[0].type == fruits[left])
                    {
                        ++left;
                        --basket[0].num;
                        if(basket[0].num == 0)
                        {
                            basket[0].type = fruits[right];
                            basket[0].num++;
                            break;
                        }
                    }
                    else if(basket[1].type == fruits[left])
                    {
                        ++left;
                        --basket[1].num;
                        if(basket[1].num == 0)
                        {
                            basket[1].type = fruits[right];
                            basket[1].num++;
                            break;
                        }
                    } 
                }
            }
            ++right;
        }
        return max;
    }
};
  • 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
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  1. 找到字符串中所有字母异位词
    对于子串是否符合规则的判断,可以利用两个hash表和一个count来解决。
vector<int> findAnagrams(string s, string p)
{
    vector<int> v;
    if(s.size() < p.size()) return v;

    int count = 0; // 记录相同的有效元素的个数

    int hash_p[26];
    memset(hash_p, 0, 26 * sizeof(int));
    for(char c : p) hash_p[c - 'a']++;

    int hash_s[26];
    memset(hash_s, 0, 26 * sizeof(int));
    for(size_t i = 0; i < p.size(); ++i)
        if(hash_s[s[i] - 'a']++ < hash_p[s[i] - 'a']) ++count;

    size_t left = 0;
    size_t right = p.size() - 1;
    while(right < s.size())
    {
        if(count == p.size()) v.push_back(left);
        
        if (hash_s[s[left] - 'a']-- <= hash_p[s[left] - 'a']) --count;
        ++left;
        if(++right < s.size() && hash_s[s[right] - 'a']++ < hash_p[s[right] - 'a']) ++count;
    }
    return v;
}
  • 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
  1. 串联所有单词的子串
vector<int> findSubstring(string s, vector<string>& words)
{
    vector<int> v;
    if (s.size() < words.size() * words[0].size()) return v;

    // words的hash
    unordered_map<string, int> m_wd;
    for (string& s : words) m_wd[s]++;
    // s的hash
    unordered_map<string, int> m_s;
    // 步长step
    size_t step = words[0].size();
    // 有效元素个数count
    size_t count = 0;
    // words的单词合并长度
    size_t words_length = words.size() * words[0].size();
    // 回归坐标index
    // 只需要滑动窗口step步长次即可
    for (size_t index = 0; index < step; ++index)
    {
        m_s.clear();
        count = 0;
        for (size_t i = index, size = 0; i < s.size() && size < words.size(); i += step, ++size)
        {
            string tmp = s.substr(i, step);
            if (m_wd.count(tmp) && m_s[tmp]++ < m_wd[tmp])
            {
                ++count;
            }
        }

        size_t left = index, right = left + words_length;
        while (right <= s.size())
        {
            if (count == words.size())
            {
                v.push_back(left);
            }

            string tmp_left = s.substr(left, step);
            if (m_wd.count(tmp_left) && m_s[tmp_left]-- <= m_wd[tmp_left])
            {
                --count;
            }
            left += step;

            right += step;
            if (right <= s.size())
            {
                string tmp_right = s.substr(right - step, step);
                if (m_wd.count(tmp_right) && m_s[tmp_right]++ < m_wd[tmp_right])
                {
                    ++count;
                }
            }
        }
    }
    return v;
}
  • 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
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  1. 最小覆盖子串
string minWindow(string s, string t)
{
    string ret = s;
    if (s.size() < t.size()) return "";

    unordered_map<char, int> t_map;
    for (char c : t) t_map[c]++;

    unordered_map<char, int> s_map;
    size_t count = 0;
    size_t left = 0, right = 0;
    while (right < s.size() && count < t.size())
    {
        if (t_map.count(s[right]) && s_map[s[right]]++ < t_map[s[right]])
        {
            ++count;
        }
        ++right;
    }
    if (right == s.size())
    {
        if (count < t.size())
        {
            return "";
        }
        else
        {
            // 到达临界点
            while (!t_map.count(s[left]) || s_map[s[left]] > t_map[s[left]])
            {
                s_map[s[left]]--;
                ++left;
            }
            return s.substr(left, right - left);
        }
    }
    while (right < s.size())
    {
        if (count == t.size())
        {
            // 到达临界点
            while (!t_map.count(s[left]) || s_map[s[left]] > t_map[s[left]])
            {
                s_map[s[left]]--;
                ++left;
            }
            if (count == t.size() && ret.size() > right - left) ret = s.substr(left, right - left);

            // 出窗口
            s_map[s[left]]--;
            ++left;
            --count;
        }
        while (right < s.size() && count < t.size())
        {
            if (t_map.count(s[right]) && s_map[s[right]]++ < t_map[s[right]]) // 元素存在且小于
            {
                ++count;
            }
            ++right;
        }
    }
    // 到达临界点
    while (left < right && (!t_map.count(s[left]) || s_map[s[left]] > t_map[s[left]]))
    {
        s_map[s[left]]--;
        ++left;
    }
    if (count == t.size() && ret.size() > right - left) ret = s.substr(left, right - 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
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/676680
推荐阅读
相关标签
  

闽ICP备14008679号