wordpress+andriod,新站优化,wordpress git 伪静态,网络营销出来可以干什么工作文章目录 C 前缀和详解#xff1a;基础题解与思维分析前言第一章#xff1a;前缀和基础应用1.1 一维前缀和模板题解法#xff08;前缀和#xff09;图解分析C代码实现易错点提示代码解读题目解析总结 1.2 二维前缀和模板题解法#xff08;二维前缀和#xff09;图解分析C… 文章目录 C 前缀和详解基础题解与思维分析前言第一章前缀和基础应用1.1 一维前缀和模板题解法前缀和图解分析C代码实现易错点提示代码解读题目解析总结 1.2 二维前缀和模板题解法二维前缀和图解分析C代码实现易错点提示代码解读题目解析总结 1.3 寻找数组的中⼼下标easy解法前缀和图解分析C代码实现更简单的解法优化后的 C代码实现 易错点提示代码解读 28. 除⾃⾝以外数组的乘积medium解法前缀积数组图解分析C代码实现更简单的解法优化后的 C代码实现 易错点提示代码解读 写在最后 C 前缀和详解基础题解与思维分析 欢迎讨论如有疑问或见解欢迎在评论区留言互动。 点赞、收藏与分享如觉得这篇文章对您有帮助请点赞、收藏并分享 分享给更多人欢迎分享给更多对 C 感兴趣的朋友一起学习前缀和的基础与进阶 前言 前缀和是一种经典的算法技巧用于高效地计算数组的某一区间内的元素和。它通过预处理一个前缀和数组将区间求和的问题转化为常数时间的查询操作。本篇博客将详细讲解前缀和的原理并结合题目解析让大家掌握这一高效的算法方法。 第一章前缀和基础应用
1.1 一维前缀和模板题
题目链接【模板】一维前缀和
题目描述
给定一个长度为 n 的整数数组 arr 和 q 个查询每个查询由两个整数 l 和 r 组成表示区间 [l, r]。请计算出每个区间内所有元素的和。
示例 1
输入arr [1, 2, 3, 4, 5], q 2, 查询区间为 [(1, 3), (2, 4)]输出[6, 9]解释区间 [1, 3] 的元素和为 1 2 3 6区间 [2, 4] 的元素和为 2 3 4 9。
提示
1 n, q 100000-10000 arr[i] 10000 解法前缀和
算法思路
a. 预处理前缀和数组
使用 dp[i] 表示从数组起始位置到第 i 个元素的累加和。递推公式为dp[i] dp[i - 1] arr[i];通过一次遍历即可构建前缀和数组时间复杂度为 O(n)。
b. 利用前缀和快速计算区间和
使用前缀和数组可以在 O(1) 的时间内计算出任意区间 [l, r] 的和sum(l, r) dp[r] - dp[l - 1];这个公式的核心在于利用 dp[r] 存储了 [1, r] 区间的和而 dp[l - 1] 则存储了 [1, l-1] 区间的和二者相减即得 [l, r] 区间内的和。 图解分析
假设 arr [1, 2, 3, 4, 5]查询区间为 [(1, 3), (2, 4)] 前缀和数组构建 dp[1] arr[1] 1dp[2] dp[1] arr[2] 1 2 3dp[3] dp[2] arr[3] 3 3 6dp[4] dp[3] arr[4] 6 4 10dp[5] dp[4] arr[5] 10 5 15 查询区间和计算 对于区间 [1, 3]sum(1, 3) dp[3] - dp[0] 6对于区间 [2, 4]sum(2, 4) dp[4] - dp[1] 9
前缀和数组
Indexarr[i]dp[i]11122333644105515 C代码实现
#include iostream
#include vector
using namespace std;const int N 100010;
vectorlong long arr(N), dp(N); // 使用 vector 存储数组和前缀和
int n, q; // n 为数组大小q 为查询次数int main()
{cin n q;// 读取数组元素for(int i 1; i n; i) cin arr[i];// 构建前缀和数组dp[i] 表示从 arr[1] 到 arr[i] 的累加和for(int i 1; i n; i) dp[i] dp[i - 1] arr[i];// 处理每个查询while(q--){int l, r;cin l r;// 输出区间和 [l, r]cout dp[r] - dp[l - 1] endl;}return 0;
} 易错点提示 前缀和数组的下标范围 dp[i] 表示从 arr[1] 到 arr[i] 的累加和因此在构建前缀和数组时需要从 i 1 开始而非 0。读取 arr 时也应从 1 开始。 边界条件处理 当 l 1 时dp[l - 1] 为 0。确保 dp[0] 初始化为 0以避免边界查询时产生错误。 数组长度与内存大小 arr 和 dp 的长度都最少需要定义为 n1 以确保不会越界。尤其在大规模数据时需要合理定义 N 以避免内存溢出。 代码解读
在这段代码中我们首先通过输入构建了原数组 arr 和相应的前缀和数组 dp。然后通过预处理后的 dp 数组能够快速计算出任意查询区间 [l, r] 的和。 整个过程只需要 O(n) 的时间构建前缀和数组再通过 O(1) 的时间解决每个区间和查询使得在多次查询场景下效率非常高。 题目解析总结 前缀和是一种非常常用的算法技巧特别是在处理区间求和问题时能够显著优化计算效率。通过一次遍历构建前缀和数组我们可以在后续查询中轻松地利用前缀和的特性实现对任意区间的快速求和。 这道题作为前缀和的模板题帮助我们掌握了前缀和的核心思想与基本操作。通过它我们能为后续更复杂的区间问题打下坚实的基础。 1.2 二维前缀和模板题
题目链接【模板】二维前缀和
题目描述
给定一个大小为 n × m 的矩阵 matrix 和 q 个查询每个查询由四个整数 x1, y1, x2, y2 组成表示一个子矩阵的左上角 (x1, y1) 和右下角 (x2, y2)。请计算出每个子矩阵内所有元素的和。
示例 1
输入matrix [[1, 2], [3, 4]], q 1, 查询区间为 [(1, 1, 2, 2)]输出[10]解释子矩阵包含所有元素 1 2 3 4 10。
提示
1 n, m 1000-10000 matrix[i][j] 10000 解法二维前缀和
算法思路
类似于一维前缀和我们可以预处理一个前缀和矩阵 sum使得 sum[i][j] 表示从矩阵起点 (1, 1) 到位置 (i, j) 的所有元素的累加和。利用这个前缀和矩阵可以在 O(1) 时间内求出任意子矩阵的和。
步骤分为两部分 构建前缀和矩阵 构建时我们在矩阵的顶部和左侧添加一行和一列的 0以简化边界处理。 前缀和矩阵的递推公式为 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) 的查询我们可以通过以下公式计算该子矩阵的和result sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] sum[x1 - 1][y1 - 1];类比小学就学过的求面积 图解分析
假设 matrix [[1, 2], [3, 4]]q 1查询区间为 [(1, 1, 2, 2)] 构建前缀和矩阵 原始矩阵1 2
3 4构建前缀和矩阵sum
0 0 0
0 1 3
0 4 10查询子矩阵和 对于 x1 1, y1 1, x2 2, y2 2result sum[2][2] - sum[0][2] - sum[2][0] sum[0][0] 10 - 0 - 0 0 10C代码实现
#include iostream
#include vector
using namespace std;int main()
{int n, m, q;cin n m q;vectorvectorint matrix(n 1, vectorint(m 1, 0));vectorvectorlong long sum(n 1, vectorlong long(m 1, 0));// 读取矩阵数据for(int i 1; i n; i) {for(int j 1; j m; j) {cin matrix[i][j];}}// 构建前缀和矩阵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][j];}}// 处理查询while(q--) {int x1, y1, x2, y2;cin x1 y1 x2 y2;long long result sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] sum[x1 - 1][y1 - 1];cout result endl;}return 0;
}易错点提示 矩阵下标的处理 构建前缀和矩阵时注意在 matrix 的基础上偏移一行和一列以简化边界处理。查询时也需调整下标。 前缀和公式理解 在计算 sum[i][j] 时记得同时减去重复计算的 sum[i - 1][j - 1]。 处理大规模输入 对于 n, m 较大的输入使用 long long 类型存储累加和以避免整数溢出。 代码解读
时间复杂度前缀和矩阵的构建时间为 O(n * m)每次查询时间为 O(1)适用于大量查询场景。空间复杂度前缀和矩阵 sum 需要 O(n * m) 的额外空间。 题目解析总结 二维前缀和是处理矩阵区域和问题的利器通过一次性构建前缀和矩阵可以高效地解决任意子矩阵的求和问题。相比于逐个元素累加的方法前缀和能大幅减少计算次数使得算法在面对多次查询时表现更佳。 1.3 寻找数组的中⼼下标easy
题目链接724. 寻找数组的中⼼下标
题目描述
给你⼀个整数数组 nums 请计算数组的 中⼼下标 。
数组 中⼼下标 是数组的⼀个下标其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中⼼下标位于数组最左端那么左侧数之和视为 0因为在下标的左侧不存在元素。这⼀点对中⼼下标位于数组最右端同样适⽤。
如果数组有多个中⼼下标应该返回 最靠近左边 的那⼀个。如果数组不存在中⼼下标返回 -1。
示例 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 ⼆者相等。
示例 2
输入nums [1, 2, 3]输出-1解释 数组中不存在满⾜此条件的中⼼下标。
示例 3
输入nums [2, 1, -1]输出0解释 中⼼下标是 0。左侧数之和 sum 0下标 0 左侧不存在元素右侧数之和 sum nums[1] nums[2] 1 -1 0。
提示
1 nums.length 10^4-1000 nums[i] 1000 解法前缀和
算法思路
根据中⼼下标的定义除了中⼼下标的元素外该元素左边的「前缀和」等于该元素右边的「后缀和」。
因此我们可以先预处理两个数组一个表示前缀和另一个表示后缀和。然后通过遍历来找到满足条件的中⼼下标。 构建前缀和数组 lsum lsum[i] 表示 nums 从开始到位置 i - 1 的所有元素的和即 [0, i - 1] 区间的累加和。构建前缀和数组 lsum 的递推公式为lsum[i] lsum[i - 1] nums[i - 1];构建后缀和数组 rsum rsum[i] 表示 nums 从位置 i 1 到最后一个元素的所有元素的和即 [i 1, n - 1] 区间的累加和。构建后缀和数组 rsum 的递推公式为rsum[i] rsum[i 1] nums[i 1];枚举中⼼下标 遍历数组比较每个位置的前缀和 lsum[i] 和后缀和 rsum[i] 是否相等。如果相等说明该位置就是中⼼下标直接返回。若遍历完成仍无满足条件的下标则返回 -1。 图解分析
假设 nums [1, 7, 3, 6, 5, 6] 前缀和数组构建 lsum[0] 0 表示 nums 的左侧没有元素lsum[1] lsum[0] nums[0] 0 1 1lsum[2] lsum[1] nums[1] 1 7 8lsum[3] lsum[2] nums[2] 8 3 11lsum[4] lsum[3] nums[3] 11 6 17lsum[5] lsum[4] nums[4] 17 5 22 后缀和数组构建 rsum[5] 0 表示 nums 的右侧没有元素rsum[4] rsum[5] nums[5] 0 6 6rsum[3] rsum[4] nums[4] 6 5 11rsum[2] rsum[3] nums[3] 11 6 17rsum[1] rsum[2] nums[2] 17 3 20rsum[0] rsum[1] nums[1] 20 7 27 查找中⼼下标 遍历过程中发现 lsum[3] rsum[3]即下标 3 满足条件因此输出 3。
前缀和、后缀和数组
Indexnums[i]lsum[i]rsum[i]0102717120238173611114517656220 C代码实现
class Solution {
public:int pivotIndex(vectorint nums) {// lsum[i] 表示 [0, i - 1] 区间的累加和// rsum[i] 表示 [i 1, n - 1] 区间的累加和int n nums.size();vectorint lsum(n), rsum(n);// 预处理前缀和数组for(int i 1; i n; i)lsum[i] lsum[i - 1] nums[i - 1];// 预处理后缀和数组for(int i n - 2; i 0; i--)rsum[i] rsum[i 1] nums[i 1];// 查找中⼼下标for(int i 0; i n; i) {if(lsum[i] rsum[i])return i;}return -1;}
};更简单的解法
该问题还可以通过更为简洁的解法实现仅需一个变量记录累加的前缀和节省空间。
优化思路
遍历数组时如果一个位置 i 满足 2 * 前缀和 nums[i] 总和则它就是中心下标。其原理在于
对于中心下标 i数组的左侧和 tmp 与右侧和总和 - tmp - nums[i]相等。即满足条件 2 * tmp nums[i] 总和。 优化后的 C代码实现
class Solution {
public:int pivotIndex(vectorint nums) {int totalSum 0, tmp 0;// 计算总和for(int num : nums) {totalSum num;}// 遍历数组判断中心下标条件for(int i 0; i nums.size(); i) {if(2 * tmp nums[i] totalSum) {return i; // 找到中心下标}tmp nums[i]; // 更新前缀和}return -1; // 没有找到中心下标}
};易错点提示 前缀和和后缀和的下标范围 lsum[i] 表示 [0, i - 1] 区间累加和而 rsum[i] 表示 [i 1, n - 1] 区间累加和。因此遍历中我们直接使用 lsum[i] rsum[i] 即可判断条件。 边界处理 若中心下标在数组最左端或最右端需要确保对应的 lsum 或 rsum 是 0这样才能保证正确的判断。 多种中心下标 如果存在多个中心下标返回最左边的那个因此遍历时找到第一个满足条件的下标即返回。 代码解读
我们先通过遍历构建了 lsum 和 rsum 数组然后再次遍历数组找到第一个满足 lsum[i] rsum[i] 的位置。
时间复杂度O(n)遍历数组的次数为常数次适合于长度较大的数组。空间复杂度O(n)额外的前缀和和后缀和数组 lsum 和 rsum。
对于优化后的解法
时间复杂度O(n)仅需一次遍历。空间复杂度O(1)只使用一个临时变量记录前缀和显著节省了空间。 28. 除⾃⾝以外数组的乘积medium
题目链接238. 除⾃⾝以外数组的乘积
题目描述
给你⼀个整数数组 nums返回数组 answer其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
题⽬数据保证数组 nums 中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。
请不要使⽤除法且在 O(n) 时间复杂度内完成此题。
示例 1
输入nums [1, 2, 3, 4]输出[24, 12, 8, 6]
示例 2
输入nums [-1, 1, 0, -3, 3]输出[0, 0, 9, 0, 0]
提示
2 nums.length 10^5-30 nums[i] 30保证数组 nums 中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。
进阶你可以在 O(1) 的额外空间复杂度内完成这个题⽬吗出于对空间复杂度分析的⽬的输出数组不被视为额外空间。 解法前缀积数组
算法思路 由于题目要求不能使用除法同时要求 O(n) 的时间复杂度因此我们不能用求出整个数组的乘积然后除以单个元素的方式求解。 可以利用前缀和思想使用两个数组来记录每个元素的前缀积和后缀积然后将两者相乘得到每个元素除自身以外的乘积。 定义前缀积数组 lprod lprod[i] 表示 nums 从开始到 i - 1 的所有元素的乘积即 [0, i - 1] 区间内所有元素的乘积。构建前缀积数组 lprod 的递推公式为lprod[i] lprod[i - 1] * nums[i - 1];定义后缀积数组 rprod rprod[i] 表示 nums 从 i 1 到数组末尾的所有元素的乘积即 [i 1, n - 1] 区间内所有元素的乘积。构建后缀积数组 rprod 的递推公式为rprod[i] rprod[i 1] * nums[i 1];计算结果数组 遍历 nums计算每个位置 i 的结果 ret[i] 为 lprod[i] * rprod[i]。因为 lprod[i] 包含的是 nums[0] 到 nums[i - 1] 的乘积而 rprod[i] 包含的是 nums[i 1] 到末尾的乘积两者相乘即为除 nums[i] 外的所有元素乘积。 图解分析
假设 nums [1, 2, 3, 4]期望的结果为 [24, 12, 8, 6] 前缀积数组构建 lprod[0] 1 初始条件表示没有元素的乘积lprod[1] lprod[0] * nums[0] 1 * 1 1lprod[2] lprod[1] * nums[1] 1 * 2 2lprod[3] lprod[2] * nums[2] 2 * 3 6 后缀积数组构建 rprod[3] 1 初始条件表示没有元素的乘积rprod[2] rprod[3] * nums[3] 1 * 4 4rprod[1] rprod[2] * nums[2] 4 * 3 12rprod[0] rprod[1] * nums[1] 12 * 2 24 计算最终结果 ret[0] lprod[0] * rprod[0] 1 * 24 24ret[1] lprod[1] * rprod[1] 1 * 12 12ret[2] lprod[2] * rprod[2] 2 * 4 8ret[3] lprod[3] * rprod[3] 6 * 1 6
前缀积、后缀积数组
Indexnums[i]lprod[i]rprod[i]ret[i]011242412112122324834616 C代码实现
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorint lprod(n, 1), rprod(n, 1), ret(n);// 构建前缀积数组for(int i 1; i n; i) {lprod[i] lprod[i - 1] * nums[i - 1];}// 构建后缀积数组for(int i n - 2; i 0; i--) {rprod[i] rprod[i 1] * nums[i 1];}// 计算结果数组for(int i 0; i n; i) {ret[i] lprod[i] * rprod[i];}return ret;}
};更简单的解法
优化思路
我们可以进一步优化空间复杂度到 O(1)。通过仅使用一个 ret 数组来存储结果并利用它保存前缀积再遍历一次通过累积的后缀积来更新结果
计算前缀积并保存到 ret 中。遍历并乘以后缀积在遍历过程中同时更新后缀积的值使每个位置的结果在不需要额外的 lprod 和 rprod 数组的情况下得到。 优化后的 C代码实现
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorint ret(n, 1);// 计算前缀积for(int i 1; i n; i) {ret[i] ret[i - 1] * nums[i - 1];}// 计算后缀积并更新结果int suffixProd 1;for(int i n - 1; i 0; i--) {ret[i] * suffixProd;suffixProd * nums[i];}return ret;}
};易错点提示 初始条件 lprod[0] 和 rprod[n-1] 都初始化为 1表示没有元素的乘积。 空间优化 优化解法中只使用 ret 数组存储前缀积后续遍历时逐个乘以后缀积。 避免溢出 题目保证元素乘积在 32 位整数范围内但实际操作时要避免大数溢出注意数据类型的使用。 代码解读
在此解法中我们通过构建前缀积和后缀积的方式实现了在 O(n) 时间复杂度下计算每个位置的乘积。在优化方案中通过巧妙地在结果数组中存储前缀积并逐步累加后缀积实现了空间复杂度的优化。
时间复杂度O(n)无论是初始计算前缀积和后缀积还是单次遍历时间复杂度都为 O(n)。空间复杂度原方案为 O(n)优化方案达到 O(1) 的额外空间复杂度。 写在最后 在这片数列的流动之中我们从前缀和的入门渐次深入直抵算法思想的核心。四道基础题如同桥梁串联起前缀和与后缀积的巧妙应用从区间求和的简明优雅到排除自身后的乘积演算每一步都指向数据处理的无限可能。这是算法的序曲数字的暗涌如流水般轻盈而深邃。随着思维渐入佳境我们将在下篇中进一步探索数列的复杂美揭开更深层的优化思路与算法之光同行。 以上就是关于【优选算法篇】前缀之序后缀之章于数列深处邂逅算法的光与影的内容啦各位大佬有什么问题欢迎在评论区指正您的支持是我创作的最大动力❤️
