代码随想录2.5——数组：904水果成篮、76最小覆盖子串

1.904水果成篮

参考：LeetCode 904. 水果成篮（滑动窗口），力扣904: medium

1.1.题目

1.2.解答

一开始毫无思路，看起来好像很复杂。实际上这个和寻找长度最小的子数组是一样的，都是需要遍历整个数组，而且在其中寻找连续的最长/最短的子数组。

思路也是非常相似的：

• 用双指针构成一个滑动窗口，右边的指针移动负责遍历整个大的数组，
• 然后左边的指针在不满足寻找的子数组要求的时候向右移动，直到满足要求。
• 每次找到一个满足要求的子数组，就把它和最大/最小的长度进行比较，然后判断是否要更新最大/最小值。
• 最后，右边的指针遍历到大数组的尾部，得到最后一个子数组，这个问题也就遍历求解完成了。

下面的解法是参考了上面的博客，但是进行了一下修改，更加简洁。

class Solution
{
public:
    int totalFruit(vector<int> &fruits)
    {
        unordered_map <int, int> basket;   // <篮子中的水果种类， 该种水果的个数>
        
        int max = -1;   // 最终返回的结果
        int left = 0;  // 左边的索引
        for(int right = 0; right < fruits.size(); right++)
        {
            basket[fruits[right]]++;   // 该种水果的个数+1

            while(basket.size() > 2)
            {
                basket[fruits[left]]--;   // 左边界的滑出，该种水果数量--
                if(basket[fruits[left]] == 0)  // 如果该种水果的数量=0，说明没有这种水果了
                {
                    basket.erase(fruits[left]);
                }
                left++;   // 左边的索引++
            }

            // 运行到此，窗口中的水果种类一定<=2
            int len = right - left + 1;   // len就是水果的个数，注意不要忘了+1，因为right/left都是索引
            max = len > max ? len : max;
        }
        return max;
    }
};

2.76最小覆盖子串

参考：LeetCode 76. 最小覆盖子串【c++/java详细题解】

2.1.题目

2.2.解答

这道题目是一道hard题，确实比较难。虽然整体的思路和滑窗的思路是一样的，但是由于滑窗中的内容不是连续的，所以处理起来和前面的不一样。

详细的解答看上面的参考博客吧，代码如下，注意仔细看注释。

class Solution
{
public:
    string minWindow(string s, string t) 
    {
        unordered_map <char, int> t_map;   // <字符，字符个数>
        unordered_map <char, int> s_map;   // <字符，字符个数>

        // 先统计t中字符的情况
        for(auto& t_char:t)
        {
            t_map[t_char]++;
        }

        int left = 0;  // 左边的索引
        int cnt = 0;  
        string res;    // 最终返回的字符串
        for(int right = 0; right < s.size(); right++)
        {
            s_map[s[right]]++;    // 这个字符的个数++
            
            // 注意这里的判断和水果成篮的判断又不一样了，因为这里在s字符串中寻找指定的字符可以是不连续的
            if(s_map[s[right]] <= t_map[s[right]])
                cnt++;   // 满足条件的字符类型个数++
            
            // 由于窗口右移的一下，可能导致某种类型的字符个数超过需要的个数，因此需要缩减窗口
            // 1.比如[A, B, C, D, A]，此时如果滑动到了最后一个A，那么A的总个数就变成了3，可能大于需要的个数
            // 2.另一中情况是根本不需要这个字符。比如1中把A滑出去之后，变成[B, C, D, A]，假设我不需要B，
            //   那么此时会继续把B滑出去
            while(s_map[s[left]] > t_map[s[left]])
                s_map[s[left++]]--;   // 一直右移left，并且滑窗中这个字符的个数-1

            if(cnt == t.size())
            {
                if(res.empty() || right - left + 1 < res.size())
                    res = s.substr(left, right - left + 1);
            }
        }
        return res;
    }
};

理解：

比如s是[A, A, B, C, D, A, C, A, B, D]，t是[A, B, D]，那么一开始满足cnt = t.size()的滑动窗口是[A, A, B, C, D]，但是显然最终的答案应该是末尾的[A, B, D]。看从开始的窗口进行一步一步进行滑动：

