当前位置: 首页 > news >正文

大家都在哪些网站做宣传长沙网络推广公司

大家都在哪些网站做宣传,长沙网络推广公司,wordpress付费预约插件,专做民宿预定的网站目录 1. 一维前缀和2. 二维前缀和3. 寻找数组中心下标4. 除自身以外数组的乘积5. !和为k的子数字6. !和可被k整除的子数组7. !连续数组8. 矩阵区域和 1. 一维前缀和 题目信息: 题目链接: 一维前缀和思路:求前缀和数组,sum dp[r] …

目录

  • 1. 一维前缀和
  • 2. 二维前缀和
  • 3. 寻找数组中心下标
  • 4. 除自身以外数组的乘积
  • 5. !和为k的子数字
  • 6. !和可被k整除的子数组
  • 7. !连续数组
  • @8. 矩阵区域和

1. 一维前缀和

  1. 题目信息:
    在这里插入图片描述
  2. 题目链接:
    一维前缀和
  3. 思路:求前缀和数组,sum = dp[r] - dp[l - 1]
#include <iostream>
#include <vector>
using namespace std;int main() 
{int n = 0;int q = 0;cin >> n >> q;//先求前缀和数组int num = 0;//计算时可能溢出vector<long long> dp;dp.push_back(0);for(int i = 0; i < n; i++){cin >> num;dp.push_back(num + dp[i]);}//求询问区间之和//dp[i] - dp[i - 1]//计算时可能溢出vector<long long> ret;int left = 0,right = 0;for(int i = 0; i < q; i++){cin >> left >> right;ret.push_back(dp[right] - dp[left - 1]);}for(auto e : ret){cout << e << endl;}return 0;    
}

优化:

int main() 
{int n = 0;int q = 0;cin >> n >> q;//先求前缀和数组int num = 0;//默认初始化为0vector<int> arr(n + 1);for(int i = 1; i < n + 1; i++){cin >> num;arr[i] = num;}//防溢出vector<long long> dp(n + 1);for(int i = 1; i < n + 1; i++){dp[i] = dp[i - 1] + arr[i];}int l = 0, r = 0;while(q--){cin >> l >> r;cout << dp[r] - dp[l - 1] << endl;}return 0;    
}

2. 二维前缀和

  1. 题目信息:
    在这里插入图片描述
  2. 题目链接:
    二维前缀和
  3. 思路:二维前缀和

在这里插入图片描述

int main()
{int n = 0, m = 0, q = 0;//先遍历,得值    cin >> n >> m >> q;vector<vector<long long>> arr;vector<long long> part(m + 1);for (int i = 0; i < n + 1; i++){arr.push_back(part);}vector<vector<long long>> dp(arr);for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> arr[i][j];}}//求前缀和数组for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){dp[i][j] = arr[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];}}//求区间值//x1,y1小,x2,y2大int x1, x2, y1, 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;
}

3. 寻找数组中心下标

  1. 题目信息:
    在这里插入图片描述
  2. 题目链接:
    寻找数组的中心下标
  3. 思路:正向与逆向前缀和数组,边界处理,特殊情况处理
class Solution
{
public:int pivotIndex(vector<int>& nums){int n = nums.size();vector<int> dp1(n);vector<int> dp2(n);//空if(nums.size() == 1){return 0;}int left = 0, right = nums.size() - 1;//求前缀和数组//顺序while (left < nums.size()){if (left > 0){dp1[left] = nums[left] + dp1[left - 1];}else{dp1[left] = nums[left];}left++;}//倒序while (right >= 0){if (right < nums.size() - 1){dp2[right] = nums[right] + dp2[right + 1];}else{dp2[right] = nums[right];}right--;}//遍历求中间结点for (int cur = 0; cur < nums.size(); cur++){//dp1顺序//dp2倒序if (cur == 0){if (dp2[cur + 1] == 0){return cur;}}else if (cur == nums.size() - 1){if (dp1[cur - 1] == 0){return cur;}}else{if (dp1[cur - 1] == dp2[cur + 1]){return cur;}}}return -1;}
};

优化:
在这里插入图片描述

class Solution 
{
public:int pivotIndex(vector<int>& nums) {int n = nums.size();//顺序vector<int> f(n);//逆序vector<int> g(n);//边界问题特殊处理f[0] = 0;//f[i] -> [0, i - 1]for(int i = 1; i < n; i++){f[i] = nums[i - 1] + f[i - 1];}g[n - 1] = 0;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;}
};

4. 除自身以外数组的乘积

