前言
这是 2021-06-06 的一场 LeetCode 周赛，本场周赛的题目相较而以往而言比较简单，基本上想到点上就可以做出来，主要涉及到矩阵的旋转、贪心、滑动窗口、前缀和、二分查找等知识点。
第 244 场周赛链接：https://leetcode-cn.com/contest/weekly-contest-244/
1. 判断矩阵经轮转后是否一致
题目链接：https://leetcode.cn/problems/determine-whether-matrix-can-be-obtained-by-rotation/
题意
给你两个大小为 n n n x n n n 的二进制矩阵 m a t mat mat 和 t a r g e t target target，判断能否通过对 m a t mat mat 进行若干次 90 度顺时针轮转操作，使得它与 t a r g e t target target 内容一致。
数据保证：
1 ≤ n ≤ 10 1 \leq n \leq 10 1≤n≤10
题解
模拟题，我们可以将实现两个函数，一个用于判断两个矩阵是否相等，另一个用于将矩阵进行 90 度顺时针轮转操作（ 即令 r e t j , n − i − 1 = m a t i , j ret_{j,n - i - 1} = mat_{i, j} retj,n−i−1=mati,j ）。
如果我们能过通过四次以内的轮转操作，将 m a t mat mat 的内容变得与 t a r g e t target target 一致，就返回 true，否则返回 false。
class Solution {
private:
bool isEqual(vector<vector<int>>& mat, vector<vector<int>>& target) {
int n = mat.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] != target[i][j]) {
return false;
}
}
}
return true;
}
vector<vector<int>> rotate(vector<vector<int>>& mat) {
int n = mat.size();
vector<vector<int>> ret(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ret[j][n - i - 1] = mat[i][j];
}
}
return ret;
}
public:
bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
for (int i = 0; i < 3; i++) {
if (isEqual(mat, target)) {
return true;
}
mat = rotate(mat);
}
return isEqual(mat, target);
}
};
时间复杂度： O ( n 2 ) O(n^2) O(n2)
空间复杂度： O ( n 2 ) O(n^2) O(n2)
2. 使数组元素相等的减少操作次数
题目链接：https://leetcode.cn/problems/reduction-operations-to-make-the-array-elements-equal/
题意
给你一个有 n n n 个元素的整数数组 A A A ，你的目标是令 A A A 中的所有元素相等，完成一次减少操作需要遵照下面的几个步骤：
- 找出 A A A 中的最大值，记录其下标 i i i。如果有多个元素都是最大值，则取下标最小的 。
- 找出 A A A 中的次大值，将其记为 v a l u e value value ，要求其严格小于 A i A_i Ai。
- 令 A i = v a l u e A_i =value Ai=value 。
返回使 A A A 中的所有元素相等的最少操作次数。
数据保证：
1 ≤ n ≤ 5 ⋅ 1 0 4 1 \leq n \leq 5 \cdot 10^4 1≤n≤5⋅104
1 ≤ A i ≤ 5 ⋅ 1 0 4 1 \leq A_i \leq 5 \cdot 10^4 1≤Ai≤5⋅104
题解
经过对样例的模拟可以发现，数组中的元素都是逐渐减少的，要想令 A A A 中的所有元素相等，则从 A A A 中的最大元素开始操作，让所有的元素最终都变为 m i n ( A ) min(A) min(A)。
对于一个元素 A i → m i n ( A ) A_i \rightarrow min(A) Ai→min(A)， 它需要不断变为次大值，最终才会变为 m i n ( A ) min(A) min(A)，所需要的操作次数等于 A A A 中比 A i A_i Ai 小的数字个数（即重复不计）。
这里先对 A A A 排序，然后通过维护一个自底向上单调递增且不包含相同元素的栈来计算操作个数。
class Solution {
public:
int reductionOperations(vector<int>& nums) {
stack<int> s;
sort(nums.begin(), nums.end());
for (auto num : nums) {
if (s.empty() || s.top() != num) {
s.push(num);
}
}
int ans = 0, n = nums.size();
for (int i = n - 1; i >= 0; i--) {
if (nums[i] != s.top()) {
s.pop();
}
ans += s.size() - 1;
}
return ans;
}
};
时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度： O ( n ) O(n) O(n)
3. 使二进制字符串字符交替的最少反转次数
题目链接：https://leetcode.cn/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/
题意
给你一个 二进制 字符串 s s s 。你可以按任意顺序执行以下两种操作任意次：
- 类型 1 ：删除 s s s 的第一个字符并将它 添加 到 s s s 结尾。
- 类型 2 ：选择 s s s 中任意一个字符并将该字符 反转 ，即 0 ⇒ 1 , 1 ⇒ 0 0 \Rightarrow 1, \ 1 \Rightarrow 0 0⇒1, 1⇒0。
请你返回使 s s s 变成 交替 字符串的前提下，类型 2 的 最少 操作次数 。
数据保证：
1 ≤ s . l e n g t h ≤ 1 0 5 1 \leq s.length \leq 10^5 1≤s.length≤105
题解
字符串 s s s 最终会变为 1010... 1010... 1010... 或者 0101... 0101... 0101...，这两种形式中的一种。
假设没有操作 1 的话，我们只需要利用操作 2 将 s s s 变成这两种最终形式，然后计算所需的操作 2 的次数 c n t 1 cnt_1 cnt1 和 c n t 2 cnt_2 cnt2，最终取 m i n ( c n t 1 , c n t 2 ) min(cnt_1, cnt_2) min(cnt1,cnt2)。
由于这两种最终形式对应位置都是互不相同的，所以 c n t 2 = s . l e n g t h − c n t 1 cnt_2 = s.length - cnt_1 cnt2=s.length−cnt1，因此我们只需要计算 c n t 1 cnt_1 cnt1，最终取 m i n ( c n t 1 , s . l e n g t h − c n t 1 ) min(cnt_1, s.length - cnt_1) min(cnt1,s.length−cnt1)。
为了处理操作 1 对结果的影响，我们使用滑动窗口算法。令 T = s + s T = s+s T=s+s，然后用大小为 s . l e n g t h s.length s.length 的窗口进行扫描，如下图所示：
(上图取自 LeetCode @Ikaruga 题解的图片)
在扫描的过程中，不断更新 c n t 1 cnt_1 cnt1 的值，同时通过一个结果变量 a n s ans ans 维护 m i n ( c n t 1 , s . l e n g t h − c n t 1 ) min(cnt_1, s.length - cnt_1) min(cnt1,s.length−cnt1) 的值。
class Solution {
public:
int minFlips(string s) {
int n = s.length();
int cnt = 0;
string t = "01";
for (int i = 0; i < n; i++) {
if (s[i] != t[i % 2]) {
cnt++;
}
}
// 滑动窗口扫描的过程
int ans = min(cnt, n - cnt);
for (int i = 0; i < n; i++) {
cnt += s[i] != t[(n + i) % 2];
cnt -= s[i] != t[i % 2];
ans = min(ans, min(cnt, n - cnt));
}
return ans;
}
};
时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( 1 ) O(1) O(1)
4. 装包裹的最小浪费空间
题目链接：https://leetcode.cn/problems/minimum-space-wasted-from-packaging/
题意
给你 n n n 个包裹，它们的尺寸分别为 P i P_i Pi。
有 m 个供应商，每个供销商提供 B i B_i Bi 种箱子，箱子的尺寸为 B i j B_{ij} Bij，每种尺寸的箱子都有无数个。
设包裹的大小为 p p p，箱子的大小为 b b b。当 p ≤ b p \leq b p≤b 时，包裹就可以被放进这个箱子中；这时，浪费的空间就表示为 b − p b - p b−p。你需要把包裹都装在箱子里，每个箱子装一个包裹。
你需要选择一个使得 总浪费空间最小 供应商，返回最小总浪费空间。如果没有供应商可以满足，则返回 -1 。答案需要对 1 0 9 + 7 10^9 + 7 109+7 取余。
数据保证：
1 ≤ n , m , P i , B i j ≤ 1 0 5 1 \leq n, m,P_i, B_{ij} \leq 10^5 1≤n,m,Pi,Bij≤105
∑ i = 0 m B i ≤ 1 0 5 \displaystyle \sum^{m}_{i = 0}{B_i} \leq 10^5 i=0∑mBi≤105
题解
我们可以计算出各个供应商提供箱子的总浪费空间，然后取最小值。
详细思路是，我们先按供应商从 0 → m 0 \rightarrow m 0→m 进行枚举。根据数据范围 ∑ i = 0 m B i ≤ 1 0 5 \displaystyle \sum^{m}_{i = 0}{B_i} \leq 10^5 i=0∑mBi≤105，之后枚举的就只能是相应供应商的提供的箱子尺寸，然后再到 P P P 中寻找所有能放进该箱子中的包裹，于是就可以求出使用该箱子所浪费的空间为 ：
( R − L ) ⋅ B i j − ∑ k = L R P k (R-L) \cdot B_{ij} - \displaystyle \sum^{R}_{k=L}{P_k} (R−L)⋅Bij−k=L∑RPk
注意到，我们要尽可能使得浪费的空间小，所以我们要尽可能用较小的箱子，我们需要对所有的 B i B_{i} Bi 进行排序。
为了提高 寻找能放进箱子的包裹 的效率，我们先对 P P P 进行排序，然后利用二分查找确定右边界 R R R，以上次的右边界结果作为左边界 L L L。
因为 ∑ j = 0 B i ∑ k = L j R j P k = ∑ j = 0 n P i \displaystyle \sum^{B_i}_{j=0} \sum^{R_j}_{k=L_j}{P_k} = \sum^{n}_{j=0}{P_i} j=0∑Bik=Lj∑RjPk=j=0∑nPi，所以我们只要先计算出最小的所用箱子尺寸总和 S u m Sum Sum，最后再减去所有包裹的尺寸总和，就可以得到最后的结果。
const int MOD = 1e9 + 7;
using ll = long long;
class Solution {
public:
int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {
ll ans = LONG_MAX;
int m = boxes.size();
sort(packages.begin(), packages.end());
for (int i = 0; i < m; i++) {
sort(boxes[i].begin(), boxes[i].end());
if (boxes[i].back() < packages.back()) {
continue;
}
int last = 0;
ll sum = 0;
for (auto box : boxes[i]) {
int pos = upper_bound(packages.begin(), packages.end(), box) - packages.begin();
sum += static_cast<ll>(pos - last) * box;
last = pos;
}
ans = min(ans, sum);
}
if (ans == LONG_MAX) {
return -1;
}
for (auto package : packages) {
ans -= package;
}
return ans % MOD;
}
};
这是很久之前写的一篇题解了，当时考虑到没有时效性了，就一直没有发。今年偶然翻到，发现 3、4 题还是有点意思的，决定分享一下，建议看到的同学可以去写一下后面两题。