前言
这是 2021-06-12 的一场双周赛，这次周赛的前三道题相对简单，第四题如果没有做过表达式处理相关的题目，是比较难想到正确做法的。其中，比赛涉及到的知识点有模拟、枚举、前缀和、表达式求值和动态规划。
第 54 场双周赛链接：https://leetcode-cn.com/contest/biweekly-contest-54/
1. 检查是否区域内所有整数都被覆盖
题目链接：https://leetcode.cn/problems/check-if-all-the-integers-in-a-range-are-covered/
题意
给出 n n n 个小区间 [ l i , r i ] [l_i, r_i] [li,ri]，表示各个区间中的整数都被覆盖。
然后给出询问区间 [ l , r ] [l,r] [l,r]，让你判断该区间内所有整数是否都被覆盖了。
数据保证：
1 ≤ n ≤ 50 1 \leq n \leq 50 1≤n≤50
1 ≤ l i ≤ r i ≤ 50 1 \leq l_i \leq r_i \leq 50 1≤li≤ri≤50
1 ≤ l ≤ r ≤ 50 1 \leq l \leq r \leq 50 1≤l≤r≤50
题解
因为数据范围比较小，所有可以考虑用暴力法解决。我们对各区间中的整数进行标记，然后遍历标记数组区间 [ l , r ] [l,r] [l,r] 中的整数，如果有未被标记的就返回 false ，否则返回 true。
时间复杂度是 O ( ∑ i = 0 n ( r i − l i + 1 ) ) O(\displaystyle \sum_{i=0}^{n}(r_i - l_i + 1)) O(i=0∑n(ri−li+1))。
class Solution {
public:
bool isCovered(vector<vector<int>>& ranges, int left, int right) {
vector<bool> isDiscovers(51, false);
for (auto range : ranges) {
for (int i = range[0]; i <= range[1]; i++) {
isDiscovers[i] = true;
}
}
for (int i = left; i <= right; i++) {
if (!isDiscovers[i]) {
return false;
}
}
return true;
}
};
2. 找到需要补充粉笔的学生编号
题目链接：https://leetcode.cn/problems/find-the-student-that-will-replace-the-chalk/
题意
班级有 n n n 个学生，从 0 → n − 1 0 \rightarrow n-1 0→n−1 编号。
老师有 k k k 根粉笔，且会按 0 → n − 1 0 \rightarrow n-1 0→n−1 的顺序对学生进行提问，学生回答问题需要粉笔，编号为 i i i 的学生回答问题消耗的粉笔数为 C i C_i Ci。
老师会循环进行提问，当 k < C i k < C_i k<Ci 时，老师需要补充粉笔，返回此时的学生编号，即 i i i 。
数据保证：
0 ≤ n , C i ≤ 1 0 5 0 \leq n,C_i \leq 10_5 0≤n,Ci≤105
0 ≤ k ≤ 1 0 9 0 \leq k \leq 10_9 0≤k≤109
题解
我们可以通过模拟来解决这道题，但是当 k k k 比较大，而 C i C_i Ci 都比较小的时候，就会时间超限。
我们在模拟的时候，其实不难发现，只有在最后一轮提问的时候，才会决定最后答案。于是我们可以通过 k % ∑ i = 0 n C i k \% \sum_{i=0}^{n}{C_i} k%∑i=0nCi，让提问直接进入最后一轮，然后再模拟去寻找老师需要补充粉笔时学生的编号。
using ll = long long;
class Solution {
public:
int chalkReplacer(vector<int>& chalk, int k) {
int n = chalk.size();
ll sum = 0;
for (auto num : chalk) {
sum += num;
}
k = k % sum;
for (int i = 0; i < n; i++) {
if (k < chalk[i]) {
return i;
} else {
k -= chalk[i];
}
}
return -1;
}
};
3. 最大的幻方
题目链接：https://leetcode.cn/problems/largest-magic-square/
题意
一个 k × k k \times k k×k 的幻方指的是一个 k × k k \times k k×k 填满整数的方阵，且 每一行、每一列以及两条对角线的和 全部相等。
给你一个 n × m n \times m n×m 的整数矩阵 g r i d grid grid，要求返回矩阵中最大幻方的边长 k k k。
数据保证：
1 ≤ n , m ≤ 50 1 \leq n,m \leq 50 1≤n,m≤50
1 ≤ g r i d i , j ≤ 1 0 6 1 \leq grid_{i,j} \leq 10^6 1≤gridi,j≤106
题解
从大到小枚举可能组成幻方的所有边长和左上顶点的坐标，由此枚举出所有可能成为幻方的方阵，然后计算该方阵每一行、每一列以及两条对角线的和，判断它们是否都相等。如果能找到幻方就立即返回，否则到最后返回 1 1 1（每个方格都是一个 1 × 1 1 \times 1 1×1 的幻方）。
因为直接暴力计算该方阵每一行、每一列以及两条对角线的和会非常耗时，这里我们可以采用前缀和的方式来进行优化，这里我维护了行、列、两条对角线方向等四个前缀和，需要用到的时候按照坐标进行差分计算即可。
using ll = long long;
class Solution {
public:
int largestMagicSquare(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<ll>> sum1(n + 1, vector<ll>(m + 1, 0)); // 每行前缀和
vector<vector<ll>> sum2(sum1); // 每列前缀和
vector<vector<ll>> sum3(sum1); // 左上到右下前缀和
vector<vector<ll>> sum4(n + 1, vector<ll>(m + 2, 0)); // 右上到左下前缀和
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum1[i][j] = sum1[i][j - 1] + grid[i - 1][j - 1];
sum2[i][j] = sum2[i - 1][j] + grid[i - 1][j - 1];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum3[i][j] = sum3[i - 1][j - 1] + grid[i - 1][j - 1];
sum4[i][j] = sum4[i - 1][j + 1] + grid[i - 1][j - 1];
}
}
for (int k = min(n, m); k >= 2; k--) {
for (int i = 0; i <= n - k; i++) {
for (int j = 0; j <= m - k; j++) {
int x1 = i, y1 = j, x2 = i + k - 1, y2 = j + k - 1;
vector<ll> lens;
// 计算各行的和
for (int a = x1; a <= x2; a++) {
lens.push_back(sum1[a + 1][y2 + 1] - sum1[a + 1][y1]);
}
// 计算各列的和
for (int a = y1; a <= y2; a++) {
lens.push_back(sum2[x2 + 1][a + 1] - sum2[x1][a + 1]);
}
// 计算两条对角线的和
lens.push_back(sum3[x2 + 1][y2 + 1] - sum3[x1][y1]);
lens.push_back(sum4[x2 + 1][y1 + 1] - sum4[x1][y2 + 2]);
int l;
for (l = 1; l < lens.size(); l++) {
if (lens[l] != lens[l - 1]) {
break;
}
}
if (l == lens.size()) {
return k;
}
}
}
}
return 1;
}
};
4. 反转表达式值的最少操作次数
题目链接：https://leetcode.cn/problems/minimum-cost-to-change-the-final-value-of-expression/
题意
给你一个有效的布尔表达式字符串 s s s，这个字符串包含字符 '1'，'0'，'&'，'|'，'(' 和 ')' 。
你可以对表达式 s s s 进行如下操作：
- 将一个
'1'变成一个'0'。 - 将一个
'0'变成一个'1'。 - 将一个
'&'变成一个'|'。 - 将一个
'|'变成一个'&'。
请你返回将表达 s s s 的结果反转（ 0 → 1 o r 1 → 0 0 \rightarrow 1 \ or \ 1\rightarrow0 0→1 or 1→0），所需要的最小操作次数。
数据保证：
1 ≤ s . l e n g t h ≤ 1 0 5 1 \leq s.length \leq 10^5 1≤s.length≤105
题解
这道题是表达式求值和动态规划的结合，通过在表达式计算的过程中进行转态转移，最后得到最优解。
首先，我们通常以双栈（操作数栈和操作符栈）的形式对表达式求值问题进行模拟求解。在这里，操作数栈中存储的元素要更换为该操作数所对应的一个二元状态 ( x , y ) (x, y) (x,y)。其中， x x x 表示将对应表达式变为 1 1 1 所需要的最小操作次数， y y y 表示将对应表达式变为 0 0 0 所需要的最小操作次数。
于是，在初始化时，操作数 1 1 1 对应的状态为 ( 0 , 1 ) (0,1) (0,1)，操作数 0 0 0 对应的状态为 ( 1 , 0 ) (1,0) (1,0)。
然后，我们根据运算符优先级确定计算顺序。因为 & 和 | 的优先级相同，所以我们只需要从左往右进行计算。考虑到有括号的存在，我们可以把每个 ( 之前的操作数先合并成一个，当遇到 ) 时再让 ( 出栈，之后再合并由出栈的 ( 所分隔的操作数。
在计算的过程中的两个状态 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1),(x_2,y_2) (x1,y1),(x2,y2) 进行状态转移时，我们可以根据操作符分类讨论：
当操作符为 & 时，分下面两种情况讨论可得转移方程。
- 要想得到 1 1 1，我们需要将两个操作数都为 1 1 1，代价为 x 1 + x 2 x_1+x_2 x1+x2；或者操作符变为
|，然后将其中一个操作数变为 1 1 1，此时代价为 m i n ( x 1 , x 2 ) + 1 min(x_1,x_2)+1 min(x1,x2)+1。 - 要想得到 0 0 0, 我们只需要将其中一个操作数变为 0 0 0，代价为 m i n ( y 1 , y 2 ) min(y_1,y_2) min(y1,y2)。
{ x = m i n ( x 1 + x 2 , m i n ( x 1 , x 2 ) + 1 ) y = m i n ( y 1 , y 2 ) \begin{cases} x = min(x_1+x_2,min(x_1,x_2)+1) \\ y = min(y1, y2) \end{cases} {x=min(x1+x2,min(x1,x2)+1)y=min(y1,y2)
当操作符为 | 时，分下面两种情况讨论可得转移方程。
- 要想得到 1 1 1，我们只需要将其中一个操作数变为 1 1 1，代价为 m i n ( x 1 , x 2 ) min(x_1,x_2) min(x1,x2)。
- 要想得到 0 0 0, 我们需要将两个操作数都为 0 0 0，代价为 y 1 + y 2 y_1+y_2 y1+y2；或者操作符变为
&，然后将其中一个操作数变为 0 0 0，此时代价为 m i n ( y 1 , y 2 ) + 1 min(y_1,y_2)+1 min(y1,y2)+1。
{ x = m i n ( x 1 , x 2 ) y = m i n ( y 1 + y 2 , m i n ( y 1 , y 2 ) + 1 ) \begin{cases} x = min(x_1,x_2) \\ y = min(y_1+y_2,min(y_1,y_2)+1) \end{cases} {x=min(x1,x2)y=min(y1+y2,min(y1,y2)+1)
在完成表达式计算之后，操作数栈中最后一个元素就是最终得到的状态 ( x , y ) (x, y) (x,y) 。其中一个值为 0 0 0，表示表达式原本的计算结果，另个值为非 0 0 0，即我们想要的答案，所以最终的答案为 m a x ( x , y ) max(x,y) max(x,y)。
using pii = pair<int, int>;
class Solution {
public:
int minOperationsToFlip(string expression) {
vector<pii> num_stk; // 数字栈
vector<char> op_stk; // 操作数栈
for (auto ch : expression) {
if (ch == '0' || ch == '1' || ch == ')') {
if (ch == '0') {
num_stk.push_back({1, 0});
} else if (ch == '1') {
num_stk.push_back({0, 1});
} else {
op_stk.pop_back(); // 弹出左括号
}
// 在计算过程中进行状态转移
if (num_stk.size() >= 2 && op_stk.back() != '(') {
char op = op_stk.back();
op_stk.pop_back();
auto [x1, y1] = num_stk.back();
num_stk.pop_back();
auto [x2, y2] = num_stk.back();
num_stk.pop_back();
if (op == '&') {
num_stk.push_back({min(x1 + x2, min(x1, x2) + 1), min(y1, y2)});
} else if (op == '|') {
num_stk.push_back({min(x1, x2), min(y1 + y2, min(y1, y2) + 1)});
}
}
} else {
op_stk.push_back(ch);
}
}
return max(num_stk[0].first, num_stk[0].second);
}
};
参考链接
- https://leetcode-cn.com/problems/minimum-cost-to-change-the-final-value-of-expression/solution/fan-zhuan-biao-da-shi-zhi-de-zui-shao-ca-s9ln/
- https://leetcode-cn.com/problems/minimum-cost-to-change-the-final-value-of-expression/solution/zhan-dong-tai-gui-hua-by-lucifer1004-7bsn/
这是一篇上古题解了，当时觉得到没有时效性了，就一直没有发。今年偶然翻到，发现压轴题有一定的学习价值，决定分享一下，建议看到的同学可以去写一下压轴题。