4. 1738.找出第K大的异或坐标值(中等)
1738. 找出第 K 大的异或坐标值 - 力扣（LeetCode）
思想
1.给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。
矩阵中坐标 (a, b) 的 目标值 可以通过对所有元素 matrix[i][j] 执行异或运算得到，其中 i 和 j 满足 0 <= i <= a < m 且 0 <= j <= b < n（下标从 0 开始计数）。
请你找出 matrix 的所有坐标中第 k 大的目标值（k 的值从 1 开始计数）。
2.异或前缀和,s[i+1][j]^s[i][j+1]会把左上角异或没，所以还要异或一个s[i][j]
代码
class Solution {
public:
typedef long long ll;
int kthLargestValue(vector<vector<int>>& matrix, int k) {
int n = matrix.size(), m = matrix[0].size();
vector<vector<ll>> s(n + 1, vector<ll>(m + 1, 0));
vector<int> res;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
s[i + 1][j + 1] =
s[i + 1][j] ^ s[i][j + 1] ^ s[i][j] ^ matrix[i][j];
res.emplace_back(s[i + 1][j + 1]);
}
}
sort(res.begin(), res.end(), greater<int>());
return res[k - 1];
}
};
列前缀和
class Solution {
public:
typedef long long ll;
int kthLargestValue(vector<vector<int>>& matrix, int k) {
int n = matrix.size(), m = matrix[0].size();
vector<ll> s(m, 0);
vector<int> res;
for (int i = 0; i < n; ++i) {
int sum = 0;
for (int j = 0; j < m; ++j) {
s[j] ^= matrix[i][j];
sum ^= s[j];
res.emplace_back(sum);
}
}
sort(res.begin(), res.end(), greater<int>());
return res[k - 1];
}
};
5. 3212.统计X和Y频数相等的子矩阵数量(中等)
3212. 统计 X 和 Y 频数相等的子矩阵数量 - 力扣（LeetCode）
思想
1.给你一个二维字符矩阵 grid，其中 grid[i][j] 可能是 'X'、'Y' 或 '.'，返回满足以下条件的子矩阵数量：
- 包含
grid[0][0] 'X'和'Y'的频数相等。- 至少包含一个
'X'。
2.固定左上角，可以只维护列前缀和。此题维护X和Y两个即可
代码
class Solution {
public:
typedef long long ll;
int numberOfSubmatrices(vector<vector<char>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<ll> sX(m, 0);
vector<ll> sY(m, 0);
int res = 0;
for (int i = 0; i < n; ++i) {
int sumX = 0, sumY = 0;
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 'X')
++sX[j];
else if (grid[i][j] == 'Y')
++sY[j];
sumX += sX[j];
sumY += sY[j];
if (sumX > 0 && sumX == sumY)
++res;
}
}
return res;
}
};
6. 1292.元素和小于等于阈值的正方形的最大边长(中等)
1292. 元素和小于等于阈值的正方形的最大边长 - 力扣（LeetCode）
思想
1.给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。
请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0 。
2.此题和[[每天坚持/leetcode/前缀和#3. 1895.最大的幻方(中等,学习枚举细节处理)|最大的幻方]]不一样，本题具有单调性，可以二分查找
代码
class Solution {
public:
typedef long long ll;
vector<vector<ll>> s;
int n, m;
bool check(int mid, vector<vector<int>>& mat, int threshold) {
for (int i = 0; i + mid - 1 < n; ++i) {
for (int j = 0; j + mid - 1 < m; ++j) {
if (s[i + mid][j + mid] - s[i][j + mid] - s[i + mid][j] +
s[i][j] <=
threshold)
return true;
}
}
return false;
}
int maxSideLength(vector<vector<int>>& mat, int threshold) {
n = mat.size();
m = mat[0].size();
s.resize(n + 1, vector<ll>(m + 1, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
s[i + 1][j + 1] =
s[i][j + 1] + s[i + 1][j] - s[i][j] + mat[i][j];
}
}
int left = 0, right = min(n, m), res = 0;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (check(mid, mat, threshold)) {
left = mid + 1;
res = mid;
} else
right = mid - 1;
}
return res;
}
};
一维差分(扫描线)
差分与前缀和的关系，类似导数与积分的关系。
数组 a 的差分的前缀和就是数组 a。
1.套路
原理讲解
![[一维差分.png]]
![[一维差分理论.png]]
class Solution {
public:
int numberOfPoints(vector<vector<int>>& nums) {
int n = nums.size();
int max_end = INT_MIN;
for (auto& num : nums)
max_end = max(max_end, num[1]);
vector<int> d(max_end + 2); // 下面有max_end+1
for (auto& num : nums) {
int start = num[0], end = num[1];
// [start,end]+1
++d[start];
--d[end + 1];
}
int res = 0, s = 0;
for (int i = 0; i < max_end + 2; ++i) { // 差分数组长度max_end+2
s += d[i];
if (s > 0)
++res;
}
return res;
}
};
2,题目描述
1.给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i，nums[i] = [starti, endi] ，其中 starti 是第 i 辆车的起点，endi 是第 i 辆车的终点。
返回数轴上被车 任意部分 覆盖的整数点的数目(答案)。
2.给你一个二维整数数组 ranges 和两个整数 left 和 right 。每个 ranges[i] = [starti, endi] 表示一个从 starti 到 endi 的 闭区间 。
如果闭区间 [left, right] 内每个整数都被 ranges 中 至少一个 区间覆盖，那么请你返回 true ，否则返回 false(答案) 。
已知区间 ranges[i] = [starti, endi] ，如果整数 x 满足 starti <= x <= endi ，那么我们称整数x 被覆盖了。
3.学习经验
1.给某段区间快速加/减个值想到差分
2.构建差分数组考虑好大小，因为下面会出现d[end+1]
1. 2848.与车相交的点(简单,学习)
思想
1.给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i，nums[i] = [starti, endi] ，其中 starti 是第 i 辆车的起点，endi 是第 i 辆车的终点。
返回数轴上被车 任意部分 覆盖的整数点的数目。
2.此题给[start,end]加1，想到差分，构建差分数组(长度为max_end+2,因为会访问max_end+1),从而构建原数组，大于0说明有车
代码
class Solution {
public:
int numberOfPoints(vector<vector<int>>& nums) {
int n = nums.size();
int max_end = INT_MIN;
for (auto& num : nums)
max_end = max(max_end, num[1]);
vector<int> d(max_end + 2); // 下面有max_end+1
for (auto& num : nums) {
int start = num[0], end = num[1];
// [start,end]+1
++d[start];
--d[end + 1];
}
int res = 0, s = 0;
for (int i = 0; i < max_end + 2; ++i) { // 差分数组长度max_end+2
s += d[i];
if (s > 0)
++res;
}
return res;
}
};
2.1893.检查是否区域内所有整数都被覆盖(简单）
1893. 检查是否区域内所有整数都被覆盖 - 力扣（LeetCode）
思想
1.给你一个二维整数数组 ranges 和两个整数 left 和 right 。每个 ranges[i] = [starti, endi] 表示一个从 starti 到 endi 的 闭区间 。
如果闭区间 [left, right] 内每个整数都被 ranges 中 至少一个 区间覆盖，那么请你返回 true ，否则返回 false 。
已知区间 ranges[i] = [starti, endi] ，如果整数 x 满足 starti <= x <= endi ，那么我们称整数x 被覆盖了。
2.跟[[差分#1. 2848.与车相交的点(简单,学习)]]一样，都是[left,right]区间加1，想到差分，任何情况请先判断特殊情况，此题right>max_end直接返回false
代码
class Solution {
public:
bool isCovered(vector<vector<int>>& ranges, int left, int right) {
int n = ranges.size();
int max_end = INT_MIN;
for (auto& range : ranges) {
max_end = max(max_end, range[1]);
}
if (right > max_end)
return false; // 特殊条件
vector<int> d(max_end + 2, 0);
for (auto& range : ranges) {
int start = range[0], end = range[1];
++d[start];
--d[end + 1];
}
long long s = 0;
for (int i = 0; i < max_end + 2; ++i) {
s += d[i];
if (i >= left && i <= right) {
if (s <= 0)
return false;
} else if (i > right)
break;
}
return true;
}
};