当前位置：首页 > news >正文

【C++二分查找前缀和】1292. 元素和小于等于阈值的正方形的最大边长

news 来源：原创 2024/9/21 5:35:28

本文涉及的基础知识点

C++二分查找
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频

LeetCode1292. 元素和小于等于阈值的正方形的最大边长

给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。
请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0 。

示例 1：
输入：mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
在这里插入图片描述

输出：2
解释：总和小于或等于 4 的正方形的最大边长为 2，如图所示。
示例 2：
输入：mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
输出：0
提示：
m == mat.length
n == mat[i].length
1 <= m, n <= 300
0 <= mat[i][j] <= 10⁴
0 <= threshold <= 10⁵

二分查找、前缀和

预处理好前缀和后，可以在O(1)的时间内，计算矩形之和。
二分查找类型：寻找末端
Check函数的参数返回：[1,min(n,m)]
异常处理：如果Check(ret)不成立，则返回0。
Check函数：枚举各矩形的左上角，如果和小于等于阈值，返回true。否则返回false。Check函数的时间复杂度：O(nm)
总时间复杂度：O(log(min(n,m))nm)

代码

核心代码

template<class T = int>
class CPreSum2 {
public:template<class _Pr>CPreSum2(int rowCnt, int colCount, _Pr pr) :m_iRowCnt(rowCnt), m_iColCnt(colCount) {m_vSum.assign(rowCnt + 1, vector<int>(colCount + 1));for (int r = 0; r < rowCnt; r++) {for (int c = 0; c < colCount; c++) {m_vSum[r + 1][c + 1] = m_vSum[r][c + 1] + m_vSum[r + 1][c] - m_vSum[r][c] + pr(r, c);}}}T Get(int left, int top, int right, int bottom)const {return m_vSum[bottom + 1][right + 1] - m_vSum[top][right + 1] - m_vSum[bottom + 1][left] + m_vSum[top][left];}T GetTopLeft(int left, int top) { return Get(left, top, m_iColCnt - 1, m_iRowCnt - 1); }vector<vector<T>> m_vSum;const int m_iRowCnt, m_iColCnt;
};
template<class INDEX_TYPE>
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}template<class _Pr>INDEX_TYPE FindFrist( _Pr pr){auto left = m_iMin - 1;auto rightInclue = m_iMax;while (rightInclue - left > 1){const auto mid = left + (rightInclue - left) / 2;if (pr(mid)){rightInclue = mid;}else{left = mid;}}return rightInclue;}template<class _Pr>INDEX_TYPE FindEnd( _Pr pr){int leftInclude = m_iMin;int right = m_iMax + 1;while (right - leftInclude > 1){const auto mid = leftInclude + (right - leftInclude) / 2;if (pr(mid)){leftInclude = mid;}else{right = mid;}}return leftInclude;}
protected:const INDEX_TYPE m_iMin, m_iMax;
};class Solution {public:int maxSideLength(vector<vector<int>>& mat, int threshold) {m_r = mat.size();m_c = mat.front().size();CPreSum2<int> preSum(m_r, m_c, [&](const int& r, const int& c) {return mat[r][c]; });			auto Check = [&](int mid) {for (int r = 0; r+mid <= m_r; r++) {for (int c = 0; c+mid <= m_c; c++) {const int sum = preSum.Get(c, r, c + mid - 1, r + mid - 1);if (sum <= threshold) { return true; }}}return false;};return CBinarySearch<int>(0, min(m_r, m_c)).FindEnd(Check);}int m_r, m_c;};

单元测试

	vector<vector<int>> mat;int threshold;TEST_METHOD(TestMethod13){mat = { {1,1,3,2,4,3,2},{1,1,3,2,4,3,2},{1,1,3,2,4,3,2} }, threshold = 4;auto res = Solution().maxSideLength(mat, threshold);AssertEx(2, res);}TEST_METHOD(TestMethod14){mat = { {2,2,2,2,2},{2,2,2,2,2},{2,2,2,2,2},{2,2,2,2,2},{2,2,2,2,2} }, threshold = 1;auto res = Solution().maxSideLength(mat, threshold);AssertEx(0, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功