LeetCode周赛

291场周赛
- 移除指定数字得到的最大结果">第一题：移除指定数字得到的最大结果
- 必须拿起的最小连续卡牌数">第二题：必须拿起的最小连续卡牌数
- 含最多 K 个可整除元素的子数组">第三题：含最多 K 个可整除元素的子数组
294场周赛
- 表示一个折线图的最少线段数">第三题：表示一个折线图的最少线段数
- 巫师的总力量和">第四题：巫师的总力量和
- 子数组的最小值之和">第四题类似：子数组的最小值之和
78场双周赛
- 找到一个数字的 K 美丽值">第一题：找到一个数字的 K 美丽值
- 分割数组的方案数（前缀和）">第二题：分割数组的方案数（前缀和）
- 毯子覆盖的最多白色砖块数（滑动窗口+贪心）">第三题：毯子覆盖的最多白色砖块数（滑动窗口+贪心）
293场周赛
- 移除字母异位词后的结果数组">第一题：移除字母异位词后的结果数组
- 不含特殊楼层的最大连续楼层数">第二题（排序就行）不含特殊楼层的最大连续楼层数
- 按位与结果大于零的最长组合">第三题：按位与结果大于零的最长组合

291场周赛

第一题：移除指定数字得到的最大结果

主要的问题是不熟练stl中字符串的使用
使用substr(), 和 append(), 很有帮助

AC 代码

class Solution {
public:
  string removeDigit(string number, char digit) {
      int n = number.size();
      string s = "";
      for(int i = 0;i < n;i ++ ){
          if(number[i] == digit){
              string tmp = number.substr(0, i);
              tmp.append(number.substr(i + 1, n - 1));
              if(s < tmp) s = tmp;
          }
      }
      return s;
  }
};

也可以使用贪心来做
- 掌握对string.erase()的使用

AC 代码

class Solution {
public:
  string removeDigit(string number, char digit) {
      int n = number.size();
      bool flag = false;
      for(int i = 0;i < n - 1; i++ ){
          if(number[i] < number[i + 1] && number[i] == digit){
              number.erase(i, 1);
              flag = true;
              break;
          }
      }
      if(!flag){
          for(int i = n - 1;i >= 0;i -- ) {
              if(number[i] == digit){
                  number.erase(i,1);
                  break;
              }
          }
      }
      return number;
  }
};

第二题：必须拿起的最小连续卡牌数

思路：选择全部可行区间比较大小即可

这道题做的时候遇到的问题
- vector l,r 要给定指定大小
- map不能像数组那样进行初始化

AC 代码

class Solution {
public:
  int minimumCardPickup(vector<int>& a) {
      int n = a.size();  
      vector<int> mp(1000010, -1); //来判断是否已经存了这个数，初始化为-1
      vector<int> l(n + 1), r(n + 1);
      int cnt = 0;
      for(int i = 0;i < n;i ++ ){
          if(mp[a[i]] != -1){
              l[cnt] = mp[a[i]];
              r[cnt ++ ] = i;
          }
          mp[a[i]] = i;
      }
      int ans = 2e9;
      if(cnt == 0) return -1;
      for(int i = 0;i < cnt;i ++ ) ans = min(ans, r[i] - l[i] + 1);
      return ans;
  }
};

用unordered_map函数做的简洁代码

class Solution {
public:
  int minimumCardPickup(vector<int>& a) {
      int n = a.size();  
      unordered_map<int, int> mp;
      int res = 2e9;
      for(int i = 0;i < n;i ++ ){
          if(mp.count(a[i])){
              res = min(res, i - mp[a[i]] + 1);
          }
          mp[a[i]] = i;
      }
      return res == 2e9 ? -1 : res;
  }
};

第三题：含最多 K 个可整除元素的子数组

考试的思路： hash映射乱搞一通

class Solution {
public:

  pair<int, int> pai[100010];
  int countDistinct(vector<int>& nums, int k, int p) {

      const int MOD = 2e9 + 7;
      int n = nums.size();
      unordered_map<int, int> mp;
      int a = 0;
      for(int i = 0;i < n; i++ ){
          for(int j = i;j < n;j ++ ){
              int cnt = 0;
              for(int u = i;u <= j;u ++ ){
                  if(nums[u] % p == 0) cnt ++;
              }
              if(cnt <= k){
                pai[a ++ ] = {i, j};  
              }
          }
      }
      int ans = 0;
      for(int i = 0;i < a;i ++ ){
          int l = pai[i].first, r = pai[i].second;
          long long hash = 0;
          for(int j = l;j <= r;j ++ ){
              hash = (hash * 124215217 % MOD + nums[j] * 1233451 % MOD) % MOD;
          }
          hash = hash * (r - l + 1) % MOD;

          if(mp[hash] == 0){
              ans ++;
              mp[hash] = 1;
          }
      }
      return ans;
  }
};

正解：
暴力枚举 + 数组的序列化
- 注意点，将数组序列化，需要在每个添加的元素中添加一个字符标记
- 不然不同的两个子数组可能会看起来相同比如 1 21 和 12 1 就被认为只有一

