黄冈网站优化公司哪家好,wordpress ftp备份,聚名网官网登录,瓷器网站源码顾得泉#xff1a;个人主页
个人专栏#xff1a;《Linux操作系统》 《C/C》 《LeedCode刷题》
键盘敲烂#xff0c;年薪百万#xff01; 一、长度最小的子数组
题目链接#xff1a;长度最小的子数组
题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。…
顾得泉个人主页
个人专栏《Linux操作系统》 《C/C》 《LeedCode刷题》
键盘敲烂年薪百万 一、长度最小的子数组
题目链接长度最小的子数组
题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., 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 1091 nums.length 1051 nums[i] 105
解法
解法一暴力求解)(会超时):
算法思路: 「从前往后」枚举数组中的任意一个元素把它当成起始位置。然后从这个「起始位置」开始然后寻找一段最短的区间使得这段区间的和「大于等于」目标值。将所有元素作为起始位置所得的结果中找到「最小值」即可。
解法二滑动窗口):
算法思路: 由于此问题分析的对象是一段连续的区间因此可以考虑「滑动窗口」的思想来解决这道题。让滑动窗口满定:从i位置开始窗口内所有元素的和小于target(那么当窗口内元素之和第一次大于等于国标值的时候就是i位置开始满足条件的最小长度)。
做法: 将右端元素划入窗口中统计出此时窗口内元素的和: 如果窗口内元素之和大于等于target:更新结果并且将左端元素划出去的同时继续判断是否满足条件并更新结果(因为左端元素可能很小划出去之后依旧满足条件) 如果窗口内元素之和不满足条件: right另下一个元素进入窗口。
为何滑动窗口可以解决问题,并且时间复杂度更低? 这个窗口寻找的是:以当前窗口最左侧元素记为left1为基准符合条件的情况。也就是在这道题中从left1开始满足区间和sum target时的最右侧(记为right1)能到哪里。 我们既然已经找到从left1开始的最优的区间那么就可以大胆舍去left1。但是如果继续像方法一样重新开始统计第二个元素(left2往后的和势必会有大量重复的计算因为我们在求第一段区间的时候已经算出很多元素的和了这些和是可以在计算下次区间和的时候用上的)。 此时rigth1的作用就体现出来了我们只需将left1这个值从sum中剔除。从right1这个元素开始往后找满足left2元素的区间此时ight也有可能是满足的因为left1可能很小。sum剔除掉left1之后依旧满定大于等于target )。这样我们就能省掉大量重复的计算。 这样我们不仅能解决问题而且效率也会大大提升。 时间复杂度:虽然代码是两层循环但是我们的left 指针和right指针都是不回退的两者最多都往后移动n次。因此时间复杂度是o(N)。
代码实现
class Solution
{
public:int minSubArrayLen(int target, vectorint 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];left;}}return len INT_MAX ? 0 : len;}
}; 二、无重复字符的最长字串
题目链接无重复字符的最长子串
题目描述 给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc 所以其长度为 3。示例 2:
输入: s bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b 所以其长度为 1。示例 3:
输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke 所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。提示
0 s.length 5 * 104s 由英文字母、数字、符号和空格组成
解法
算法思路: 研究的对象依旧是一段连续的区间因此继续使用「滑动窗口」思想来优化。让滑动窗口满足:窗口内所有元素都是不重复的。
做法: 右端元素ch进入茵口的时候哈希表统计这个字符的频次: 如果这个字符出现的频次超过1说明窗口内有重复元素那么就从左侧开始划出窗口直到ch这个元素的频次变为1然后再更新结果。 如果没有超过1,说明当前窗口没有重复元素可以直接更新结果
代码实现
class Solution
{
public:int lengthOfLongestSubstring(string s) {int hash[123] {0};int left 0, right 0, ret 0, n s.size();while(right n){hash[s[right]];while(hash[s[right]] 1)hash[s[left]]--;ret max(ret , right - left 1);right;}return ret;}
}; 三、最大连续1的个数Ⅲ
题目链接最大连续1的个数 III
题目描述 给定一个二进制数组 nums 和一个整数 k如果可以翻转最多 k 个 0 则返回 数组中连续 1 的最大个数 。
示例 1
输入nums [1,1,1,0,0,0,1,1,1,1,0], K 2
输出6
解释[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1最长的子数组长度为 6
示例 2
输入nums [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K 3
输出10
解释[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1最长的子数组长度为 10提示
1 nums.length 105nums[i] 不是 0 就是 10 k nums.length
解法
算法思路: 不要去想怎么翻转不要把问题想的很复杂这道题的结果就是一段连续的1中间塞了k个0。 因此我们可以把问题转化成:求数组中一段最长的连续区间要求这段区间内的0个数不超过k个。 既然是连续区间可以考虑使用「滑动窗口」来解决问题。
算法流程:
a.初始化一个大小为2的数组就可以当做哈希表hash 了;初始化一些变量left 0right 0 , ret 0;
b.当right小于数组大小的时候一直下列循环: i.让当前元素进入窗口顺便统计到哈希表中; ii.检查0的个数是否超标: 如果超标依次让左侧元素滑出窗口顺便更新哈希表的值直到的个数恢复正常; iii.程序到这里说明窗口内元素是符合要求的更新结果;iv. right处理下一个元素;
c.循环结束后ret存的就是最终结果。
代码实现
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;}
}; 结语今日的刷题分享到这里就结束了希望本篇文章的分享会对大家的学习带来些许帮助如果大家有什么问题欢迎大家在评论区留言~~~
