快速排名网站,黑龙江住房和城乡建设厅网站,重钢建设公司官方网站,网站换模板要怎么做大家好啊,好久没有更新了,最近比较忙,所以来更新初阶算法,正好复习一下,感谢大家的观看,如有错误欢迎指出。 下面我们来看题目吧#xff01; 1.209. 长度最小的子数组
这题大家想必一眼就看出了解法一暴力法
这个解法很简单
代码如下,不做多的解释
class Solution {
publi…大家好啊,好久没有更新了,最近比较忙,所以来更新初阶算法,正好复习一下,感谢大家的观看,如有错误欢迎指出。 下面我们来看题目吧 1.209. 长度最小的子数组
这题大家想必一眼就看出了解法一暴力法
这个解法很简单
代码如下,不做多的解释
class Solution {
public:int minSubArrayLen(int s, vectorint nums) {int n nums.size();if (n 0) {return 0;}int ans INT_MAX;for (int i 0; i n; i) {int sum 0;for (int j i; j n; j) {sum nums[j];if (sum s) {ans min(ans, j - i 1);break;}}}return ans INT_MAX ? 0 : ans;}
};这个解法时间复杂度是O()其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标对于每个开始下标需要遍历其后面的下标得到长度最小的子数组。 但是这不是我们要学的思路,我们要探究的是另一种的解法——滑动窗口
该解法思路
定义两个指针 start 和 end 分别表示子数组滑动窗口窗口的开始位置和结束位置维护变量 sum 存储子数组中的元素和即从 nums[start] 到 nums[end] 的元素和。
初始状态下start 和 end 都指向下标 0sum 的值为 0。
每一轮迭代将 nums[end] 加到 sum如果 sum≥s则更新子数组的最小长度此时子数组的长度是 end−start1然后将 nums[start] 从 sum 中减去并将 start 右移直到 sums在此过程中同样更新子数组的最小长度。在每一轮迭代的最后将 end 右移。
代码如下
class Solution {
public:int minSubArrayLen(int s, vectorint nums) {int n nums.size();if (n 0) {return 0;}int ans INT_MAX;int start 0, end 0;int sum 0;while (end n) {sum nums[end];while (sum s) {ans min(ans, end - start 1);sum - nums[start];start;}end;}return ans INT_MAX ? 0 : ans;}
};
该方法时间复杂度O(n) 2.3. 无重复字符的最长子串 - 力扣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;}
}; 当然,我们知道我们想要的也不是这种解法 解法⼆滑动窗口 算法思路 研究的对象依旧是⼀段连续的区间因此继续使⽤「滑动窗口」思想来优化。 让滑动窗口满⾜窗口内所有元素都是不重复的。 做法右端元素 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;}
}; 3.1004. 最大连续1的个数 III - 力扣LeetCode 思路与算法 不要去想怎么翻转不要把问题想的很复杂这道题的结果⽆⾮就是⼀段连续的 1 中间塞了 k 个 0 嘛。 因此我们可以把问题转化成求数组中⼀段最⻓的连续区间要求这段区间内 0 的个数不超 过 k 个 代码如下 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;}
}; 是不是很简单呢?
