【数组】剑指 Offer II 012. 左右两边子数组的和相等 | 剑指 Offer II 013. 二维子矩阵的和
剑指 Offer II 012. 左右两边子数组的和相等
原题链接:
左右两边子数组的和相等
题目:
给你一个整数数组 nums ,请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标,应该返回 最靠近左边 的那一个。如果数组不存在中心下标,返回 -1 。
示例:
输入:nums = [1,7,3,6,5,6]
输出:3
解释:
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ,
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ,二者相等。
1 <= nums.length <= 104
-1000 <= nums[i] <= 1000
题解:
// 利用一个性质, 中心元素+左边的元素和+右边元素和,就等于数组所有元素和
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int n = nums.size();
if (n <= 0) return -1;
int total = 0;
for (int i = 0; i < n; ++i)
{
// 表示数组元素总合
total += nums[i];
}
int sum = 0; // 表示一边的元素和
for (int i = 0; i < n; ++i)
{
if (nums[i] + sum * 2 == total) {
return i;
}
sum += nums[i];
}
return -1;
}
};
剑指 Offer II 013. 二维子矩阵的和
原题链接:二维子矩阵的和
题目:
给定一个二维矩阵 matrix,以下类型的多个请求:
计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2) 。
实现 NumMatrix 类:
NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。
输入:
[“NumMatrix”,“sumRegion”,“sumRegion”,“sumRegion”]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
[null, 8, 11, 12]
解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)
题解:一维前缀和
实现NumMatrix()函数,对二维数组先进行一维前缀和,保存在sums中。
创建 m 行 n+1 列的二维数组 sums,其中 m 和 n 分别是矩阵 matrix 的行数和列数,sums[i] 为 matrix[i] 的前缀和数组。将 sums 的列数设为 n+1 的目的是为了方便计算每一行的子数组和:
class NumMatrix {
public:
vector<vector<int>> sums;
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
if (m > 0) {
int n = matrix[0].size();
sums.resize(m, vector<int>(n + 1));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sums[i][j + 1] = sums[i][j] + matrix[i][j];
}
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for (int i = row1; i <= row2; i++) {
sum += sums[i][col2 + 1] - sums[i][col1];
}
return sum;
}
};
题解:二维前缀和
将 sums 的行数和列数分别设为 m+1 和 n+1 的目的是为了方便计算 sumRegion(row1,col1,row2,col2),不需要对 row1=0 和 col1=0 的情况特殊处理。此时有:
sumRegion(row1,col1,row2,col2) = sums[row2+1][col2+1] − sums[row1][col2+1] − sums[row2+1][col1] + sums[row1][col1]
class NumMatrix {
public:
vector<vector<int>> sums;
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
if (m > 0) {
int n = matrix[0].size();
sums.resize(m + 1, vector<int>(n + 1));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
}
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
}
};
模板
// 预处理前缀和数组
{
sum.resize(n+1, vector<int>(m+1,0));
// 预处理除前缀和数组(模板部分)
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
// 当前格子(和) = 上方的格子(和) + 左边的格子(和) - 左上角的格子(和) + 当前格子(值)【和是指对应的前缀和,值是指原数组中的值】
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1];
}
}
}
// 首先我们要令左上角为 (x1, y1) 右下角为 (x2, y2)
// 计算 (x1, y1, x2, y2) 的结果
{
// 前缀和是从 1 开始,原数组是从 0 开始,上来先将原数组坐标全部 +1,转换为前缀和坐标
x1++; y1++; x2++; y2++;
// 记作 22 - 12 - 21 + 11,然后 不减,减第一位,减第二位,减两位
// 也可以记作 22 - 12(x - 1) - 21(y - 1) + 11(x y 都 - 1)
ans = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
}
相关文章
- 从简单到复杂,一文带你搞懂滑动窗口在数组及字符串中的应用
- 数组赋值
- 【C语言】二维数组中的查找,杨氏矩阵
- Matlab中数组与矩阵运算
- sql 查询-字段里是逗号,分隔开的数组,查询匹配数据
- Go 稀疏数组模拟棋盘矩阵
- 【BZOJ1009】[HNOI2008]GT考试 next数组+矩阵乘法
- 数组arr的任意子序列和模m的最大值是多少?
- 剑指offer编程题解法汇总6-旋转数组中的最小数字
- 力扣解法汇总1630. 等差子数组
- php 删除二维数组中某个key值
- 《剑指offer》-- 调整数组顺序使奇数位于偶数前面、顺时针打印矩阵、数字在排序数组中出现的次数
- 61、【数组】leetcode——[高频考题]59. 螺旋矩阵 II:N*N型(C++、Python版本)
- 再来一波关于数组的操作
- 《C#零基础入门之百识百例》(二十七)多维数组 -- 转置矩阵
- Swift - 用装有控制器name的数组for循环批量创建控制器(string转UIViewController)
- JavaScript引用类型之Array数组之强大的splice()方法
- 数组置换(基础)