class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        int n = nums.size();
        unordered_set<string> st;
        for(int i = 0;i < n;i ++){
            string s = "";
            int cnt = 0;
            for(int j = i;j < n;j ++ ){
                if(nums[j] % p == 0){
                    cnt ++;
                    if(cnt > k) break;
                }
                s.append(to_string(nums[j]));  
                s.push_back('#');  // 这里一定要用 '#' 来分开两个单独的数 比如 7 12 和 71 2
                st.insert(s);
            }
        }
        return st.size();
    }
};

294场周赛

第三题：表示一个折线图的最少线段数

思路：斜率如果连续相等就表示可以合成一条线段
被卡的点：精度问题用除法进行大整数的运算答案不够精确，所有一般除法问题都转换成乘法问题来解决

被卡的代码 ```cpp class Solution { public:

double findK(int x1,int y1,int x2,int y2){

  return (y2 - y1) * 1.0 / (x2 - x1);

}

int minimumLines(vector>& v) {

  if(v.size() == 1) return 0;
  sort(v.begin(),v.end());

  int ans = 0;
  for(int i = 2;i < v.size();i ++ ){
      if(abs(findK(v[i - 2][0],v[i - 2][1],v[i - 1][0], v[i - 1][1]) - findK(v[i - 1][0],v[i - 1][1], v[i][0], v[i][1])) > 1e-18){
          ans ++;
      }
  }
  return ans + 1;

} };


- 换成乘法的AC代码
```cpp
class Solution {
public:
    typedef long long LL;
    int minimumLines(vector<vector<int>>& v) {
        if(v.size() == 1) return 0;
        sort(v.begin(),v.end());

        int ans = 0;
        for(int i = 2;i < v.size();i ++ ){
            int x1 = v[i - 2][0], y1 = v[i - 2][1];
            int x2 = v[i - 1][0], y2 = v[i - 1][1];
            int x3 = v[i][0], y3 = v[i][1];
            if((LL)(y3 - y2) * (x2 - x1) != (LL)(y2 - y1) * (x3 - x2)) ans ++;
        }
        return ans + 1;
    }
};

第四题：巫师的总力量和

这是一个单调栈 + 前缀和问题
做的时候完全没思路
将某个子段的所有点看成是最弱的巫师，然后找这个巫师可以左右合法边界
把所有的结果相加既是答案
用单调栈的方式找到左右边界，注意左边取小于，右边就要取小于等于，不然会重复或者遗漏
- 至于为什么枚举所有点就能得到该数组的所有连续区域,因为任意举一个子数组，都能够被该数组中的最小点进行管辖
这里难在求某个包含 i 的区间中所有的连续子数组和的和
这里的x和y互不干涉，所有后序展开就很方便
还有一个易错点，如果使用了两次栈，记得把第一次的结果清空
AC 代码

第四题类似：子数组的最小值之和
这两道题的唯一区别在于以某个点为权值的管辖范围所要求的值不一样
前面要求求这个范围中所有包含最小点的子数组的和的和
这道题要求包含最小点的子数组一共有多少个

AC 代码

class Solution {
public:
  typedef long long LL;
  int sumSubarrayMins(vector<int>& arr) {
      const int MOD = 1e9 + 7;
      int n = arr.size();
      vector<LL> left(n, - 1), right(n, n);
      stack<int> st;
      for(int i = 0;i < n;i ++ ){
          while(!st.empty() && arr[st.top()] >= arr[i]){
              right[st.top()] = i;
              st.pop();
          }
          if(!st.empty()) left[i] = st.top();
          st.push(i);
      }
      LL ans = 0;
      for(int i = 0;i < n;i ++ ){
          LL tmp = arr[i] * ((i - left[i]) * (right[i] - i) % MOD) % MOD;
          ans = (ans + tmp) % MOD;
      }
      return ans;
  }
};

78场双周赛

第一题：找到一个数字的 K 美丽值

将数存到数组中，然后得到子序列的数进行判断，如果满足要求就将结果++

class Solution {
public:

  vector<int> v;
  int divisorSubstrings(int num, int k) {

      int a = num;
      int cnt = 0;
      while(a){
          v.push_back(a % 10);
          a /= 10;
      }

      reverse(v.begin(),v.end());  // 需要将数组逆序来遍历比较方便

      int res = 0;
      for(int i = 0;i < v.size();i ++ ){
          int ans = 0;
          for(int j = i;j < i + k && i + k - 1 < v.size();j ++ ){
              ans = 10 * ans + v[j];
          }
          if(i + k - 1 < v.size() && ans && num % ans == 0) res ++;
      }
      return res;
  }
};

第二题：分割数组的方案数（前缀和）

简单的一个前缀和问题

注意s[i] 代表的是前i个数的前缀和

class Solution {
public:
  int waysToSplitArray(vector<int>& a) {
      vector<long> s(a.size() + 1);
      for(int i = 1;i     <= a.size();i ++ ) s[i] = s[i - 1] + a[i - 1];
      int ans = 0;
      for(int i = 0;i < a.size() - 1;i ++ )
          if(s[i + 1] >= s[a.size()] - s[i + 1]) ans ++;
      return ans;
  }
};

