东莞城乡建设网站,asp 微信网站,网站建设项目团队,铜陵专业网站制作公司本篇文章继续和大家一起刷算法题 第一题
题目链接
. - 力扣#xff08;LeetCode#xff09;
题目解析 题目要求#xff1a;
这是一个连续的子数组
计算子数组内元素的和#xff0c;若数组内元素的和符合 target的值并且该子数组的长度是最短的#xff0c;则返回…本篇文章继续和大家一起刷算法题 第一题
题目链接
. - 力扣LeetCode
题目解析 题目要求
这是一个连续的子数组
计算子数组内元素的和若数组内元素的和符合 target的值并且该子数组的长度是最短的则返回该长度
代码原理
原理一暴力枚举 原理二滑动窗口 代码编写
对应原理一
class Solution {
public: int minSubArrayLen(int target, vectorint nums) { int len INT_MAX; for(int left 0; left nums.size(); left) { int sum 0; for(int right left; right nums.size(); right) { sum nums[right]; if(sum target) { len min(len, right - left 1); break; } } } if(len INT_MAX) { len 0; } return len; }
};
这里值得注意的是暴力枚举会超过时间限制但并不是说这种方法是错误的 对应原理二
class Solution {
public: int minSubArrayLen(int target, vectorint nums) { int left 0, right 0, sum 0, len INT_MAX; while(right nums.size()) { sum nums[right];//进窗口 while(sum target)//判断 {//4 len min(len, right 1 - left);//更新结果 sum - nums[left];//出窗口 } right; } if(len INT_MAX) { len 0; } return len; }
};
本题总结
1. 首这个解法叫滑动窗口本质是同向双指针
2. 使用这个解法的原因是利用了单调性
3.滑动窗口的正确性利用的单调性规避了没必要的枚举行为
4.枚举二字算是在博主的文章中第一次出现那么我也解释枚举是什么意思枚举就是将每一种情况都一一列举出来
第二题
题目链接
3. 无重复字符的最长子串 - 力扣LeetCode
题目解析 题目要求返回字符串且字符串内的字符不能有相同
代码原理
方法二滑动窗口 总而言之如果nums[right]若与hash表中的字符相同则出窗即在哈希表中删除
代码编写
方法二滑动窗口
class Solution {
public: int lengthOfLongestSubstring(string s) { int n s.size(),len 0; int hash[128] {0}; for(int left 0, right 0; right n; right) { hash[s[right]]; while(hash[s[right]] 1) { hash[s[left]]--; } len max(len, right - left 1); } return len; }
};
第三题
题目链接
数组中两个字符串的最小距离__牛客网
题目解析 代码原理
思路一暴力枚举 思路二贪心算法 代码编写
对应法二
#include iostream #includestring using namespace std;
int main() { int n 0; int prev1 -1, prev2 -1,min_distance 0x3f3f3f3f; cin n; string strs, str1, str2; cin str1 str2; for(int i 0; i n; i) { cin strs; if(strs str1) { if(prev2 ! -1) { min_distance min(min_distance, i - prev2); } prev1 i; } else if(strs str2) { if(prev1 ! -1) { min_distance min(min_distance, i - prev1); } prev2 i; } } if(min_distance 0x3f3f3f3f) cout -1 endl; else cout min_distance endl; return 0; } // 64 位输出请用 printf(%lld)
本篇文章的算法题就先讲到这里我们下期文章再见。 都看到这了给个三联再走呗谢谢啦
