当前位置:网站首页>[算法] 剑指offer2 golang 面试题13:二维子矩阵的数字之和
[算法] 剑指offer2 golang 面试题13:二维子矩阵的数字之和
2022-07-06 09:18:00 【邓嘉文Jarvan】
[算法] 剑指offer2 golang 面试题13:二维子矩阵的数字之和
题目1:
思路1: 暴力模拟
暴力模拟
代码
type NumMatrix struct {
Matrix [][]int
}
func Constructor(matrix [][]int) NumMatrix {
return NumMatrix{
Matrix: matrix}
}
//start: 17:05
//二维子矩阵的元素和
//思路: 遍历子矩阵的每一行累加值即可
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
//参数处理 todo
//矩阵
//行i,列j
sum := 0
for i:=row1; i <= row2; i++ {
for j:=col1; j <= col2; j++{
sum += this.Matrix[i][j]
}
}
return sum
}
/** * Your NumMatrix object will be instantiated and called as such: * obj := Constructor(matrix); * param_1 := obj.SumRegion(row1,col1,row2,col2); */
思路2: 提前算好每个区域的值然后最后计算
比如计算蓝色区域1的值可以等于红色区域2减去绿色区域3和其他区域4和5
我们在构造的时候记录好矩形左上到右下位置的值然后获得每个区域的时候时间复杂度是 O(1)
代码2
type NumMatrix struct {
sums [][]int
}
func Constructor(matrix [][]int) NumMatrix {
//第一行
for j:=1; j < len(matrix[0]); j++{
matrix[0][j] = matrix[0][j-1] + matrix[0][j]
}
//第2-n行
for i:=1; i < len(matrix); i++ {
sum := 0
for j:=0; j < len(matrix[0]); j++{
sum += matrix[i][j]
matrix[i][j] = sum + matrix[i-1][j]
}
}
return NumMatrix{
sums: matrix}
}
//start: 17:05
//二维子矩阵的元素和
//思路2: 提前计算好(0,0)到每个点的sum然后第二次计算就能O(1)
//a1 - a2 - a3 -a4
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
a1 := this.sums[row2][col2]
a2 := 0
a3 := 0
a4 := 0
if row1 >= 1 {
a2 = this.sums[row1-1][col1]
if col1 >= 1 {
a2 = this.sums[row1-1][col1-1]
}
}
if row1 >= 1 {
a3 = this.sums[row1-1][col2] - a2
}
if col1 >= 1 {
a4 = this.sums[row2][col1-1] - a2
}
return a1 - a2 - a3 - a4
}
/** * Your NumMatrix object will be instantiated and called as such: * obj := Constructor(matrix); * param_1 := obj.SumRegion(row1,col1,row2,col2); */
边栏推荐
猜你喜欢
Unity3D,阿里云服务器,平台配置
Derivation of logistic regression theory
Problèmes avec MySQL time, fuseau horaire, remplissage automatique 0
抗差估计在rtklib的pntpos函数(标准单点定位spp)中的c代码实现
單片機藍牙無線燒錄
Office prompts that your license is not genuine pop-up box solution
第一人称视角的角色移动
Halcon knowledge: gray_ Tophat transform and bottom cap transform
There is no red exclamation mark after SVN update
KF UD分解之UD分解基础篇【1】
随机推荐
C programming exercise
MySQL performance tuning - dirty page refresh
JS Title: input array, exchange the largest with the first element, exchange the smallest with the last element, and output array.
【GNSS数据处理】赫尔默特(helmert)方差分量估计解析及代码实现
[leetcode622]设计循环队列
Compile GDAL source code with nmake (win10, vs2022)
HCIP Day 12
FairyGUI简单背包的制作
Compilation principle: preprocessing of source program and design and implementation of lexical analysis program (including code)
数据库课程设计:高校教务管理系统(含代码)
Guided package method in idea
FairyGUI复选框与进度条的组合使用
The service robots that have been hyped by capital and the Winter Olympics are not just a flash in the pan
FairyGUI增益BUFF数值改变的显示
[offer29] sorted circular linked list
(1) Introduction Guide to R language - the first step of data analysis
NRF24L01故障排查
Fairygui loop list
Problèmes avec MySQL time, fuseau horaire, remplissage automatique 0
Mixed use of fairygui button dynamics