个人网站命名的要求,公司简介范本文字,高端营销型企业网站建设,门户网站怎么建设需要多长时间前缀和 前缀和1. 前缀和【模板】2. 二维前缀和【模板】3. 寻找数组的中心下标4. 除自身以外数组的乘积5. 和为K的子数组6. 和可被K整除的子数组7. 连续数组8. 矩阵区域和 前缀和
1. 前缀和【模板】
题目链接 - Nowcoder -DP34.前缀和【模板】
Nowcoder -DP34.前缀和【模… 前缀和 前缀和1. 前缀和【模板】2. 二维前缀和【模板】3. 寻找数组的中心下标4. 除自身以外数组的乘积5. 和为K的子数组6. 和可被K整除的子数组7. 连续数组8. 矩阵区域和 前缀和
1. 前缀和【模板】
题目链接 - Nowcoder -DP34.前缀和【模板】
Nowcoder -DP34.前缀和【模板】
题目给定一个长度为n的数组 a1, a2, …an. 接下来有q次查询, 每次查询有两个参数l, r. 对于每个询问, 请输出 al al 1 … ar
输入描述 第一行包含两个整数n和q. 第二行包含n个整数, 表示 a1, a2, …an. 接下来q行, 每行包含两个整数 l 和 r. 1 ≤ n, q ≤ 10^5 −10^9 ≤ a[i] ≤ 10^9 1 ≤ l ≤ r ≤n
输出描述 输出q行, 每行代表一次查询的结果.
示例1 输入 3 2 1 2 4 1 2 2 3
输出 3 6
思路
先预处理出来⼀个「前缀和」数组
用 dp[i] 表示 [1, i] 区间内所有元素的和那么 dp[i - 1] 里面存的就是 [1, i - 1] 区间内所有元素的和那么可得递推公式 dp[i] dp[i - 1] arr[i]
使用前缀和数组「快速」求出「某⼀个区间内」所有元素的和
当询问的区间是 [l, r] 时区间内所有元素的和为 dp[r] - dp[l - 1]
代码如下 #include iostream#include vectorusing namespace std;int main() {int n 0, q 0;cin n q;// 读取数据vectorlong long arr(n 1);for(int i 1; i n; i) cin arr[i];// 处理前缀和数组vectorlong long dp(n 1);for(int i 1; i n; i)dp[i] dp[i - 1] arr[i];// 计算区间和while(q--){int l 0, r 0;cin l r;cout dp[r] - dp[l - 1] endl;}return 0;}2. 二维前缀和【模板】
题目链接 - Nowcoder -DP35.二维前缀和【模板】
Nowcoder -DP35.二维前缀和【模板】
题目给你一个 n 行 m 列的矩阵 A 下标从1开始。 接下来有 q 次查询每次查询输入 4 个参数 x1, y1, x2, y2 请输出以(x1, y1) 为左上角, (x2, y2) 为右下角的子矩阵的和
输入描述 第一行包含三个整数n, m, q. 接下来n行每行m个整数代表矩阵的元素 接下来q行每行4个整数x1, y1, x2, y2分别代表这次查询的参数
1 n,m 1000 1 q 10^5 -10^9 a[i][j] 10^9 1 x1 x2 n 1 y1 y2 m
输出描述 输出q行每行表示查询结果。
思路前缀和 1、首先搞出来前缀和矩阵这里就要用到一维数组里面的拓展知识我们要在矩阵的最上面和最左边添加上一行和一列 0这样我们就可以省去非常多的边界条件的处理处理后的矩阵就像这样 这样我们填写前缀和矩阵数组的时候下标直接从 1 开始能大胆使用 i - 1 , j - 1 位置的值。 注意 dp 表与原数组 matrix 内的元素的映射关系
从 dp 表到 matrix 矩阵横纵坐标减一从 matrix 矩阵到 dp 表横纵坐标加一
前缀和矩阵中 dp[i][j] 的含义以及如何递推二维前缀和方程
dp[i][j] 的含义 dp[i][j] 表示从 [0, 0] 位置到 [i, j] 位置这段区域内所有元素的累加和。对应下图的红色区域 递推方程
我们可以将 [0, 0] 位置到 [i, j] 位置这段区域分解成下面的部分 dp[i][j] 红 蓝 绿 紫分析一下这四块区域
紫色部分最简单它就是原数组矩阵中的 matrix[i - 1][j - 1] 注意坐标的映射关系单独的蓝不好求因为它不是我们定义的状态表示中的区域同理单独的绿也是但是如果是红 蓝正好是我们 dp 数组矩阵中 dp[i - 1][j] 的值同理如果是红 绿正好是我们 dp 数组矩阵中 dp[i][j - 1] 的值如果把上面求的三个值加起来那就是紫 红 蓝 红 绿发现多算了一部分红的面积因此再单独减去红的面积即可红的面积正好也是符合 dp 数组的定义的即 dp[i - 1][j - 1]
综上所述我们的 dp 矩阵递推方程就是 dp[i][j]dp[i - 1][j] dp[i][j - 1] - dp[i - 1][j - 1]matrix[i - 1][j - 1]
2、使用 dp 前缀和矩阵
我们可以继续使用下面这个图题中求的是 [x1, y1] 到 [x2, y2] 的面积 也可以画出具体的图理解如下图所示 接下来分析如何使用这个前缀和矩阵假设上图中这里的 x 和 y 都处理过了对应的正是 dp 矩阵中的下标
因此我们要求的就是紫色部分的面积继续分析几个区域
红色能直接求出来就是 dp[x1 - 1][y1 - 1] 为什么减一因为要剔除掉 x1 这一行和 y1 这一列这一行和这一列是要求出来的结果的一部分蓝色直接求不好求但是和红色拼起来正好是 dp 表内 dp[x1 - 1][y2] 的数据同理绿色不好求但是 红 绿 dp[x2][y1 - 1] 再看看整个面积非常好求正好是 dp[x2][y2] 那么紫色 整个面积 - 红 - 蓝 - 绿但是蓝绿不好求我们可以这样减整个面积 -蓝 红-绿 红这样相当于多减去了一个红再加上即可
综上所述紫 整个面积 -蓝 红- 绿 红 红从而可得紫色区域内的元素总和为dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] dp[x1 - 1][y1 - 1]
思路介绍完毕代码如下 #include iostream#include vectorusing namespace std;int main() {int n 0, m 0, q 0; cin n m q;// 输入矩阵vectorvectorlong long arr(n 1, vectorlong long(m 1));for(int i 1; i n; i)for(int j 1; j m; j)cin arr[i][j];// 预处理创建一个 dp 矩阵vectorvectorlong long dp(n 1, vectorlong long(m 1));for(int i 1; i n; i)for(int j 1; j m; j)dp[i][j] dp[i - 1][j] dp[i][j - 1] - dp[i - 1][j - 1] arr[i][j];// 使用矩阵查询while(q--){int x1, y1, x2, y2;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;}3. 寻找数组的中心下标
题目链接 - Leetcode -724.寻找数组的中心下标
Leetcode -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^41000 nums[i] 1000
思路从中心下标的定义可知除中心下标的元素外该元素左边的「前缀和」等于该元素右边的「后缀和」。
因此我们可以先预处理出来两个数组⼀个表示前缀和另一个表示后缀和。然后我们可以用一个 for 循环枚举可能的中心下标判断每一个位置的「前缀和」以及「后缀和」如果二者相等就返回当前下标。
代码如下 class Solution {public:// 前缀和思想int pivotIndex(vectorint nums) {int n nums.size();vectorint dp(n 1);// 先填表for(int i 1; i n; i)dp[i] dp[i - 1] nums[i - 1];// 使用 dp 表for(int i 1; i n; i)if(dp[i - 1] dp[n] - dp[i]) return i - 1;return -1;}};4. 除自身以外数组的乘积
题目链接 - Leetcode -238.除自身以外数组的乘积
Leetcode -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^530 nums[i] 30
保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
思路根据题意对于每⼀个位置的最终结果 ret[i] 它是由两部分组成的
nums[0] * nums[1] * nums[2] * … * nums[i - 1]nums[i 1] * nums[i 2] * … * nums[n - 1]
于是我们可以利用前缀和的思想使用两个数组 f 和 g分别处理出来两个信息
f[i] 表示i 位置之前的所有元素即 [0, i - 1] 区间内所有元素的前缀乘积g[i] 表示i 位置之后的所有元素即 [i 1, n - 1] 区间内所有元素的后缀乘积
然后再处理最终结果
代码如下 class Solution {public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorint f(n, 1), g(n, 1), dp(n);// f[i] 表示i 位置之前的所有元素即 [0, i - 1] 区间内所有元素的前缀乘积; // g[i] 表示i 位置之后的所有元素即 [i 1, n - 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) dp[i] f[i] * g[i];return dp;}};5. 和为K的子数组
题目链接 - Leetcode -560.和为K的子数组
Leetcode -560.和为K的子数组
题目给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的连续子数组的个数 。 子数组是数组中元素的连续非空序列。
示例 1 输入nums [1, 1, 1], k 2 输出2
示例 2 输入nums [1, 2, 3], k 3 输出2
提示
1 nums.length 2 * 10^41000 nums[i] 100010^7 k 10^7
思路设 i 为数组中的任意位置用 sum[i] 表示 [0, i] 区间内所有元素的和想知道有多少个「以 i 为结尾的和为 k 的子数组」就要找到有多少个起始位置为 x1, x2, x3… 使得 [x, i] 区间内的所有元素的和为 k 那么 [0, x] 区间内的和就是sum[i] - k 了。于是问题就变成
找到在 [0, i - 1] 区间内有多少前缀和等于 sum[i] - k 的即可 代码如下 class Solution {public:int subarraySum(vectorint nums, int k) {int n nums.size();vectorint dp(n 1);unordered_mapint, int hash;// 当整个前缀和等于 k 时相当于找和为 0 的个数所以默认和为 0 的有一个hash[0] 1;int sum 0, ret 0;for(int i 1; i n; i){// 计算当前位置的前缀和dp[i] dp[i - 1] nums[i - 1];// 在 [0, i - 1] 区间内有多少前缀和等于 dp[i] - kif(hash.count(dp[i] - k)) ret hash[dp[i] - k];hash[dp[i]];}return ret;}};6. 和可被K整除的子数组
题目链接 - Leetcode -974.和可被K整除的子数组
Leetcode -974.和可被K整除的子数组
题目给定一个整数数组 nums 和一个整数 k 返回其中元素之和可被 k 整除的连续、非空 子数组 的数目。
子数组 是数组的 连续 部分。
示例 1 输入nums [4, 5, 0, -2, -3, 1], k 5 输出7 解释 有 7 个子数组满足其元素之和可被 k 5 整除 [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
示例 2: 输入: nums [5], k 9 输出 : 0
提示 :
1 nums.length 3 * 10^410^4 nums[i] 10^42 k 10^4
思路
同余定理如果a - b% p 0那么 a % p b % p设 [0, x - 1] 区间内所有元素之和等于 a [0, i] 区间内所有元素的和等于 b 可得(b - a) % k 0
由同余定理可得 [0, x - 1] 区间与 [0, i] 区间内的前缀和同余。于是问题就变成找到在 [0, i - 1] 区间内有多少前缀和的余数等于 dp[i] % k 的即可。
代码如下 class Solution {public:int subarraysDivByK(vectorint nums, int k){int n nums.size();vectorint dp(n 1);unordered_mapint, int hash;hash[0] 1; // 0 这个数的余数int ret 0;for (int i 1; i n; i){// 当前位置的前缀和dp[i] dp[i - 1] nums[i - 1];// 因为 c 中负数对正数取余得到的是负数所以要进行修正修正后的结果int tp (dp[i] % k k) % k; // 相当于是 dp[i] % k// 统计结果// 如果这个余数在前面出现过现在加上 nums[i - 1] 后还是等于这个余数说明这个数可以被 k 整数if (hash.count(tp)) ret hash[tp];hash[tp];}return ret;}};7. 连续数组
题目链接 - Leetcode -525.连续数组
Leetcode -525.连续数组
题目给定一个二进制数组 nums, 找到含有相同数量的 0 和 1 的最长连续子数组并返回该子数组的长度。
示例 1: 输入: nums [0, 1] 输出 : 2 说明 : [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2 : 输入 : nums [0, 1, 0] 输出 : 2 说明 : [0, 1] (或[1, 0]) 是具有相同数量0和1的最长连续子数组。
提示
1 nums.length 10^5nums[i] 不是 0 就是 1
思路设 i 为数组中的任意位置用 sum[i] 表示 [0, i] 区间内所有元素的和。如果将 0 记为 -1 1 记为 1 问题就变成了找出一段区间这段区间的和等于 0. 想知道最大的「以 i 为结尾的和为 0 的⼦数组」就要找到从左往右第⼀个 x1 使得 [x1, i] 区间内的所有元素的和为 0 。 那么 [0, x1 - 1] 区间内的和就是 sum[i] 了。于是问题就变成 找到在 [0, i - 1] 区间内第⼀次出现 sum[i] 的位置即可 我们可以用一个哈希表⼀边求当前位置的前缀和一边记录第一次出现该前缀和的位置。
代码如下 class Solution {public:int findMaxLength(vectorint nums) {int n nums.size();unordered_mapint, int hash;// 默认有一个前缀和为 0 的情况hash[0] -1; int retlen 0, sum 0;for(int i 0; i n; i){// 计算当前位置的前缀和sum nums[i] 0? -1 : 1;if(hash.count(sum)) retlen max(i - hash[sum], retlen);// 存下标else hash[sum] i;}return retlen;}};8. 矩阵区域和
题目链接 - Leetcode -1314.矩阵区域和
Leetcode -1314.矩阵区域和
题目给你一个 m x n 的矩阵 mat 和一个整数 k 请你返回一个矩阵 answer 其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和
i - k r i k, j - k c j k 且 (r, c) 在矩阵内。
示例 1 输入mat [[1, 2, 3], [4, 5, 6], [7, 8, 9]], k 1 输出 [[12, 21, 16], [27, 45, 33], [24, 39, 28]]
示例 2 输入mat [[1, 2, 3], [4, 5, 6], [7, 8, 9]], k 2 输出 [[45, 45, 45], [45, 45, 45], [45, 45, 45]]
提示
m mat.lengthn mat[i].length1 m, n, k 1001 mat[i][j] 100
思路二维前缀和的简单应用题画图写出公式即可
代码如下 class Solution {public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k) {int m mat.size(), n mat[0].size();vectorvectorint dp(m 1, vectorint(n 1));vectorvectorint ret(m, vectorint(n));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] - dp[i - 1][j - 1] mat[i - 1][j - 1];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; }};
