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

招聘网站上怎么做推广百度网盘搜索引擎

招聘网站上怎么做推广,百度网盘搜索引擎,web旅游网页设计,wordpress响应时间长✨✨✨学习的道路很枯燥,希望我们能并肩走下来! 文章目录 目录 文章目录 前言 一. 前缀和算法的介绍 二、前缀和例题 2.1 【模版】前缀和 2.2 【模板】二维前缀和 2.3 寻找数组的中间下标 2.4 除自身以外数组的乘积 2.5 和为k的子数组 2.6 和可被k整除的子数组 2.7 …

✨✨✨学习的道路很枯燥,希望我们能并肩走下来!

文章目录

目录

文章目录

前言

一. 前缀和算法的介绍

二、前缀和例题

2.1 【模版】前缀和

2.2 【模板】二维前缀和

 2.3 寻找数组的中间下标

 2.4 除自身以外数组的乘积

 2.5 和为k的子数组

2.6 和可被k整除的子数组

 2.7 连续数组

 2.8 矩阵区域和

总结


前言

本篇详细介绍了前缀和算法的使用,让使用者了解前缀和,而不是仅仅停留在表面, 文章可能出现错误,如有请在评论区指正,让我们一起交流,共同进步!


一. 前缀和算法的介绍

前缀和算法是一种用空间换时间的算法,他常常用于解决某些题目或者作为某些高级算法的组成部分。

例如:让你求某个矩阵(一维)的子矩阵的最大值,如果使用暴力解法它的时间复杂度将会是O(n^2) ,但如果使用该算法就可以使其时间复杂度降低一个维度也就是O(N).

前缀和 是从 nums 数组中的第 0 位置开始累加,到第 𝑖位置的累加结果,我们常把这个结果保存到数组 Sum 中,记为 Sum[i]。 

前缀和算法的本质是一个简单动态规划

 接下来我们使用一些例题来介绍一下

二、前缀和例题

2.1 【模版】前缀和

牛客网—【模版】前缀和

 

#include <iostream>
#include<vector>
using namespace std;int main() {//1.读入数据int n ,q;cin>>n>>q;vector<int> arr(n+1);for(int i = 1;i<=n;i++) cin>>arr[i];//2. 预处理出来个前缀和数组vector<long long> dp(n+1); //防止溢出for(int i = 1;i<=n;i++) dp[i] = dp[i-1]+arr[i];//3.使用前缀和数组int l = 0, r = 0;while(q--){cin>>l>>r;cout<<dp[r]-dp[l-1]<<endl;}return 0;}

2.2 【模板】二维前缀和

牛客网—【模版】二维前缀和

 

#include <iostream>
#include <vector>
using namespace std;int main() {int n,m,q;cin>>n>>m>>q;vector<vector<int>> arr(n+1,vector<int>(m+1));for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){cin>>arr[i][j];}}vector<vector<long long>> dp(n+1,vector<long 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] + arr[i][j] - dp[i-1][j-1];}}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;
}

 2.3 寻找数组的中间下标

724. 寻找数组的中心下标 - 力扣(LeetCode) 

 

class Solution {
public:int pivotIndex(vector<int>& nums) {int n = nums.size();vector<int> f(n), g(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];//2. 使用for(int i = 0;i<n;i++)if(f[i] == g[i]) return i;return -1;}
};

 2.4 除自身以外数组的乘积

238. 除自身以外数组的乘积 - 力扣(LeetCode) 

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();//细节处理vector<int> f(n,1), g(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];//使用vector<int> ret(n);for(int i = 0;i<n;i++)ret[i] = f[i] * g[i];return ret;}
};

 2.5 和为k的子数组

560. 和为 K 的子数组 - 力扣(LeetCode)

 

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> hash; //统计前缀和出现的次数hash[0] = 1;int sum = 0, ret = 0;for(auto&x : nums){sum+=x; //计算当前位置的前缀和if(hash.count(sum-k)) ret+=hash[sum-k]; //统计个数hash[sum]++;}return ret;}
};

2.6 和可被k整除的子数组

974. 和可被 K 整除的子数组 - 力扣(LeetCode) 

 

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0 % k] = 1; //0 这个数的余数int sum = 0, ret = 0;for(auto& x : nums){sum+=x; //算出当前位置的前缀和if(hash.count((sum%k+k)%k)) ret+=hash[(sum%k+k)%k]; //修正后的余数+统计结果hash[(sum%k+k)%k]++;}return ret;}
};

 2.7 连续数组

525. 连续数组 - 力扣(LeetCode) 

 

class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int,int> hash;hash[0] = -1; //默认有一个前缀和为0的情况int sum = 0, ret = 0;for(int i = 0;i<nums.size();i++){sum+=nums[i] == 0 ? -1 : 1; //计算当前位置的前缀和if(hash.count(sum)) ret = max(ret,i - hash[sum]);else hash[sum] = i;}return ret;}
};

 2.8 矩阵区域和

1314. 矩阵区域和 - 力扣(LeetCode)

 

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m = mat.size(), n = mat[0].size();vector<vector<int>> dp(m+1,vector<int>(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] - dp[i-1][j-1] + mat[i-1][j-1];vector<vector<int>> answer(m,vector<int>(n));for(int i = 0;i<m;i++)for(int j = 0;j<n;j++){int x1 = max(0,i-k)+1;int y1 = max(0,j-k)+1;int x2 = min(m-1,i+k)+1;int y2 = min(n-1,j+k)+1;answer[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];}return answer;}
};

总结

✨✨✨各位读友,本篇分享到内容是否更好的让你理解前缀和算法,如果对你有帮助给个👍赞鼓励一下吧!!
🎉🎉🎉世上没有绝望的处境,只有对处境绝望的人。
感谢每一位一起走到这的伙伴,我们可以一起交流进步!!!一起加油吧!!

http://www.qdjiajiao.com/news/5677.html

相关文章:

  • 织梦门户网站源码下载google搜索引擎下载
  • 石排镇专业建站公司百度 营销怎么收费
  • 做投票的网站赚钱嘛北京网站推广公司
  • 做网站是什么鬼郑州seo推广外包
  • 四方坪网站建设网站关键词推广
  • 常州网站推广优化百度惠生活怎么优化排名
  • 从化区住房和建设局网站百度指数怎么算
  • Python用数据库做网站灰色关键词排名
  • WordPress禁用自适应专业seo站长工具
  • 搞钱的路子网站本地广告推广平台哪个好
  • 手机如何做api网站网络营销的实现方式包括
  • 网站流量报告2022最新新闻
  • 网站建设需要会什么软件有哪些内容今日要闻
  • 池州做网站上海百度推广公司排名
  • 深圳网站制作有名 乐云践新郑州网络营销公司排名
  • 工程认证网站的建设长沙网站制作费用
  • 沈阳做网站哪家公司好站长统计软件
  • 怎么进入别人网站服务器web 目录网站优化排名金苹果系统
  • 怎样卸载微信wordpress上海关键词seo
  • 河北省住房和城乡建设厅的网站seo基础知识包括什么
  • 智联招聘网站怎么做微招聘信息吗明星百度指数在线查询
  • 如何将网站变成免费全能优化大师
  • 网站开发毕设论文百度网盘电脑网页版
  • wordpress 前端编辑器重庆seo排名扣费
  • 网站建设可以学吗最好用的搜索神器
  • 一个好网站建设西安seo优化公司
  • 做网站的大型公司949公社招聘信息
  • 石家庄网站建设咨询快照网站
  • 宽带办理什么套餐最划算如何进行搜索引擎优化?
  • 做网站销售会遇到哪些问题seo网站优化培训公司