建企业网站 硬件,武夷山住房和城乡建设部网站,wordpress循环文章,苏州建交建设工程有限公司目录 长度最小的子数组
解题思路
代码实现
无重复字符的最大字串
解题思路
代码实现
最大连续1的个数l l l
解题思路
代码实现
将x减到0的最小操作数
解题思路
代码实现 长度最小的子数组
题目链接#xff1a;209. 长度最小的子数组题目描述#xff1a; 给定一个…目录 长度最小的子数组
解题思路
代码实现
无重复字符的最大字串
解题思路
代码实现
最大连续1的个数l l l
解题思路
代码实现
将x减到0的最小操作数
解题思路
代码实现 长度最小的子数组
题目链接209. 长度最小的子数组题目描述 给定一个含有 n 个正整数的数组 nums 和一个正整数 target。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0。 解题思路
解法一暴力求解
枚举所有可能的子数组计算子数组的和检查是否大于等于 target 找到符合题目要求的长度最小的子数组。
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int n nums.size();int ret INT_MAX;for (int left 0; left n; left) {int sum 0;for (int right left; right n; right) {sum nums[right];if (sum target) {ret min(ret, right - left 1);break;}}}return ret INT_MAX ? 0 : ret;}
};
暴力解法简单粗暴但是由于时间复杂度是 O(n ^ 2)一旦数据量比较大必定会超时
解法二滑动窗口
滑动窗口其实也是基于暴力解法优化而来滑动窗口的核心就是想办法让暴力解法中的 right 指针不回退一直往前走。
我们想想这样一个问题在暴力解法中当left和right找到一个合法的子数组后leftright有必要回退到left位置吗答案是没有必要的当left后left和right区间的子数组的和可能大于等于target也可能小于target。我们可以让left一直并在此过程中记录区间长度直到left和right区间的子数组的和小于target然后再让right增大区间长度的和重复上述过程直到遍历完数组。 滑动窗口具体过程如下
1.初始化left和right指针为0。2.进窗口计算区间的和3.判断当区间和大于等于target时找到合法区间更新结果出窗口让left重复判断-更新结果过程直到区间和小于target当区间和小于target时进窗口让right计算区间和。4.重复上述过程直到right遍历完数组。
值得注意的是更新结果这步不是固定的有时候在判断时更新有时候在判断完后再更新。 代码实现
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int sum 0, n nums.size(), 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;}
};
细节由于求的是长度最小的子数组所以len要初始化为INT_MAX不能初始化为0。
时间复杂度O(n)
空间复杂度O(1)
无重复字符的最大字串
题目链接3. 无重复字符的最长子串题目描述 给定一个字符串 s请你找出其中不含有重复字符的最长子串的长度。 解题思路
解法一暴力求解
通过枚举从每个位置开始向后寻找无重复字符的子串能到达的位置记录其中最长的子串长度即可。在寻找无重复子串时可以使用哈希表统计字符出现的频次遇到重复字符时停止。
class Solution {
public:int lengthOfLongestSubstring(string s) {int ret 0; // 记录结果int n s.length();// 枚举从不同位置开始的无重复子串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 max(ret, j - i 1); // 更新结果}}return ret;}
};暴力求解的问题还是时间复杂度是O(n)对于处理数据量比较大的数据时会超时。
解法二滑动窗口
使用滑动窗口使得窗口内的字符不重复。
当窗口右端进入新字符时更新哈希表记录字符频次
如果字符频次大于1则窗口出现重复字符开始从左侧收缩窗口直到字符频次变为1更新结果。如果没有超过1说明没有重复字符直接更新结果。
代码实现
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] { 0 }; // 使用数组模拟哈希表int left 0, right 0, n s.size(), len 0;while(right n){hash[s[right]]; // 将右端字符加入窗口while(hash[s[right]] 1) //判断hash[s[left]]--; //出窗⼝//更新结果len max(len, right - left 1); //让下⼀个元素进⼊窗⼝right; }return len;}
};
细节由于s由英文字母、数字、符号和空格组成不必真的使用unordered_map用一个128大小的数组当作哈希表即可。
时间复杂度O(n)
空间复杂度O(1)
最大连续1的个数l l l
题目链接1004. 最大连续 1 的个数 III题目描述 给定一个二进制数组 nums 和一个整数 k如果可以翻转最多 k 个0则返回数组中连续 1的最大个数。 解题思路
根据题目描述我们可以将其转换为求一段最长的连续子区间其中0的数量不超过k个我们用滑动窗口解决。
1.初始化左右指针left和right以及记录0个数的变量cnt。2.当right向右遍历数组时如果当前元素是0cnt然后判断cnt是否大于cnt大于则让left缩减窗口移除窗口中的0直到cnt小于等于k。3。此时窗口合法更新结果。
代码实现
class Solution {
public:int longestOnes(vectorint nums, int k) {int ret 0, cnt 0, n nums.size();for(int left 0, right 0; right n; right){if(nums[right] 0) cnt; //当前元素为0cnt//当cnt k时移除窗口中的0直到cnt kwhile(cnt k){if(nums[left] 0)cnt--;left; }//更新结果ret max(ret, right - left 1);}return ret;}
};
时间复杂度O(n)
空间复杂度O(1)
将x减到0的最小操作数
题目链接1658. 将 x 减到 0 的最小操作数
题目描述 给你一个整数数组 nums 和一个整数 x。每次操作时你可以移除数组 nums 的最左边或最右边的元素然后从 x 中减去该元素的值。请注意你需要修改数组以供接下来的操作使用。如果可以将 x 恰好减到 0返回最少的操作数否则返回 -1。 解题思路
解法滑动窗口
题目要求的是在数组左端、右端找两段连续且和为x的短数组我们可以将其转换为在数组中找到和为 sum - x 的最长子数组其剩余数组长度就是最小操作数可以使用滑动窗口解决问题。
具体过程如下
1.计算数组的和 sum 然后求出target sum - x。这里有个小细节若target 0说明x sum不可能找到题目要求的最小操作数直接返回-1。2.初始化 left 和 righ t两个指针为0再用一个变量 part_sum 记录区间长度的和。3.当 part_sum target 时减小 part_sumleft直到 part_sum target。4.如果 part_sum target更新最长子数组的长度。5.right增大 part_sum。循环上述过程直到 right 遍历完数组。
代码实现
class Solution {
public:int minOperations(vectorint nums, int x) {//1.计算数组总和int n nums.size(), sum 0;for(auto e : nums) sum e;int len -1, target sum - x, part_sum 0;if(target 0) return -1;//2.使用滑动窗口求出符合条件的最大子数组和for(int left 0, right 0; right n; right){part_sum nums[right];while(left n part_sum target)part_sum - nums[left];if(part_sum target)len max(len, right - left 1);}return len -1 ? -1 : n - len;}
}; 拜拜下期再见
摸鱼ing✨
