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")