每日算法刷题Day46 7.12:leetcode前缀和3道题和差分2道题,用时1h30min
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;} elseright = 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+1for (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+2s += 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+1for (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+2s += 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;}
};