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

本篇文章的算法题就先讲到这里，我们下期文章再见。

都看到这了，给个三联再走呗，谢谢啦！！！