A

题目

6171. 和相等的子数组 - 力扣（LeetCode） (opens new window)

思路

1. 枚举

枚举所有情况判断即可

代码

class Solution {
public:
    bool findSubarrays(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n - 1; i ++) {
            for (int j = 0; j < n - 1; j ++) {
                if (i == j) continue;
                if (nums[i] + nums[i + 1] == nums[j] + nums[j + 1]) return true;
            }
        }
        return false;
    }
};

// Make sure to add code blocks to your code group

B

题目

数学证明 - 严格回文的数字 - 力扣（LeetCode） (opens new window)

思路

1. 数学

对于 ，容易发现 在 进制下，值为 ，不满足回文；

对于 ， 在 进制下，值为 ，也不满足回文。

综上，一定不存在严格回文的数字。

代码

class Solution {
public:
  bool isStrictlyPalindromic(int n) {
      return false;
  }
};

// Make sure to add code blocks to your code group

C

题目

6173. 被列覆盖的最多行数 - 力扣（LeetCode） (opens new window)

思路

1. 二进制枚举

看一眼数据，，因此直接暴力即可。

二进制枚举去枚举所有情况，在所有可行状态中取可覆盖行数的最大值即可。

代码

class Solution {
public:
  int maximumRows(vector<vector<int>>& mat, int cols) {
      int n = mat.size(), m = mat[0].size();

      auto get = [&](int x) { // 求 x 中有多少个 1
          int cnt = 0;
          for (int z = 0; z < 12; z ++) {
              if (x & (1 << z)) cnt ++;
          }
          return cnt;
      };

      auto check = [&](int o) { // 判断 o 有多少个可覆盖行
          auto t = mat; // 备份矩阵
          for (int z = 0; z < 12; z ++) { //将所有带 1 的列清空
              if (o & (1 << z)) {
                  for (int i = 0; i < n; i ++) {
                      t[i][z] = 0;
                  }
              }
          };
          int cnt = 0; // 统计可覆盖行数
          for (int i = 0; i < n; i ++) {
              bool ok = true;
              for (int j = 0; j < m; j ++) { 
                  if (t[i][j]) { // 如果该行有 1，则该行未被覆盖。
                      ok = false;
                      break;
                  }
              }
              cnt += ok;
          }
          return cnt;
      };
      int res = 0;
      for (int o = 0; o < (1 << m); o ++) {
          int cnt = 0;
          if (get(o) > cols) continue; // 判断是否可行
          res = std::max(res, check(o));
      }
      return res;
  }
};

// Make sure to add code blocks to your code group

D

题目

6143. 预算内的最多机器人数目 - 力扣（LeetCode） (opens new window)

思路

题目翻译有点问题，题干中的 连续 指的是下标连续。

前置题：239. 滑动窗口最大值 - 力扣（LeetCode） (opens new window)

1. 二分 + 单调队列

对 进行二分，判断是否成立的部分和滑动窗口的模板题基本一样，额外维护 个数的 和即可。

代码

class Solution {
public:
  int q[50005];
  using ll = long long;
  int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
      int n = chargeTimes.size();
      int L = 0, R = n;

      auto check = [&](int k) {
          int hh = 0, tt = -1;
          ll sum = 0;
          for (int i = 0; i < n; i ++) {
              if (hh <= tt && q[hh] <= i - k) hh ++;
              while (hh <= tt && chargeTimes[i] >= chargeTimes[q[tt]]) tt --;
              q[++ tt] = i;
              sum += 1ll * k * runningCosts[i];
              if (i >= k) sum -= 1ll * k * runningCosts[i - k];
              if (i >= k - 1 && sum + chargeTimes[q[hh]] <= budget) return true; 
          }
          return false;
      };

      while (L < R) {
          int m = (L + R + 1) >> 1;
          if (check(m)) {
              L = m;
          } else {
              R = m - 1;
          }
      }
      return L;
  }
};

// Make sure to add code blocks to your code group

2. 双指针 + 单调队列

本题其实并不需要二分，我们用右指针进行遍历，并用单调队列维护区间最值，同时对每一个右指针，我们通过移动左指针，找到最长的满足条件的区间，并更新答案。

代码

class Solution {
public:
  using ll = long long;
  int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
      int n = chargeTimes.size();
      std::deque<int> DQ;
      ll sum = 0;
      int res = 0;
      for (int i = 0, j = 0; j < n; j ++) {
          sum += runningCosts[j];
          while (!DQ.empty() && chargeTimes[j] >= chargeTimes[DQ.back()]) DQ.pop_back();
          DQ.push_back(j);
          while (!DQ.empty() && sum * (j - i + 1) + chargeTimes[DQ.front()] > budget) {
              if (DQ.front() == i) DQ.pop_front();
              sum -= runningCosts[i ++];
          }  
          res = std::max(res, j - i + 1);
      }   
      return res;
  }
};

// Make sure to add code blocks to your code group