第三题：毯子覆盖的最多白色砖块数（滑动窗口+贪心）

滑动窗口在滑动需要考虑的问题
- 什么条件下窗口会进行滑动
  - 直到处理到一个区间时，窗口不能够把它框住后，就需要将窗口进行滑动
- 怎么处理窗口中所要求的最值
  - 每一次处理一个区间都要进行一次更新操作
  - 用一个sum来动态记录完全在窗口中的数大小
    - 如果某个区间没有完全包含在窗口中，不对sum进行更新，不然后序操作会重复
  - 用一个ans来动态更新答案的最值

本题学到的知识点：

vector> 可以用sort进行排序，默认按每一维的第一个元素先从小到大排序，如果一样，按照后面的从小到大排序

vector的初始化 vector> v(n, vector (m, 0)) 第一个参数传入初始化个数，第二个传入具体初始化的值

class Solution {
public:

int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {

   sort(tiles.begin(),tiles.end()); 
   int l = 0,r = 0,n = tiles.size(),mx = 0,sum = 0,ans = 0;
   while(l <= r && r < n){ // 这里需要判断 l <= r, 不然会越界
       int leftBound = tiles[l][0],rightBound = leftBound + carpetLen - 1;
       if(rightBound >= tiles[r][1]){
           sum += tiles[r][1] - tiles[r][0] + 1;
           ans = max(ans, sum);
           r ++;
       }
       else{
           if(rightBound >= tiles[r][0]){
               // 这里更新最值，不对sum进行更新，因为后序在更新的时候会把这整个区间再加一遍，
               // 会重复添加
               ans = max(ans, sum + rightBound - tiles[r][0] + 1);
           }
           sum -= tiles[l][1] - tiles[l][0] + 1;
           l ++;
       }
   }
   return ans;
}
};

293场周赛

第一题：移除字母异位词后的结果数组

思路：本题卡住的点是不知道该怎么比较相邻两个字符串是否为异构形式，后来用了将每个字符串的每个字符依次相乘的方法然后比较是否相等，哈希思想

判断异构字符串模板：
以下为AC代码：

class Solution {
public:

    // 判断异构的方法
     bool is_same(string s1,string s2){
        int cnt[26] = {0};
        if(s1.size() != s2.size()) return false;
        for(int i = 0;i < s1.size();i ++ ){
            cnt[s1[i] - 'a'] ++;
            cnt[s2[i] - 'a'] --;
        }
        for(int i = 0;i < 26;i ++){
            if(cnt[i] != 0) return false;
        }
        return true;
    }

    vector<string> removeAnagrams(vector<string>& words) {
        vector<string> v;
        v.push_back(words[0]);
        for(int i = 1;i < words.size();i ++){
            if(!is_same(words[i - 1],words[i])){
                v.push_back(words[i]);
            }
        }
        return v;
    }
};

或者直接对字符串排序后再比较

class Solution {
public:

  vector<string> removeAnagrams(vector<string>& words) {
      vector<string> v;
      v.push_back(words[0]);
      for(int i = 1;i < words.size();i ++){
          string s1 = words[i - 1];
          string s2 = words[i];
          string ans = words[i];
          sort(s1.begin(),s1.end());
          sort(s2.begin(),s2.end());
          if(s1 != s2){
              v.push_back(ans);
          }
      }
      return v;
  }
};

第二题（排序就行）不含特殊楼层的最大连续楼层数

第三题：按位与结果大于零的最长组合

思路：最开始毫无头绪，甚至老去想动态规划。。。

正解：把每个数都看成二进制形式，既然要找到多个数相与的最大个数，所有只要找到1最多的那个位次，就是这
些数相与的最终答案

附上AC代码 ```cpp class Solution { public:

const int N = 100010; int cnt[32]; int largestCombination(vector& v) {

  for(int i = 0;i < v.size();i ++ ){
      for(int j = 0;j < 32;j ++ ){
          if(v[i] >> j & 1){ 
          cnt[j] ++;
          }
      }
  }
  int mx = -2e9;
  for(int i = 0;i < 32;i ++){
      mx = max(mx, cnt[i]);  // 找1最多的那个位次
  }
  return mx;

}

}; ```

291场周赛

第一题：移除指定数字得到的最大结果

第二题：必须拿起的最小连续卡牌数

第三题：含最多 K 个可整除元素的子数组

294场周赛

第三题：表示一个折线图的最少线段数

第四题：巫师的总力量和

第四题类似：子数组的最小值之和

78场双周赛

第一题：找到一个数字的 K 美丽值

第二题：分割数组的方案数（前缀和）

第三题：毯子覆盖的最多白色砖块数 （滑动窗口+贪心）

293场周赛

第一题：移除字母异位词后的结果数组

第二题（排序就行）不含特殊楼层的最大连续楼层数

第三题：按位与结果大于零的最长组合

第三题：毯子覆盖的最多白色砖块数（滑动窗口+贪心）