厦门市建设局网站摇号,elegant wordpress,谈谈你对网络营销的认识,如何免费网络营销推广目录
一维前缀和#xff08;原题链接#xff09;
二维前缀和#xff08;原题链接#xff09;
寻找数组的中心下标#xff08;原题链接#xff09;
除自身以外数组的乘积#xff08;原题链接#xff09;
和为 K 的子数组#xff08;原题链接#xff09;
和可被 …目录
一维前缀和原题链接
二维前缀和原题链接
寻找数组的中心下标原题链接
除自身以外数组的乘积原题链接
和为 K 的子数组原题链接
和可被 K 整除的子数组原题链接
连续数组原题链接
矩阵区域和原题链接 一维前缀和原题链接
描述 给定一个长度为n的数组a1,a2,....ana1,a2,....an. 接下来有q次查询, 每次查询有两个参数l, r. 对于每个询问, 请输出 输入描述 第一行包含两个整数n和q. 第二行包含n个整数, 表示a1,a2,....ana1,a2,....an. 接下来q行,每行包含两个整数 l和r. 输出描述 输出q行,每行代表一次查询的结果. 解题思路 读取输入读取数组的长度 n 和查询的次数 q接着读取数组的元素。前缀和计算 创建一个 dp 数组其中 dp[i] 存储从数组的起始位置到第 i 个元素的和。通过前缀和数组 dp可以快速计算任意子区间 [l, r] 的和。处理查询 对于每个查询 (l, r)利用前缀和数组 dp 来计算区间和 dp[r] - dp[l-1]并输出结果。 步骤说明 输入处理 使用 cin 读取输入的数组大小 n 和查询次数 q。读取数组的元素并存储到 arr 中。 计算前缀和 初始化前缀和数组 dp。使用一个循环来填充 dp 数组其中 dp[i] 是从数组的开始到第 i 个元素的累积和。 查询处理 读取每个查询的区间 [l, r]。计算并输出区间 [l, r] 的和这通过前缀和数组 dp 来实现。 具体代码 #include iostream
#include vectorusing namespace std;int main()
{int n, q;cin n q; // 读取数组的大小 n 和查询的数量 qvectorint arr(n 1); // 创建一个大小为 n 1 的数组索引从 1 开始for(int i 1; i n; i)cin arr[i]; // 读取数组元素vectorlong long dp(n 1); // 创建前缀和数组 dp大小为 n 1for(int i 1; i n; i)dp[i] dp[i-1] arr[i]; // 计算前缀和dp[i] 是从 arr[1] 到 arr[i] 的累积和int l, r;while(q--) // 对于每个查询{cin l r; // 读取查询的区间 [l, r]// 计算并输出区间 [l, r] 的和cout dp[r] - dp[l - 1] endl; }return 0;
} 二维前缀和原题链接
描述 给你一个 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分别代表这次查询的参数 输出描述 输出q行每行表示查询结果。 解题思路 输入处理 读取二维数组的行数 n、列数 m 和查询的次数 q。读取二维数组的数据并存储到 arr 中。 前缀和计算 创建一个二维前缀和数组 dp用来存储从 (1, 1) 到 (i, j) 的矩阵和。计算 dp 数组的值通过动态规划公式进行填充dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] arr[i][j] 这个公式用于去除重复计算的区域并包含当前元素 arr[i][j]。 查询处理 对于每个查询 (x1, y1, x2, y2)使用前缀和数组 dp 快速计算子矩阵的和dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] dp[x1-1][y1-1] 其中dp[x2][y2] 是从 (1, 1) 到 (x2, y2) 的矩阵和减去 dp[x1-1][y2] 和 dp[x2][y1-1]再加上 dp[x1-1][y1-1] 修正重叠区域。 步骤说明 取输入数据 读取 n、m 和 q。读取二维数组的元素到 arr 中。 计算二维前缀和 初始化 dp 数组为零。通过嵌套循环填充 dp 数组使用动态规划公式来计算前缀和。 处理查询并输出结果 对每个查询 (x1, y1, x2, y2)利用前缀和数组 dp 计算子矩阵的和并输出结果。 具体代码 #include iostream
#include vector
using namespace std;int main()
{int n 0, m 0, q 0;cin n m q; // 读取矩阵的行数 n、列数 m 和查询的数量 q// 创建并填充二维数组 arr索引从 1 开始vectorvectorint arr(n 1, vectorint(m 1));for(int i 1; i n; i)for(int j 1; j m; j)cin arr[i][j]; // 读取矩阵元素// 创建并计算二维前缀和数组 dpvectorvectorlong 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]; // 计算前缀和int x1 0, y1 0, x2 0, y2 0;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;
}寻找数组的中心下标原题链接
给你一个整数数组 nums 请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端那么左侧数之和视为 0 因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标应该返回 最靠近左边 的那一个。如果数组不存在中心下标返回 -1 。 解题思路 定义前缀和和后缀和 使用两个数组 f 和 g分别存储当前索引 i 左侧和右侧元素的和。f[i] 代表从数组开头到索引 i-1 的和即索引 i 之前的所有元素的和。g[i] 代表从索引 i1 到数组末尾的和即索引 i 之后的所有元素的和。 计算前缀和和后缀和 从左到右计算前缀和 f。从右到左计算后缀和 g。 查找枢轴索引 遍历数组如果 f[i] 等于 g[i]则 i 是一个枢轴索引返回 i。如果没有找到合适的索引返回 -1。 步骤说明 初始化和计算前缀和 f 遍历数组从索引 1 开始到数组的最后一个元素逐步累加前面的元素和。 初始化和计算后缀和 g 从数组的倒数第二个元素开始逐步累加后面的元素和。 查找满足条件的索引 遍历整个数组如果某个索引 i 的前缀和 f[i] 等于后缀和 g[i]返回 i。 返回结果 如果没有找到符合条件的索引返回 -1。 具体代码 class Solution
{
public:int pivotIndex(vectorint nums) {int n nums.size();vectorint f(n, 0), g(n, 0);// 计算前缀和 ffor(int i 1; i n; i)f[i] f[i - 1] nums[i - 1];// 计算后缀和 gfor(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;}
};除自身以外数组的乘积原题链接
给你一个整数数组 nums返回 数组 answer 其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法且在 O(n) 时间复杂度内完成此题。 解题思路 定义前缀积和后缀积 lprod[i] 表示数组 nums 中从起始位置到索引 i-1 的所有元素的乘积前缀积。rprod[i] 表示数组 nums 中从索引 i1 到末尾的所有元素的乘积后缀积。 计算前缀积 从左到右遍历数组计算每个位置 i 左侧所有元素的乘积并存储在 lprod[i] 中。 计算后缀积 从右到左遍历数组计算每个位置 i 右侧所有元素的乘积并存储在 rprod[i] 中。 计算结果数组 对于每个位置 i结果数组 ret[i] 是 lprod[i] 和 rprod[i] 的乘积表示去掉 nums[i] 后的所有元素的乘积。 步骤说明 初始化 lprod 和 rprod 数组的大小都为 n 1。lprod[0] 初始化为 1因为没有元素在位置 0 的左边。rprod[n-1] 初始化为 1因为没有元素在位置 n-1 的右边。 计算前缀积 遍历数组从位置 1 开始逐步计算前缀积并填充 lprod。 计算后缀积 遍历数组从位置 n-2 开始逐步计算后缀积并填充 rprod。 生成结果数组 遍历数组将每个位置的 ret[i] 计算为 lprod[i] * rprod[i]。 具体代码 class Solution
{
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();// lprod 表示 [0, i - 1] 区间内所有元素的乘积// rprod 表示 [i 1, n - 1] 区间内所有元素的乘积vectorint lprod(n, 1), rprod(n, 1); // 不需要 n 1 的大小// 计算前缀积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];// 生成结果数组vectorint ret(n);for (int i 0; i n; i)ret[i] lprod[i] * rprod[i];return ret;}
};和为 K 的子数组原题链接
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。 解题思路 前缀和 使用前缀和来表示从数组开始到当前位置的和。对于每个位置 i计算到当前位置的前缀和 sum。 哈希表记录前缀和的出现次数 使用一个哈希表 hash 来记录前缀和及其出现的次数。hash[sum] 代表前缀和 sum 出现的次数。 查找目标和 对于当前位置的前缀和 sum检查 sum - k 是否在哈希表中存在。如果存在则表示存在子数组和为 k将 hash[sum - k] 加到结果 ret 中hash[sum - k] 表示到当前位置的子数组个数。 更新哈希表 每次更新当前前缀和 sum 在哈希表中的计数。 步骤说明 初始化 创建一个哈希表 hash并将 hash[0] 初始化为 1。这个设置是为了处理前缀和等于 k 的情况。 计算前缀和并查找目标和 遍历数组累加前缀和 sum。如果 sum - k 在哈希表中存在则结果 ret 增加 hash[sum - k]表示找到的符合条件的子数组的个数。 更新哈希表 将当前前缀和 sum 的计数增加。 具体代码 class Solution
{
public:int subarraySum(vectorint nums, int k) {unordered_mapint, int hash; // 统计前缀和出现的次数hash[0] 1; // 处理前缀和等于 k 的情况int sum 0, ret 0;for (auto x : nums) {sum x; // 计算当前位置的前缀和// 检查 sum - k 是否在哈希表中if (hash.count(sum - k))ret hash[sum - k]; // 如果存在累加结果// 更新哈希表hash[sum];}return ret;}
};和可被 K 整除的子数组原题链接
给定一个整数数组 nums 和一个整数 k 返回其中元素之和可被 k 整除的非空 子数组 的数目。
子数组 是数组中 连续 的部分。 解题思路 前缀和 计算从数组起始到当前位置的前缀和 sum。对于每个位置 i前缀和 sum 是从数组开始到位置 i 的所有元素之和。 余数计算 对于每个前缀和 sum计算它模 k 的余数 r。由于余数可能是负数因此需要进行调整使余数始终是非负的。计算公式为 (sum % k k) % k。 哈希表记录余数出现次数 使用一个哈希表 hash 来记录每个余数出现的次数。如果当前余数 r 已经在哈希表中出现过那么存在以之前某个位置为结束的子数组和能被 k 整除。累加 hash[r] 到结果 ret。 更新哈希表 每次更新当前余数 r 的计数。 步骤说明 初始化哈希表 hash[0 % k] 1这个设置是为了处理从数组开头到当前位置的和能被 k 整除的子数组。初始值为 1 表示前缀和为 0即不包括任何元素的情况。 计算前缀和和余数 遍历数组对每个元素 x 更新前缀和 sum。计算当前前缀和 sum 的模 k 的余数 r并调整为非负值。 查找和更新哈希表 如果余数 r 存在于哈希表中将其出现次数 hash[r] 加到结果 ret。更新哈希表中余数 r 的计数。 具体代码 class Solution
{
public:int subarraysDivByK(vectorint nums, int k) {unordered_mapint, int hash;hash[0 % k] 1; // 初始余数 0 的出现次数为 1int sum 0, ret 0;for (auto x : nums) {sum x; // 计算当前位置的前缀和int r (sum % k k) % k; // 修正后的余数// 如果该余数曾出现过则累加结果if (hash.count(r))ret hash[r];// 更新当前余数的计数hash[r];}return ret;}
}; 连续数组原题链接
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组并返回该子数组的长度。 解题思路 前缀和的概念 计算当前前缀和将数组中的 0 视为 -1将 1 视为 1。这样如果一个子数组中的 0 和 1 的数量相等那么该子数组的前缀和在开始和结束的位置是相同的。 使用哈希表记录前缀和的第一次出现位置 使用哈希表 hash 来记录每个前缀和首次出现的位置。如果前缀和已经出现过则表示从之前出现位置到当前的位置形成的子数组是 0 和 1 数量相等的子数组。计算这个子数组的长度并更新最大长度 ret。 处理前缀和为 0 的特殊情况 初始化哈希表时将 hash[0] 设置为 -1。这是为了处理从数组开头到当前索引的子数组前缀和为 0 的情况。 步骤说明 初始化哈希表 hash[0] -1这个设置表示前缀和为 0 的情况发生在虚拟的数组起点之前的位置 -1。 计算前缀和并查找 遍历数组对每个元素 nums[i]将其转化为 1如果是 1或者 -1如果是 0并累加到 sum 中。使用哈希表检查当前前缀和 sum 是否已出现过。如果出现过计算当前子数组的长度并更新最大长度 ret。如果当前前缀和 sum 未出现过将其位置 i 存储到哈希表中。 具体代码 class Solution
{
public:int findMaxLength(vectorint nums) {unordered_mapint, int hash;hash[0] -1; // 默认前缀和为 0 的情况int sum 0, ret 0;for (int i 0; i nums.size(); i) {// 将 0 转换为 -11 保持不变计算前缀和sum nums[i] 0 ? -1 : 1;// 如果当前前缀和 sum 已出现计算当前子数组长度if (hash.count(sum))ret max(ret, i - hash[sum]);else// 记录当前前缀和的第一次出现位置hash[sum] i;}return ret;}
};矩阵区域和原题链接
给你一个 m x n 的矩阵 mat 和一个整数 k 请你返回一个矩阵 answer 其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和 解题思路 前缀和矩阵 构建一个前缀和矩阵 dp使得 dp[i][j] 表示从矩阵的左上角到位置 (i-1, j-1) 的所有元素的和。前缀和的公式是dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] mat[i-1][j-1]。 计算每个位置的 k x k 子矩阵的和 对于每个位置 (i, j)计算以该位置为中心的 k x k 子矩阵的和。确定子矩阵的边界上边界 x1、左边界 y1、下边界 x2 和右边界 y2。使用前缀和矩阵 dp 来计算子矩阵的和 sumdp[x2][y2]−dp[x1−1][y2]−dp[x2][y1−1]dp[x1−1][y1−1]\text{sum} dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] dp[x1 - 1][y1 - 1]sumdp[x2][y2]−dp[x1−1][y2]−dp[x2][y1−1]dp[x1−1][y1−1]处理边界条件以确保索引不越界。 步骤说明 构建前缀和矩阵 遍历矩阵 mat使用前缀和的公式计算 dp 矩阵。 计算每个位置的 k x k 子矩阵的和 对于每个位置 (i, j)计算子矩阵的边界并通过前缀和矩阵 dp 计算和。 具体代码 class Solution
{
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k) {int m mat.size(), n mat[0].size();vectorvectorint dp(m 1, vectorint(n 1));// 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] - dp[i - 1][j - 1] mat[i - 1][j - 1];// 2. 使用前缀和矩阵计算每个位置的 k x k 子矩阵的和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;}
};
