莆田建站服务,珠宝 网站欣赏,怎么查询企业信息,装饰装修工程第一题#xff1a;长度最小的子数组
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
思路#xff1a;
第一想法肯定时暴力枚举#xff0c;枚举数组任何一个元素#xff0c;把他当起始位置#xff0c;然后从起始位置找最短区间#xff0c;使得…第一题长度最小的子数组
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路
第一想法肯定时暴力枚举枚举数组任何一个元素把他当起始位置然后从起始位置找最短区间使得区间和大于等于目标值
利用两个嵌套for循环如果符合条件就记录然后更新结果返回
class Solution {
public:int minSubArrayLen(int target, vectorint 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, vectorint nums) {int nnums.size(),sum0,lenINT_MAX;for(int left0,right0;rightn;right){sumnums[right];while(sumtarget){lenmin(len,right-left1);sum-nums[left];}}return lenINT_MAX?0:len;}
};
来自一个力扣大佬的形象解释左右指针中间窗口的sum为两指针的“共同财产”就是右指针一直在努力工作挣钱好不容易共同财产大过target记录一下两指针之间的距离结果左指针就开始得瑟挥霍不停花钱往右移动结果花钱一直花到sum又小过target此时右指针不得不再次出来工作不停向右移动周而复始最后取左右指针离得最近的时候 第二题⽆重复字符的最⻓⼦串medium
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 法一依旧是暴力
即先固定一个然后遍历所有创建个哈希表用来记录出现的次数如果大于一则说明出现重复那么就跳出当前循环进入下一个固定的数进行遍历否则就记录此刻长度
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;// 如果没有重复就更新 retret 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 left0,right0,ns.size();int ret0;while(rightn){hash[s[right]];while(hash[s[right]]1)//判断进入{hash[s[left]]--;//出窗口然后左边移动}ret max(ret,right-left1);right;//}return ret;}
};
第三题最大连续1的个数
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 思路这题
不要去想怎么翻转不要把问题想的很复杂这道题的结果⽆⾮就是⼀段连续的 1 中间塞了 k 个 0 嘛。因此我们可以把问题转化成求数组中⼀段最⻓的连续区间要求这段区间内 0 的个数不超 过 k 个。 因此先初始化一些变量然后right小于数组大小就一直循环先进入窗口然后统计检查0是否超标不超标就计数超标就依次把左侧元素滑出窗口直到0个数正常然后right处理下一个。 class Solution
{
public:int longestOnes(vectorint 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;}
}
