C++算法第五天
本篇文章继续和大家一起刷算法题
第一题
题目链接
. - 力扣（LeetCode）
题目解析
题目要求：
这是一个连续的子数组
计算子数组内元素的和，若数组内元素的和符合 >= target的值并且该子数组的长度是最短的，则返回该长度
代码原理
原理一：暴力枚举
原理二：滑动窗口
代码编写
对应原理一
class Solution {
public:
int minSubArrayLen(int target, vector<int>& 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, vector<int>& 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>
#include<string>
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")
本篇文章的算法题就先讲到这里，我们下期文章再见。
都看到这了，给个三联再走呗，谢谢啦！！！