• right继续右移到A，变成[A, A, B, C, D, A]；此时发现左边A出现次数为3>1，要把左边的A滑掉，变成[A, B, C, D, A]；此时发现左边A出现次数为2>1，仍然要把左边的A滑掉，变成[B, C, D, A]；
• right继续右移到C，变成[B, C, D, A, C]，此时左边界不会移动。
• right继续右移到A，变成[B, C, D, A, C, A]，此时左边界不会移动，。
• right继续右移到B，变成[B, C, D, A, C, A, B]；此时发现左边B出现的次数为2>1，因此把左边的B划掉，变成[ C, D, A, C, A, B]；此时发现左边C出现的次数为2>0，因此把左边的C划掉，变成[ D, A, C, A, B]
• right继续右移到D，变成[D, A, C, A, B, D]；此时发现左边D出现的次数为2>1，因此把左边的D划掉，变成[ A, C, A, B, D]；此时发现左边A出现次数为2>1，要把左边的A滑掉，变成[C, A, B, D]；此时发现左边C出现次数为1>0，要把左边的C滑掉，变成[A, B, D]，即为最终答案！

从上面详细的步骤可以看到，代码中的cnt计数和while循环删除，是最重要的两个点。while循环删除，保证了最左边的元素在滑窗中出现的次数一定和t中出现的次数相等（出现0次或者n次），然后只要是到了cnt之后，后面滑窗中元素的个数一定是包含t中所有元素的，所以后面会一直满足，而无序对cnt再进行操作。

3.54螺旋矩阵

3.1.题目

3.2.解答(自己的解法存在问题)

先没有看别人的解答，自己写了一个，整体思路还是参考59.螺旋矩阵II来写的，但是这里的矩阵可能不是方阵，导致还是有很多的corner case需要讨论和处理，最后试了好几次才通过，感觉自己的这种解法还是没有找到正确的思路，正确的思路应该一个统一的解法就足够了。

class Solution
{
public:
    vector<int> spiralOrder(vector<vector<int>> &matrix)
    {
        // 顺时针螺旋，使用[left, right)的形式
        int m = matrix.size();     // 矩阵的行
        int n = matrix[0].size();  // 矩阵的列
        vector<int> res(m*n, 0);   // 最终结果的初始化！
        int min_mn = m < n ? m : n;
        int loop = min_mn / 2;
        int offset = 1;  // 到头差多少

        int start_x = 0;
        int start_y = 0;
        int index = 0;
        while(loop--)
        {
            int i = start_x;    // i是行
            int j = start_y;    // j是列
            // 上边行
            for(; j < n - offset; j++)
            {
                res[index++] = matrix[i][j];
            }

            // 右边列
            for(; i < m - offset; i++)
            {
                res[index++] = matrix[i][j];
            }
    
            // 下边行
            for(; j > start_y; j--)
            {
                res[index++] = matrix[i][j];
            }
           
            // 左边列
            for(; i > start_x; i--)
            {
                res[index++] = matrix[i][j];
            }
            
            //更新完
            start_x++;
            start_y++;
            offset++;
        }

        // 一定要加上这个部分，不加上的话还是存在考虑不周的问题，比如2行3列的矩阵，其实一个循环就解决了，但是
        // 如果这里不判断一下的话，下面会多计算一列，导致数组越界，存在问题。
        // 感觉这个题目还是没有找到统一的套路和方法，还是要看一下别人的博客
        if(index >= m*n)
            return res;

        // 针对奇数还是要单独处理
        if(m % 2 || n % 2)
        {
            if(m == n)
            {
                res[index] = matrix[m/2][n/2];
            }
            else if(m > n)   // 以n为准，还差右边一列
            {
                // 右边列
                for(int i = start_x; i <= m - offset; i++)
                {
                    res[index++] = matrix[i][start_y];
                }
            }
            else   // 以m为准，还差上面一行
            {
                // 上边行
                for(int j = start_y; j <= n - offset; j++)
                {
                    res[index++] = matrix[start_x][j];
                }
            }
        }

        return res;
    }
};