如何seo网站挣钱,舆情分析的主要方法,南京网站建设优化,百度免费域名前缀和 一.一维前缀和(模板)#xff1a;1.思路一#xff1a;暴力解法2.思路二#xff1a;前缀和思路 二. 二维前缀和(模板)#xff1a;1.思路一#xff1a;构造前缀和数组 三.寻找数组的中心下标#xff1a;1.思路一#xff1a;前缀和 四.除自身以外数组的乘积#xff… 前缀和 一.一维前缀和(模板)1.思路一暴力解法2.思路二前缀和思路 二. 二维前缀和(模板)1.思路一构造前缀和数组 三.寻找数组的中心下标1.思路一前缀和 四.除自身以外数组的乘积1.思路一暴力解法2.思路二前缀积后缀积 五.和为K的子数组1.思路一前缀和哈希 六.前缀和可以被K整除的子数组1.思路一前缀和哈希 七.连续数组1.思路一 八.矩阵区域和1.思路一二维前缀和模板细节处理 一.一维前缀和(模板) 一维前缀和
1.思路一暴力解法 1.输入数组长度n和查询次数q。 2.使用一个一维数组保存数据。 3.使用一个循环获取q次需要查询范围的数据。 4.遍历r-l1次进行一个范围求和然后输出。 5.时间复杂度O(n^2) 6.通过不了所有的测试用例。 2.思路二前缀和思路 1.输入数组长度n和查询次数q。 2.使用一个一维数组保存数据。 3.构建一个前缀和的一个数组。 4.使用一个循环获取q次需要查询范围的数据。 5.时间复杂度O(n^2) 6.通过不了所有的测试用例。 #include iostream
#include vector
using namespace std;int main()
{//1.输入数组长度和查询次数 int n 0,q0;cinnq;//2.输入数组数据vectorint arr(n1);for(int i1;in;i) cinarr[i];//3.前缀和数组vectorlong long bp(n1);for(int i1;in;i) bp[i] bp[i-1] arr[i];//4.计算和int i0,r0;while(q!0){cinir;cout(bp[r] - bp[i-1])endl;q--;}
}二. 二维前缀和(模板) 二维前缀和
1.思路一构造前缀和数组 #include iostream
#include vector
using namespace std;int main()
{//1.n行m列的一个二维数组int n 0, m 0, q 0;cin n m q;//2.数组输入数据vectorvectorint vv((n 1),vectorint(m1));for (int i 1; i n; i){for (int j 1; j m; j)cin vv[i][j];}//3.创造二维的求和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][j - 1] dp[i - 1][j]) - dp[i-1][j-1]) vv[i][j];}}//4.数据查询while (q ! 0){int x1 0, y1 0, x2 0, y2 0;cin x1 y1 x2 y2;cout (dp[x2][y2] - (dp[x1 - 1][y2] dp[x2][y1-1]) dp[x1-1][y1-1]) endl;q--;}}三.寻找数组的中心下标 寻找数组的中心下标
1.思路一前缀和 class Solution {
public:int pivotIndex(vectorint nums) {//1.构建前缀和数组int n nums.size();vectorint dp(n1);//2.前缀和数组值遍历for(int i 1 ; in;i) dp[i] dp[i-1] nums[i-1];//3.进行中心下标的寻找int mid -1;for(int i1 ; i n ; i){if((dp[i-1] - dp[0]) (dp[n] - dp[i])){mid i-1;break;}}//4.没有中心下标的情况return (mid -1? -1:mid);}
};四.除自身以外数组的乘积 除自身以外数组的乘积
1.思路一暴力解法 2.思路二前缀积后缀积 class Solution {
public:vectorint productExceptSelf(vectorint nums) {//1.前缀积后缀积int n nums.size();vectorint left(n 1, 1);vectorint right(n 1, 1);//2.遍历确定前缀积后缀积的值for (int i 1; i n; i) left[i] left[i - 1] * nums[i - 1];for (int i n - 1; i 0; i--) right[i] right[i 1] * nums[i];// 1 1 2 6 24// 24 24 12 4 1// 0 1 2 3 4//0 1 2 3//24 12 8 6vectorint ret(n);//3.遍历ret数组并且赋值for (int i 0; i n; i){ret[i] left[i] * right[i1];}return ret;}
};五.和为K的子数组 和为K的子数组
1.思路一前缀和哈希 class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint,int hash;hash[0]1;int sum 0 , ret 0;for(auto n : nums){sumn;if(hash.count(sum-k)) rethash[sum-k];hash[sum];}return ret;}
};六.前缀和可以被K整除的子数组 前缀和可以被K整除的子数组
1.思路一前缀和哈希 class Solution {
public:int subarraysDivByK(vectorint nums, int k) {unordered_mapint,int hash;hash[0] 1;//1.开始遍历判断int sum 0 , ret 0;for(auto a : nums){suma;int n (sum%k k) % k;if(hash.count(n)) rethash[n];hash[n];}return ret;}
};七.连续数组 连续数组
1.思路一 class Solution {
public:int findMaxLength(vectorint nums) {vectorint nums_1(nums);for(auto n:nums_1){if(n0) n -1;}//2.hash前缀和的思路unordered_mapint,int hash;//1.前缀和为0的下标处理hash[0] -1;int sum 0,ret 0;for(int i0;inums.size();i){sumnums_1[i];if(hash.count(sum)) ret max(ret , i - hash[sum]);else hash[sum] i;}return ret;}
};八.矩阵区域和 矩阵区域和
1.思路一二维前缀和模板细节处理 class Solution {
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k) {int m mat.size();int n mat[0].size();//1.创建(m1) * (n1) 大小的二维数组vectorvectorint dp(m1 , vectorint(n1));//2.dp数组赋值for(int i1 ; im ; i){for(int j1 ; jn ; j){dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] mat[i-1][j-1];}}//3.使用dp数组并且考虑i-k 和 j-k的越界问题vectorvectorint ret(m,vectorint(n));for(int i0 ; im ; i){for(int j0 ; jn ; 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;}
};
