前言

看了一下，今天要写的这道滑动窗口是hard的，只能自己模仿试试了，加深滑动窗口的理解，另外我发现让ChatGPT读代码真的好方便，而且比较准确，也能举一反三，小白狂喜

76. 最小覆盖子串

• 官方题解给的动图，也是滑动窗口的思路，右边界先，左边界后
• 重点在于t可能有重复字符，需要有判断字符频次的哈希表

• class Solution {
  public:
      string minWindow(string s, string t) {
          // 声明两个哈希表，tmap和smap，用于存储t和s中出现的字符以及对应的数量
          unordered_map<char, int> smap, tmap;
          int left = 0, correct = 0; // left指向当前窗口的左端点，correct表示在当前窗口内已经匹配上的字符数量
          // 初始化res为s串加一个最大字符串，用于记录当前满足条件的最小子串
          string res = s + "initialize a max string";
          // 对于t制作字符出现数的字典
          for (const auto &item: t)
              ++tmap[item]; // 遍历t串中的所有字符，将其加入到tmap哈希表中，并记录其出现次数
  
          // 遍历s串中的每个字符
          for (int right = 0; right < s.size(); ++right) {
              // 将当前字符添加到smap中，即记录当前窗口内字符的出现次数
              ++smap[s[right]];
              // 如果当前字符是t串中存在的字符，并且在smap中的数量不超过tmap中的数量，则匹配成功
              if (smap[s[right]] <= tmap[s[right]])
                  ++correct;
              // 当前窗口内已经包含了t中所有字符，需要缩短左边界
              while (left < right && smap[s[left]] > tmap[s[left]])
                  --smap[s[left++]]; // 将左边界对应的字符移出窗口
              // 当前窗口内已经满足t串的所有字符，更新res
              if (correct == t.size()){
                  if (right - left + 1 < res.size())
                      res = s.substr(left, right - left + 1); // 更新最小子串
              }
          }
          // 如果res没有被更新，则说明没有找到符合条件的子串
          return res == s + "initialize a max string" ? "" : res;
      }
  };
  

59. 螺旋矩阵 II

• 创建矩阵赋值，左闭右开，不难但要求边界逻辑清楚

 

 

 

• class Solution {
  public:
      vector<vector<int>> generateMatrix(int n) {
          vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
          int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
          int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
          int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
          int count = 1; // 用来给矩阵中每一个空格赋值
          int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
          int i,j;
          while (loop --) {
              i = startx;
              j = starty;
  
              // 下面开始的四个for就是模拟转了一圈
              // 模拟填充上行从左到右(左闭右开)
              for (j = starty; j < n - offset; j++) {
                  res[startx][j] = count++;
              }
              // 模拟填充右列从上到下(左闭右开)
              for (i = startx; i < n - offset; i++) {
                  res[i][j] = count++;
              }
              // 模拟填充下行从右到左(左闭右开)
              for (; j > starty; j--) {
                  res[i][j] = count++;
              }
              // 模拟填充左列从下到上(左闭右开)
              for (; i > startx; i--) {
                  res[i][j] = count++;
              }
  
              // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
              startx++;
              starty++;
  
              // offset 控制每一圈里每一条边遍历的长度
              offset += 1;
          }
  
          // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
          if (n % 2) {
              res[mid][mid] = count;
          }
          return res;
      }
  };

 54. 螺旋矩阵

•  题解里大佬设定边界的写法，真的如同“疏通了我多年的便秘”

• class Solution {
  public:
      vector<int> spiralOrder(vector<vector<int>>& matrix) {
          vector <int> ans;
          if(matrix.empty()) return ans; //若数组为空，直接返回答案
          int u = 0; //赋值上下左右边界
          int d = matrix.size() - 1;
          int l = 0;
          int r = matrix[0].size() - 1;
          while(true)
          {
              for(int i = l; i <= r; ++i) ans.push_back(matrix[u][i]); //向右移动直到最右
              if(++ u > d) break; //重新设定上边界，若上边界大于下边界，则遍历遍历完成，下同
              for(int i = u; i <= d; ++i) ans.push_back(matrix[i][r]); //向下
              if(-- r < l) break; //重新设定有边界
              for(int i = r; i >= l; --i) ans.push_back(matrix[d][i]); //向左
              if(-- d < u) break; //重新设定下边界
              for(int i = d; i >= u; --i) ans.push_back(matrix[i][l]); //向上
              if(++ l > r) break; //重新设定左边界
          }
          return ans;
      }
  };

 数组总结

• 二分法：O(n) → O(logn)，循环不变量原则，常考题
• 双指针法：O(n2) → O(n)，一个快指针和慢指针在一个for循环下完成两个for循环的工作
• 滑动窗口：O(n2) → O(n)，根据当前子序列和大小的情况，不断调节子序列的两端位置
• 模拟行为：单纯模拟，循环不变量原则，常见题，代码尽量简洁

 后言

今天整整刷了一下午了！明天开链表啦~数据结构这边还没撕过代码呢，希望能学清楚吧。