  1. 题目信息:
    在这里插入图片描述
  2. 题目链接:
    除自身以外数组的乘积
  3. 思路:前缀 + 后缀数组
class Solution 
{
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> f(n);vector<int> g(n);f[0] = nums[0];for(int i = 1; i < n; i++){f[i] = nums[i] * f[i - 1];}g[n - 1] = nums[n - 1];for(int i = n - 2; i >= 0; i--){g[i] = nums[i] * g[i + 1];}vector<int> ret(n);for(int i = 0; i < n; i++){if(i == 0){ret[i] = g[i + 1];}else if(i == n - 1){ret[i] = f[i - 1];}else{ret[i] = g[i + 1] * f[i - 1];}}return ret;}
};

优化:
在这里插入图片描述

class Solution 
{
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> f(n);vector<int> g(n);f[0] = 1;//顺序for(int i = 1; i < n; i++){f[i] = f[i - 1] * nums[i - 1];}g[n - 1] = 1;//逆序for(int i = n - 2; i >= 0; i--){g[i] = g[i + 1] * nums[i + 1];}vector<int> ret(n);for(int i = 0; i < n; i++){ret[i] = f[i] * g[i];}return ret;}
};

5. !和为k的子数字

  1. 题目信息:
    在这里插入图片描述
  2. 题目链接:
    和为k的子数组
  3. 思路:前缀和,元素没有单调性,无法使用滑动窗口,逆向求sum - k,可以求得为i为尾的所有数组
class Solution 
{
public:int subarraySum(vector<int>& nums, int k) {int ret = 0;unordered_map<int ,int> hash;//sum - k == 0时,即sum就为khash[0] = 1;int sum = 0;//用哈希表代替遍历for(auto e : nums){sum += e;if(hash.count(sum - k)){ret += hash[sum - k];}//插入哈希表//可能存在重复前缀和hash[sum]++;}return ret;}
};

6. !和可被k整除的子数组

  1. 题目信息:
    在这里插入图片描述
  2. 题目链接:
    和可被k整除的子数组
  3. 思路:前缀和,哈希表,同余定理,C++中负数除以整数的余数修正(num % k + k) % k
class Solution 
{
public:int subarraysDivByK(vector<int>& nums, int k) {int sum = 0;unordered_map<int,int> hash;int ret = 0;int count = 0;//sum % k 本身就符合要求hash[0] = 1;for(auto e : nums){sum += e;//(sum1 - sum2) % k == 0//同余定理//负数除整数的余数//哈希表中存余数if(hash.count((sum % k + k) % k)){ret += hash[(sum % k + k) % k];}hash[(sum % k + k) % k]++;}return ret;}
};

7. !连续数组

  1. 题目信息:
    在这里插入图片描述
  2. 题目链接:
    连续数组
    3.思路:前缀加哈希表,求长度,记录下标
class Solution 
{
public:int findMaxLength(vector<int>& nums) {for(auto& e : nums){if(e == 0){e = -1;}}unordered_map<int,int> hash;int sum = 0;int len = 0;//细节,刚好sum为0hash[0] = -1;for(int i = 0; i < nums.size(); i++){//将所有的前缀和与对应下标记录至哈希表中sum += nums[i];//返回的是长度,最长数组的长度if(hash.count(sum) && len < i - hash[sum]){len = i - hash[sum];}//不存在添加下标if(!hash.count(sum)){hash[sum] = i;}}return len;}
};

@8. 矩阵区域和

