当前位置:网站首页>[algorithm] sword finger offer2 golang interview question 13: sum of numbers of two-dimensional submatrix
[algorithm] sword finger offer2 golang interview question 13: sum of numbers of two-dimensional submatrix
2022-07-06 12:51:00 【Deng Jiawen jarvan】
[ Algorithm ] The finger of the sword offer2 golang Interview questions 13: Sum of numbers of two-dimensional submatrix
subject 1:
Ideas 1: Violent simulation
Violent simulation
Code
type NumMatrix struct {
Matrix [][]int
}
func Constructor(matrix [][]int) NumMatrix {
return NumMatrix{
Matrix: matrix}
}
//start: 17:05
// Sum of elements of two-dimensional submatrix
// Ideas : Traverse each row of the submatrix and accumulate values
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
// Processing parameters todo
// matrix
// That's ok i, Column 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); */
Ideas 2: Calculate the value of each area in advance, and then finally calculate
For example, calculate the blue area 1 The value of can be equal to the red area 2 Subtract the green area 3 And other areas 4 and 5
When we construct, we record the values of the upper left to lower right positions of the rectangle, and then obtain the time complexity of each region O(1)
Code 2
type NumMatrix struct {
sums [][]int
}
func Constructor(matrix [][]int) NumMatrix {
// first line
for j:=1; j < len(matrix[0]); j++{
matrix[0][j] = matrix[0][j-1] + matrix[0][j]
}
// The first 2-n That's ok
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
// Sum of elements of two-dimensional submatrix
// Ideas 2: Calculate ahead of time (0,0) To each point sum Then the second calculation can 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); */
边栏推荐
- (the first set of course design) sub task 1-5 317 (100 points) (dijkstra: heavy edge self loop)
- Vulnhub target: hacknos_ PLAYER V1.1
- Comparative analysis of the execution efficiency of MySQL 5.7 statistical table records
- NRF24L01 troubleshooting
- Unity scene jump and exit
- JUC forkjoin and completable future
- dosbox第一次使用
- FairyGUI循環列錶
- Solution to the problem of automatic login in Yanshan University Campus Network
- GPS高程拟合抗差中误差的求取代码实现
猜你喜欢
Design and implementation of general interface open platform - (39) simple and crude implementation of API services
Easy to use shortcut keys in idea
Expected value (EV)
Guided package method in idea
341. Flatten nested list iterator
idea中好用的快捷键
Unity3d, Alibaba cloud server, platform configuration
MySQL shutdown is slow
[算法] 剑指offer2 golang 面试题2:二进制加法
Unity3D基础入门之粒子系统(属性介绍+火焰粒子系统案例制作)
随机推荐
In 2020, the average salary of IT industry exceeded 170000, ranking first
Unity3D摄像机,键盘控制前后左右上下移动,鼠标控制旋转、放缩
Fabrication of fairygui simple Backpack
Containers and Devops: container based Devops delivery pipeline
(core focus of software engineering review) Chapter V detailed design exercises
Agile development helps me
[算法] 剑指offer2 golang 面试题13:二维子矩阵的数字之和
Idea problem record
341. Flatten nested list iterator
GNSS定位精度指标计算
[offer78] merge multiple ordered linked lists
[offer29] sorted circular linked list
Halcon knowledge: gray_ Tophat transform and bottom cap transform
[leetcode622]设计循环队列
FairyGUI人物状态弹窗
NovAtel 板卡OEM617D配置步骤记录
How to improve the deletion speed of sequential class containers?
idea中导包方法
3月15号 Go 1.18 正式版发布 了解最新特色以及使用方法
Special palindromes of daily practice of Blue Bridge Cup