滑动窗口如人生,回顾往事不复还———力扣刷题

2023-12-13 19:51:01

第一题:长度最小的子数组

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

2f2f5cfa09674873b7b2c70b0b26a2da.png思路:

第一想法肯定时暴力枚举,枚举数组任何一个元素,把他当起始位置,然后从起始位置找最短区间,使得区间和大于等于目标值

利用两个嵌套for循环,如果符合条件就记录,然后更新结果,返回

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        // 记录结果
            int ret = INT_MAX;
        int n = nums.size();
        // 枚举出所有满?和?于等于 target 的?数组[start, end]
        // 由于是取到最?,因此枚举的过程中要尽量让数组的?度最?
        // 枚举开始位置
        for (int start = 0; start < n; start++)
        {
            int sum = 0; // 记录从这个位置开始的连续数组的和
            // 寻找结束位置
            for (int end = start; end < n; end++)
            {
                sum += nums[end]; // 将当前位置加上

                if (sum >= target) // 当这段区间内的和满?条件时
                {
                    // 更新结果,start 开头的最短区间已经找到
                    ret = min(ret, end - start + 1);
                    break;
                }
            }
        }
        // 返回最后结果
        return ret == INT_MAX ? 0 : ret;
    }
};

由于都是正数因此,只要找到最短区间就不必往下继续查找,因为可能所有的数都不满足条件,因此这里可能返回0,并且保证所有数都可更新,初始化ret为INT_MAX;

法二:滑动窗口

先将右端元素划入窗口,然后统计窗口元素和,如果大于target,更新,并且把左端元素滑出,继续同时判断是否满足更新结果,因为滑出去之和依旧可能满足条件,如果窗口不满足right++,进入下一个窗口。

?

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
            int n=nums.size(),sum=0,len=INT_MAX;
            for(int left=0,right=0;right<n;right++)
            {
                sum+=nums[right];
                while(sum>=target)
                {
                    len=min(len,right-left+1);
                    sum-=nums[left++];
                }
            }
            return len==INT_MAX?0:len;
    }
};

来自一个力扣大佬的形象解释:左右指针中间窗口的sum为两指针的“共同财产”,就是右指针一直在努力工作挣钱,好不容易共同财产大过target,记录一下两指针之间的距离,结果左指针就开始得瑟挥霍,不停花钱(往右移动),结果花钱一直花到sum又小过target,此时右指针不得不再次出来工作,不停向右移动,周而复始,最后取左右指针离得最近的时候

?

第二题:?重复字符的最??串(medium)

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

84df8a2a14b54730b3b36f87ee5682e1.png

法一依旧是暴力:

即先固定一个,然后遍历所有,创建个哈希表用来记录出现的次数,如果大于一则说明出现重复,那么就跳出当前循环,进入下一个固定的数进行遍历,否则就记录此刻长度

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0; // 记录结果
        int n = s.length();
        // 1. 枚举从不同位置开始的最?重复?串
        // 枚举起始位置
        for (int i = 0; i < n; i++)
        {// 创建?个哈希表,统计频次
            int hash[128] = { 0 };

            // 寻找结束为?
            for (int j = i; j < n; j++)
            {
                hash[s[j]]++; // 统计字符出现的频次
                if (hash[s[j]] > 1) // 如果出现重复的
                    break;

                // 如果没有重复,就更新 ret
                ret = max(ret, j - i + 1);
            }
        }
        // 2. 返回结果
        return ret;
    }
};

?

?法二:

例题中的 abcabcbb,进入这个队列(窗口)为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列!如何移动?我们只要把队列的左边的元素移出就行了,直到满足题目要求!一直维持这样的队列,找出队列出现最长的长度时候,求出解!

步骤就是右端ch元素进入时,用哈希表统计次数,如果超过1,则有重复,那么从左侧滑出窗口,直到ch次数变为1,然后更新。

如果没有超过1,说明没有重复,直接更新

class Solution {
public:
    int lengthOfLongestSubstring(string s)
     {
        int hash[128]={0};
        int left=0,right=0,n=s.size();
        int ret=0;
        while(right<n)
        {
            hash[s[right]]++;
            while(hash[s[right]]>1)//判断进入
            {
                hash[s[left++]]--;//出窗口,然后左边移动
            }
            ret = max(ret,right-left+1);
            right++;//
        }
        return ret;
    }     
};

第三题:最大连续1的个数

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

6e59a658da7b48f79a8752b667e90d43.png

思路:这题,

不要去想怎么翻转,不要把问题想的很复杂,这道题的结果??就是?段连续的 1 中间塞了 k
个 0 嘛。因此,我们可以把问题转化成:求数组中?段最?的连续区间,要求这段区间内 0 的个数不超 过 k 个。
因此先初始化一些变量,然后right小于数组大小就一直循环,先进入窗口,然后统计,检查0是否超标,不超标就计数,超标就依次把左侧元素滑出窗口,直到0个数正常,然后right++处理下一个。
class Solution
{
public:
    int longestOnes(vector<int>& nums, int k)
    {
        int ret = 0;
        for (int left = 0, right = 0, zero = 0; right < nums.size(); right++)
        {
            if (nums[right] == 0) zero++; // 进窗?
            while (zero > k) // 判断
                if (nums[left++] == 0) zero--; // 出窗?
            ret = max(ret, right - left + 1); // 更新结果
        }
        return ret;
    }
}

?

?

?

文章来源:https://blog.csdn.net/2302_80084329/article/details/134979350
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。