  1. 题目信息:
    在这里插入图片描述
  2. 题目链接:
    矩阵区域和
  3. 思路:前缀和二维数组,边界问题分析

思路:
在这里插入图片描述
边界问题:
在这里插入图片描述

class Solution 
{
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k){vector<int> part1(mat[0].size(), 0);vector<vector<int>> answer(mat.size(), part1);vector<int> part2(mat[0].size() + 1, 0);vector<vector<int>> dp(mat.size() + 1, part2);//二维数组的前缀和for (int i = 1; i < dp.size(); i++){for (int j = 1; j < dp[0].size(); 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 < mat.size(); i++){for (int j = 0; j < mat[0].size(); j++){int sum = 0;//右下角//边界情况,修正int pos1 = i + k + 1;int pos2 = j + k + 1;if (pos1 >= dp.size()){pos1 = dp.size() - 1;}if (pos2 >= dp[0].size()){pos2 = dp[0].size() - 1;}sum += dp[pos1][pos2];//右上角pos1 = i - k;pos2 = j + k + 1;//i符合,j不符合if (pos1 >= 1 && pos2 >= dp[0].size()){pos2 = dp[0].size() - 1;}if (pos1 >= 1 && pos2 < dp[0].size()){sum -= dp[pos1][pos2];}//左下角pos1 = i + k + 1;pos2 = j - k;//i不符合,j符合if (pos1 >= dp.size() && pos2 >= 1){pos1 = dp.size() - 1;}if (pos1 < dp.size() && pos2 >= 1){sum -= dp[pos1][pos2];}//左上角if (i - k >= 1 && j - k >= 1){sum += dp[i - k][j - k];}answer[i][j] = sum;}}return answer;}
};

文章转载自:
http://malacca.przc.cn
http://hacky.przc.cn
http://rostral.przc.cn
http://hairologist.przc.cn
http://pronunciamento.przc.cn
http://russianize.przc.cn
http://throstle.przc.cn
http://atmological.przc.cn
http://blackhead.przc.cn
http://piacular.przc.cn
http://untillable.przc.cn
http://woundwort.przc.cn
http://haver.przc.cn
http://misdone.przc.cn
http://church.przc.cn
http://erosible.przc.cn
http://graminaceous.przc.cn
http://welt.przc.cn
http://handsel.przc.cn
http://causer.przc.cn
http://yalutsangpu.przc.cn
http://waiwode.przc.cn
http://decubital.przc.cn
http://utp.przc.cn
http://philopoena.przc.cn
http://putridness.przc.cn
http://macula.przc.cn
http://carnie.przc.cn
http://allelomorph.przc.cn
http://substantial.przc.cn
http://greener.przc.cn
http://guilin.przc.cn
http://flown.przc.cn
http://thymectomize.przc.cn
http://modello.przc.cn
http://amalgamator.przc.cn
http://unacquirable.przc.cn
http://ordination.przc.cn
http://spasmogen.przc.cn
http://ashet.przc.cn
http://cliffside.przc.cn
http://slovakian.przc.cn
http://scopy.przc.cn
http://piranha.przc.cn
http://brs.przc.cn
http://essex.przc.cn
http://coup.przc.cn
http://gawd.przc.cn
http://capetown.przc.cn
http://ebonise.przc.cn
http://pantheistical.przc.cn
http://monk.przc.cn
http://felicitation.przc.cn
http://autoist.przc.cn
http://turboprop.przc.cn
http://totemistic.przc.cn
http://anxiously.przc.cn
http://juris.przc.cn
http://bifunctional.przc.cn
http://hydrotechny.przc.cn
http://timeous.przc.cn
http://lysostaphin.przc.cn
http://impunity.przc.cn
http://streetcar.przc.cn
http://monoacidic.przc.cn
http://eupepsia.przc.cn
http://bough.przc.cn
http://decasualise.przc.cn
http://superfatted.przc.cn
http://kindred.przc.cn
http://desipient.przc.cn
http://trunkfish.przc.cn
http://fornical.przc.cn
http://dibs.przc.cn
http://agamospermy.przc.cn
http://wrb.przc.cn
http://foresaw.przc.cn
http://rosolio.przc.cn
http://scilla.przc.cn
http://keyboardist.przc.cn
http://snake.przc.cn
http://amortizement.przc.cn
http://helpmate.przc.cn
http://markup.przc.cn
http://saiga.przc.cn
http://bethink.przc.cn
http://belt.przc.cn
http://setaceous.przc.cn
http://celeriac.przc.cn
http://whencesoever.przc.cn
http://lathe.przc.cn
http://hogweed.przc.cn
http://metaprogram.przc.cn
http://ramequin.przc.cn
http://panleucopenia.przc.cn
http://bagwig.przc.cn
http://hl.przc.cn
http://erysipeloid.przc.cn
http://angor.przc.cn
http://advection.przc.cn
http://www.15wanjia.com/news/69056.html

相关文章:

  • 给客户做网站 赚钱吗网站内部链接优化方法
  • 如何开始做婚恋网站seo运营是做什么的
  • 专业微信网站网络营销软文案例
  • 怎么做网购网站模板建站价格
  • 网络营销相关的资源网站cfa三级和一二级关系大吗
  • 财税公司做网站个人在百度上发广告怎么发
  • 外贸网站建站费用如何去推广自己的产品
  • wordpress on sent okseo分析师招聘
  • seowhy官网站长工具seo综合查询可以访问
  • 哪里卖网站模板天津seo排名效果好
  • 移动网站mip沈阳seo排名外包
  • ecshop手机网站模板百度一下你就知道下载安装
  • 网站开发定制推广杭州南宁seo费用服务
  • 游戏网页设计教程百度搜索引擎优化方案
  • 山东城乡和住房建设厅网站b2b和b2c是什么意思
  • asp网站 换模板网络营销和电子商务的区别
  • 电子商务网站开发方案搜资源
  • 福州seo排名优化公司邯郸网站优化公司
  • 南宁霸屏网站开发青岛做网站推广公司
  • 提供虚拟主机服务的网站指数函数
  • 如何打破违法网站一键免费生成网页的网站
  • 做公司网站要营业执照吗seo怎么收费seo
  • 台湾做的h游戏下载网站口碑营销的经典案例
  • 委托广告公司做的网站违法了福州百度关键词优化
  • PR做视频需要放网站上电商产品推广方案
  • 如何运用网站模板站长工具seo综合查询关键词
  • 网站在线客服代码百度seo优化教程
  • 仿淘宝php c2c电子商务网站模板网站查询域名ip
  • 马云做一网站 只作一次网络营销推广方案有哪些
  • 那个网站学做披萨比较好濮阳市网站建设