C++前缀和算法应用:矩形区域不超过 K 的最大数值和

简介: C++前缀和算法应用:矩形区域不超过 K 的最大数值和

基础知识点

C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例

题目

给你一个 m x n 的矩阵 matrix 和一个整数 k ,找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。

题目数据保证总会存在一个数值和不超过 k 的矩形区域。

示例 1:

输入:matrix = [[1,0,1],[0,-2,3]], k = 2

输出:2

解释:蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2,且 2 是不超过 k 的最大数字(k = 2)。

示例 2:

输入:matrix = [[2,2,-1]], k = 3

输出:3

提示:

m == matrix.length

n == matrix[i].length

1 <= m, n <= 100

-100 <= matrix[i][j] <= 100

-105 <= k <= 105

分析

二维前缀和

vPreSum[r][c] 记录以(0,0)开始,宽高为c r的矩形和。vPreSum[r][c] = vPreSum[r - 1][c] + vPreSum[r][c - 1] + matrix[r - 1][c - 1] - vPreSum[r - 1][c - 1];

vPreSum[r - 1][c] 绿色实心矩形的和
vPreSum[r][c - 1] 蓝色空心矩形
matrix[r - 1][c - 1] 黄色矩形
vPreSum[r - 1][c - 1] 蓝绿重叠部分

时间复杂度O(nnn*logn)

枚举所有矩形,时间复杂度是O(n^4),超时。三层循环,第一层和第二层循环,枚举左右。第三层循环枚举下,setSum记录了所有合法的t的构成的矩形(left,0,right,t-1)的和。显然iLeftRight - setSum任意元素的值,就是(left,t,right,row)矩形的和。iLeftRight 是矩形(left,0,right,row)的和。对setSum 进行二分。

源码

class Solution {
public:
int maxSumSubmatrix(vector<vector>& matrix, int k) {
m_r = matrix.size();
m_c = matrix.front().size();
vector<vector> vPreSum(m_r+1,vector(m_c+1,0)); //vPreSum[r][c] 以(0,0)开始,宽高为c r的矩形
for (int r = 1; r <= m_r; r++)
{
for (int c = 1; c <= m_c; c++)
{
//令r=1,c=1 vPreSum[1][1] = 0 +0 + matrix[0][0] -0
//令r=2,c=2 vPreSum[2][2] = vPreSum[1][2] +vPreSum[2][1] + matrix[1][1] + vPreSum[1][1]
vPreSum[r][c] = vPreSum[r - 1][c] + vPreSum[r][c - 1] + matrix[r - 1][c - 1] - vPreSum[r - 1][c - 1];
}
}
int iMin = INT_MIN;
//vector<vector> vDebug(m_r, vector(m_c,INT_MIN));
for (int left = 0; left < m_c ; left++ )
{
for (int right = left ; right < m_c; right++ )
{
//row和right 是右下角的坐标
set setSum = { 0 };
for (int row = 0; row < m_r; row++)
{
const int iLeftRight = vPreSum[row + 1][right + 1]
• vPreSum[row + 1][left];
//iLeftRight - x <=k ==> -x <= k - iLeftRight ==> x >= iLeftRight-k
auto it = setSum.lower_bound(iLeftRight - k);
if (setSum.end() != it)
{
iMin = max(iMin, iLeftRight - *it);
//vDebug[row][right] = iLeftRight - *it;
}
setSum.emplace(iLeftRight);
}
}
}
return iMin;
}
int m_r, m_c;
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}
template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
int main()
{
vector<vector> matrix = { {1, 2, 3}, { 4,5,6 } };
int k = 2;
auto res = Solution().maxSumSubmatrix(matrix, k);
Assert(res, 2);
matrix = { {1, 0, 1}, { 0,-2,3 } };
k = 2;
res = Solution().maxSumSubmatrix(matrix, k);
Assert(res, 2);
matrix = { {2,2,-1} };
k = 3;
res = Solution().maxSumSubmatrix(matrix, k);
Assert(res, 3);
CConsole::Out(res);
}

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

鄙人想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
墨家名称的来源:有所得以墨记之。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境: VS2022 C++17


相关文章
|
2天前
|
算法 Serverless 数据处理
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
24 12
|
1天前
|
算法 安全 网络安全
基于 Python 的布隆过滤器算法在内网行为管理中的应用探究
在复杂多变的网络环境中,内网行为管理至关重要。本文介绍布隆过滤器(Bloom Filter),一种高效的空间节省型概率数据结构,用于判断元素是否存在于集合中。通过多个哈希函数映射到位数组,实现快速访问控制。Python代码示例展示了如何构建和使用布隆过滤器,有效提升企业内网安全性和资源管理效率。
27 9
|
2天前
|
机器学习/深度学习 人工智能 自然语言处理
解锁机器学习的新维度:元学习的算法与应用探秘
元学习作为一个重要的研究领域,正逐渐在多个应用领域展现其潜力。通过理解和应用元学习的基本算法,研究者可以更好地解决在样本不足或任务快速变化的情况下的学习问题。随着研究的深入,元学习有望在人工智能的未来发展中发挥更大的作用。
|
1月前
|
编译器 数据安全/隐私保护 C++
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
56 5
|
1月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
52 2
|
2月前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
1月前
|
存储 算法 安全
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
|
2月前
|
算法
|
2月前
|
存储 缓存 算法
探索企业文件管理软件:Python中的哈希表算法应用
企业文件管理软件依赖哈希表实现高效的数据管理和安全保障。哈希表通过键值映射,提供平均O(1)时间复杂度的快速访问,适用于海量文件处理。在Python中,字典类型基于哈希表实现,可用于管理文件元数据、缓存机制、版本控制及快速搜索等功能,极大提升工作效率和数据安全性。
74 0
|
2天前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。