今天带来四道题目56. 合并区间 ， 53. 最大子数组和 ， 76. 最小覆盖子串 ， 2129. 将标题首字母大写

56. 合并区间 题目描述：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

本题其实不怎么难，但我的思路不太行，我是想要在原数组上while循环遍历intervals[i][0] <= intervals[i – 1][1]的情况，但是只和前面的比，如果当前数组是能够合并的数组的开头，那就会重复添加数组了。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() <= 1) return intervals;
        sort(intervals.begin(), intervals.end(), [](const vector<int>& i, const vector<int>& j){
            return i[0] < j[0];
        });
        vector<vector<int>> result;
        if (intervals[1][0] > intervals[0][1]) result.push_back({intervals[0][0], intervals[0][1]});
        for (int i = 1; i < intervals.size(); i++){
            if (intervals[i][0] <= intervals[i - 1][1]){
                while (i < intervals.size() && intervals[i][0] <= intervals[i - 1][1]){
                    intervals[i][0] = intervals[i - 1][0];
                    intervals[i][1] = max(intervals[i][1], intervals[i - 1][1]);
                    i++;
                    
                    }
                    i--;
            }
            result.push_back({intervals[i][0], intervals[i][1]});
        }
        return result;
    }
};

所以最好的办法还是不要在原数组上进行修改，直接在result数组上进行修改。

result.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++){
            if (intervals[i][0] <= result.back()[1]){
                result.back()[1] = max(intervals[i][1], result.back()[1]);
            }else{
                result.push_back(intervals[i]);
            }
        }

这样就能够兼顾当前数组作为能够合并的数组的开头的情况了。

53. 最大子数组和 题目描述：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组

是数组中的一个连续部分。

示例：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

本题用贪心很好做，但不是那么好想，贪心本身就没什么套路，我觉得贪心最终考察的还是我们对规律的敏感度。

主要解法就是前面的和于当前数相加，如果和大于记录最大值，就更新，小于0，和就置零。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            count += nums[i];
            if (count > result) { 
                result = count;
            }
            if (count <= 0) count = 0;
        }
        return result;
    }
};

还有一种方法就是递归算法，和贪心其实相差不大.

dp数组的定义取的是以下标为i的元素作为结尾的最大序列和。

但整个数组的最大序列和可能是以任何下标为i的元素作为结尾的。所以需要一个result数组记录最大值。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size());
        int result = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < nums.size(); i++){
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            result = result > dp[i] ? result : dp[i];
        }
        return result;
    }
};

76.最小覆盖子串 题目描述：

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

示例：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

本题比较适合哈希表＋滑动窗口的做法，具体就是先把t字符串的字符都先放入哈希表中，再用滑动窗口把s字符串的字符一个个放入滑动窗口中，同时也放入哈希表中，每次放入对比哈希表中s字符串是否有足够的字符来凑成t字符串，如果够的话，就先停止将字符放入滑动窗口的操作，先将滑动窗口的左边界进行更新，来寻找最小的子串，如果当前左边界去除后，滑动窗口不再能凑出t字符串，就说明我们已经找到了目前的最小子串了，而在这次左边界去除之前我们已经提前将最小子串的左边界存储起来了。

class Solution {
public:
    unordered_map<char, int> tstr, sstr;
    bool check(){//检查函数，用于判断滑动窗口是否能够凑出t字符串
        for (auto tchar : tstr){
            if (tchar.second > sstr[tchar.first]) return false;
        }
        return true;
    }
    string minWindow(string s, string t) {
        int n1 = s.size(), n2 = t.size();
        if (n1 < n2) return "";
        int len = INT_MAX;//最小子串的长度，要求最小，就初始化成最大
        int ans_left = -1;//最小子串的左边界
        for (auto tchar : t) ++tstr[tchar];//将t字符串先放入哈希表，用于后面与滑动窗口比较
        int left = 0, right = 0;//滑动窗口左右边界
        for (int right = 0; right < n1; right++){
            ++sstr[s[right]];//从滑动窗口的右边界将字符加入到哈希表中，用于后面与t字符的哈希表进行比较
            if (tstr.find(s[right]) != sstr.end()){//如果当前字符在t字符的哈希表中出现，则可以开始将两个哈希表进行比较
                while (check() && left <= right){//两哈希表比较需要滑动窗口能够完全凑出t字符串
                    if (len > right - left + 1){//如果滑动窗口的大小比最小子串的长度还要小，就更新最小子串的长度和左边界
                        ans_left = left;
                        len = right - left + 1;
                    }
                    --sstr[s[left]];//开始缩小滑动窗口的左边界来查找最小的子串
                    left++;//缩小后如果还能够通过check函数，滑动窗口还能够凑出t字符串，就会通过while循环继续查找最小子串
                }
            }
        }
        if (ans_left == -1) return "";
        else return s.substr(ans_left, len);
    }
};

2129.将标题首字母大写 题目描述：

给你一个字符串 title ，它由单个空格连接一个或多个单词组成，每个单词都只包含英文字母。请你按以下规则将每个单词的首字母 大写 ：

• • 如果单词的长度为 1 或者 2 ，所有字母变成小写。
  • 否则，将单词首字母大写，剩余字母变成小写。

请你返回 大写后 的 title 。、

示例：

输入：title = "capiTalIze tHe titLe"
输出："Capitalize The Title"
解释：
由于所有单词的长度都至少为 3 ，将每个单词首字母大写，剩余字母变为小写。

本题虽然是个简单题，但还是耗费了我挺长时间的，我的思路是先把单词一个个放进数组里，然后在遍历数组，把大写的字母都变成小写，再把大于两个字母的单词的首字母给换成大写

首先是用快慢指针寻找单词，并将其放入数组：

int slow = 0;
        vector<string> words;
        for (int fast = 0; fast < title.size(); fast++){
            if (title[fast] == ' '){
                string s = title.substr(slow, fast - slow);
                words.push_back(s);
                slow = fast + 1;
            }
            else if(fast == title.size() - 1){
                string s = title.substr(slow, fast - slow + 1);
                words.push_back(s);
            }
        }

for (int i = 0; i < words.size(); i++){
            for (int j = 0; j < words[i].size(); j++){
                if (words[i][j] < 'a'){
                    words[i][j] = words[i][j] - 'A' + 'a';
                }
            }
            if (words[i].size() < 3) continue;
            words[i][0] = words[i][0] - 'a' + 'A';
        }

string result;
        for (int i = 0; i < words.size(); i++){
            result = result + words[i] + ' ';
        }
        result = result.substr(0, result.size() - 1);
        return result;