教育网站制作开发,网页版梦幻西游手游官网,常平镇网站建设,中小企业网站建设调研报告算法笔记#xff08;三#xff09;——前缀和算法 文章目录 算法笔记#xff08;三#xff09;——前缀和算法一维前缀和二维前缀和寻找数组的中心下标除自身以外数组的乘积和为 K 的子数组和可被 K 整除的子数组连续数组矩阵区域和 前缀和算法是一种用空间换时间的算法三——前缀和算法 文章目录 算法笔记三——前缀和算法一维前缀和二维前缀和寻找数组的中心下标除自身以外数组的乘积和为 K 的子数组和可被 K 整除的子数组连续数组矩阵区域和 前缀和算法是一种用空间换时间的算法他常常用于解决某些题目或者作为某些高级算法的组成部分
一维前缀和 题目链接DP34 【模板】前缀和 思路
通过数组arr存储输入的 n 个整数数组 dp存储数组 arr的前缀和使用循环读取数组元素并计算前缀和 dp进行q 次查询每次查询给定一个区间[l, r]。查询结果为dp[r] - dp[l-1]表示数组在区间 [l, r] 的和
C代码
#includeiostream
using namespace std;int main()
{int n, q;cin n q;long long arr[100001]{0}, dp[100001]{0};for(int i 1; i n;i){cin arr[i];dp[i] arr[i] dp[i-1];}while(q--){int l, r;cin l r;cout dp[r] - dp[l-1] endl;}return 0;
}二维前缀和 题目DP35 【模板】二维前缀和 思路 初始化前缀和 构造前缀和数组dp[i][j]其含义是从(1,1)到(i,j)区域的面积D区域也是dp[i][j]存储的值其面积也等于 ABCD初始化前缀和dp[i][j] (AB)(AC)D - A dp[i-1][j]dp[i][j-1]arr[i][j]-dp[i-1][j-1]
使用前缀和计算
D ABCD-(AB)-(AC)AD dp[i][j]-dp[i][j-1]-dp[i-1][j]dp[i-1][j-1]
C代码
#include iostream
using namespace std;int arr[1100][1100];
long long dp[1100][1100];
int n, m, q, x1, x2, y1, y2;int main()
{cin n m q;for(int i 1; i n; i){for(int j 1; j m; j){cin arr[i][j];dp[i][j] dp[i-1][j] dp[i][j-1] arr[i][j] - dp[i-1][j-1]; }}while(q--){cin x1 y1 x2 y2;cout dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] dp[x1-1][y1-1] endl;}return 0;
}寻找数组的中心下标 题目寻找数组的中心下标 思路
初始化f表示前缀和g表示后缀和f[i]表示[0,i-1]所有元素的和f[i] f[i-1] nums[i-1]g[i]表示[i1,n-1]所有元素的和g[i] g[i1] nums[i1];遍历数组nums找到一个索引使得 f[i]左侧元素的和等于 l[i]右侧元素的和
C代码
class Solution {
public:int pivotIndex(vectorint nums) {int n nums.size();vectorint f(n), g(n);for (int i 1; i n; i)f[i] f[i - 1] nums[i - 1];for (int i n - 2; i 0; i--)g[i] g[i 1] nums[i 1];for (int i 0; i n; i)if (f[i] g[i])return i;return -1;}
};除自身以外数组的乘积 题目除自身以外数组的乘积 思路
初始化f表示前缀积g表示后缀积f[i]表示[0,i-1]所有元素的积f[i] f[i - 1] * nums[i - 1]g[i]表示[i1,n-1]所有元素的积g[i] g[i1] * nums[i1];遍历数组nums计算res[i]的值
C代码
class Solution
{
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorint f(n 1);vectorint g(n 1);vectorint res(n);f[0] 1, g[n - 1] 1; for(int i 1; i n; i)f[i] f[i - 1] * nums[i - 1];for(int i n - 2; i 0; i--)g[i] g[i 1] * nums[i 1];for(int i 0; i n; i)res[i] f[i] * g[i];return res; }
};
和为 K 的子数组 题目和为 K 的子数组 思路 将问题转化为寻找和为k的子数组 而不是直接在数组中寻找和为k的连续元素 这样就可以使问题在一次遍历中解决 具体来说就是对于每个前缀和都检查是否存在一个早先的前缀和使得它们的差等于k。如果存在就找到了一个和为k的子数组
初始化一个哈希表 hash其中hash[0]表示和为 0 的子数组的个数初始化为 1两个变量 sum和 ret其中 sum 表示当前累积的和ret 表示满足条件的子数组的个数遍历数组 nums累积和并更新哈希表 对于每个元素 x更新 sum x 检查是否存在之前的累积和 sum - k 在哈希表中如果存在则累加 hash[sum - k] 到 ret。更新哈希表中的当前累积和sum 的计数
C代码
class Solution
{
public:int subarraySum(vectorint nums, int k) {// K前缀和// V前缀和出现的次数unordered_mapint, int hash;int sum 0, ans 0;// 初始化时为空区间则前缀和为0出现的次数为1hash[0] 1;for(int num : nums) {sum num; ans hash[sum - k]; // 要么为0要么为sum - k出现的次数hash[sum];}return ans;}
};和可被 K 整除的子数组 题目和可被 K 整除的子数组 补充
同余定理 若(a-b) % p k......0则a % p b % pC、Java中 负数%正数等于负数 修正 a % p p 为了a0或a0统一后(a % p p) % p
思路 和上题基本相同转化为在[0, i - 1]中找到有多少个前缀和的余数等于(sum % k k) % k
在 for(auto x : nums) 的循环中遍历数组nums。对于每个元素xsum x; 累加当前位置的元素得到当前位置的前缀和。int r (sum % k k) % kif(hash.count(r)) ret hash[r]; 检查之前是否存在相同的余数r如果存在则将哈希表中对应的次数累加到结果 ret 中。hash[r]; 更新哈希表将当前余数 r 的次数加一
C代码
class Solution
{
public:int subarraysDivByK(vectorint nums, int k) {unordered_mapint, int hash;hash[0] 1; // 初始时前缀和为 0 的余数的个数为 1 int sum 0;int ret 0;for(auto x : nums){sum x; // 当前位置前缀和int r (sum % k k) % k;if(hash.count(r)) // 检查之前是否存在相同的余数 r如果存在ret hash[r]; hash[r]; // 更新哈希表将当前余数 r 的次数加一}return ret;}
};连续数组 题目连续数组 思路
将 0 看作 -1问题就转换成在数组中找出最长的子数组使其和为0unordered_mapint, int hash表示创建一个哈希表用于存储前缀和以及对应的出现位置遍历数组nums对于每个元素 nums[i]如果 nums[i] 是 0则令 sum -1如果是1则令 sum 1。这样sum就表示当前位置的前缀和判断哈希表中是否存在当前前缀和sum。如果存在说明从上次该前缀和出现的位置到当前位置的子数组的和为零更新最长长度 ret。如果哈希表中不存在当前前缀和sum则将当前前缀和和对应的位置存入哈希表中
C代码
class Solution
{
public:int findMaxLength(vectorint nums) {unordered_mapint,int hash;hash[0] -1;int ret 0;int sum 0;for(int i 0; i nums.size(); i){sum (nums[i] 1 ? 1 : -1);if(hash.count(sum)) ret max(ret, i - hash[sum]);else hash[sum]i;}return ret;}
};矩阵区域和 题目矩阵区域和 思路 二维前缀和问题但是需要处理好边界问题
int mmat.size(), nmat[0].size()获取矩阵的行数和列数vectorvectorint dp(m1,vectorint(n1))创建二维前缀和数组dpdp[i][j]表示矩阵左上角 (0,0)到 (i-1,j-1)的元素和计算前缀和数组 dp对于每个位置(i,j)计算块的左上角和右下角的坐标确保不超过矩阵边界
C代码
class Solution
{
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k) {int m mat.size(), n mat[0].size();vectorvectorint dp(m 1, vectorint(n 1));for(int i 1; i m; i)for(int j 1; j n; j)dp[i][j] dp[i - 1][j] dp[i][j - 1] mat[i - 1][j - 1] - dp[i - 1][j - 1];vectorvectorint ret(m,vectorint(n));for(int i 0; i m; i)for(int j 0; j n; j){int x1 max(0, i - k) 1, y1 max(0, j - k) 1;int x2 min(m - 1, i k) 1, y2 min(n - 1, j k) 1;ret[i][j] dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] dp[x1 - 1][y1 - 1];}return ret;}
};
