如何诊断网站,宣城建设网站,电子商务后悔死了,平面设计培训班哪家好一、长度最小的子数组
题目链接#xff1a;
209. 长度最小的子数组 - 力扣#xff08;LeetCode#xff09;
题目介绍#xff1a;
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl1, .…一、长度最小的子数组
题目链接
209. 长度最小的子数组 - 力扣LeetCode
题目介绍
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl1, ..., numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。 思路1暴力枚举
每次固定一个起始下标往后遍历求和直到大于target停止并更新最小长度
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;}
};思路2对思路1进行优化滑动窗口 思路1在从一个下标开始计算完后sum会重新归为0从下一个下标开始重新计算求和但是这里有一个问题第一次求和与第二次求和只相差了一个元素的值如果直接从头开始就会产生重重复的计算所以每当我们从一个下标计算完最小长度后可以利用单调性不让sum归0也不改变end了直接让sum - nums[start] 然后让start这样就可以继续向后计算了但是要注意的是最左边的值可能是一个很小的值甚至sum减去它以后还是满足大于target的所以这里不能用if判断而是用一个while循环。 这样在一个连续空间上两个指针同向移动就叫做滑动窗口
时间复杂度虽然代码是两层循环但是我们的 left 指针和 right 指针都是不回退的两者最多都往后移动 n 次。因此时间复杂度是 O(N) 。
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int minlenINT_MAX;int sum0;for(int left0,right0;rightnums.size();right){sumnums[right];while(sumtarget){minlenmin(minlen,right-left1);sum-nums[left];left;}}return minlenINT_MAX?0:minlen;;}
};
二、无重复字符的最长子串
题目链接
3. 无重复字符的最长子串 - 力扣LeetCode
题目介绍:
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。 0 s.length 5 * 104s 由英文字母、数字、符号和空格组成
思路1暴力枚举
依旧是从一个下标开始遍历判断是否出现重复字符串可以利用哈希表当hash[n]1时就说明有重复字符了
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;}
};
思路2滑动窗口
研究的对象依旧是⼀段连续的区间因此继续使用「滑动窗口」思想来优化。
让滑动窗口满足窗口内所有元素都是不重复的。 做法
右端元素 ch 进⼊窗口的时候哈希表统计这个字符的频次
如果这个字符出现的频次超过 1 说明窗口内有重复元素那么就从左侧开始划出窗口 直到 ch 这个元素的频次变为 1 然后再更新结果。如果没有超过1 说明当前窗口没有重复元素可以直接更新结果
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] {0};int maxlen 0;for (int left 0, right 0; right s.size(); right) {hash[s[right]];while (hash[s[right]] 1) {hash[s[left]]--;left;}maxlen max(maxlen, right - left 1);}return maxlen;}
};三、最大连续 1 的个数 III
题目链接
1004. 最大连续1的个数 III - 力扣LeetCode
题目介绍
给定一个二进制数组 nums 和一个整数 k假设最多可以翻转 k 个 0 则返回执行操作后 数组中连续 1 的最大个数 。 思路
不用想着翻转元素这样反而会把题目搞复杂转变一下思路这个题目就是找一个0的个数不大于k个的连续区间的最大长度同样的在一段连续区间上操作可以采用滑动窗口。
定义一个变量num用于记录窗口中0的个数每次让nums[right]入窗口如果他的值是0的话就让num如果numk,就从左边出窗口直到 num k,再更新结果如果入窗口后num还是小于k的说明这段区间是符合要求的可以直接更新结果
class Solution {
public:int longestOnes(vectorint nums, int k) {int num0;int maxlenINT_MIN;for(int left0,right0;rightnums.size();right){if(nums[right]0)num;while(numk){if(nums[left]0){left;num--;}else{left;}}maxlenmax(maxlen,right-left1);}return maxlen;}
};
四、将 x 减到 0 的最小操作数
题目链接
1658. 将 x 减到 0 的最小操作数 - 力扣LeetCode
题目介绍
给你一个整数数组 nums 和一个整数 x 。每一次操作时你应当移除数组 nums 最左边或最右边的元素然后从 x 中减去该元素的值。请注意需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 返回 最小操作数 否则返回 -1 。
1 nums.length 1051 nums[i] 1041 x 109
思路
这个题目如果从正面想的话比较复杂因为它是从数组两边进行操作的所以我们可以转变一下思路将这个题变为找一段最长连续区间的和sum - x这样最小操作数就是数组的长度减去这个连续区间的长度了。
首先计算出数组的和然后求出sum-x如果target的值都小于0了就返回1因为数组中的元素都是大于0的。
接下来就可以让right入窗口了如果和大于target的话就出窗口直到和小于等于target要注意更新结果要有一个判断条件就是 sumtarget
class Solution {
public:int minOperations(vectorint nums, int x) {//转变思路求一段连续空间中和为sum-x的长度int sum0;for(auto e: nums){sume;}int targetsum-x;if(target0)return -1;int maxlen-1;sum0;for(int left0,right0;rightnums.size();right){sumnums[right];while(sumtarget){sum-nums[left];}if(sumtarget)maxlenmax(maxlen,right-left1);}if(maxlen-1)return -1;elsereturn nums.size()-maxlen;}
};
五、水果成篮
题目链接
904. 水果成篮 - 力扣LeetCode
题目介绍
你正在探访一家农场农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而农场的主人设定了一些严格的规矩你必须按照要求采摘水果
你只有 两个 篮子并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘你必须从 每棵 树包括开始采摘的树上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次你将会向右移动到下一棵树并继续采摘。一旦你走到某棵树前但水果不符合篮子的水果类型那么就必须停止采摘。
给你一个整数数组 fruits 返回你可以收集的水果的 最大 数目。 思路
这个题目依旧是操作一个连续的空间也要遍历所以可以采用滑动窗口让滑动窗口维护只有两类水果。
当一个水果入窗口后可以将他的种类用哈希表维护起来这样当一个新水果进来后哈希表的长度就会加1如果哈西表的长度大于2的话说明窗口中存在第三种水果了那就从左边出窗口直到哈希表的长度小于2
class Solution {
public:int totalFruit(vectorint fruits) {unordered_mapint,int m;int num0;for(int left0,right0;rightfruits.size();right){m[fruits[right]];while(m.size()2){m[fruits[left]]--;if(m[fruits[left]]0)m.erase(fruits[left]);left;}nummax(num,right-left1);}return num;}
};
