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

徐州专业制作网站做网站网站应该注意什么

徐州专业制作网站,做网站网站应该注意什么,seo引擎优化是什么意思,长沙人才招聘网官网目录 689. 三个无重叠子数组的最大和 题目描述#xff1a; 实现代码与解析#xff1a; dp 原理思路#xff1a; 滑动窗口#xff1a; 原理思路#xff1a; 689. 三个无重叠子数组的最大和 题目描述#xff1a; 给你一个整数数组 nums 和一个整数 k #xff0c;找…目录 689. 三个无重叠子数组的最大和 题目描述 实现代码与解析 dp 原理思路 滑动窗口 原理思路 689. 三个无重叠子数组的最大和 题目描述 给你一个整数数组 nums 和一个整数 k 找出三个长度为 k 、互不重叠、且全部数字和3 * k 项最大的子数组并返回这三个子数组。 以下标的数组形式返回结果数组中的每一项分别指示每个子数组的起始位置下标从 0 开始。如果有多个结果返回字典序最小的一个。 示例 1 输入nums [1,2,1,2,6,7,5,1], k 2 输出[0,3,5] 解释子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。 也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。示例 2 输入nums [1,2,1,2,1,2,1,2,1], k 2 输出[0,2,4]提示 1 nums.length 2 * 1041 nums[i]  2161 k floor(nums.length / 3) 实现代码与解析 dp class Solution { public:vectorint maxSumOfThreeSubarrays(vectorint nums, int k) {reverse(nums.begin(), nums.end());int n nums.size();vectorvectorint f(n 1, vectorint(4));// 计算前缀和vectorint s(n 1, 0); // 一般0位置空出来方便处理边界for (int i 1; i n; i) { // s[1] nums[0];s[i] s[i - 1] nums[i - 1]; }// dpfor (int i k; i n; i) {for (int j 1; j 4; j) {f[i][j] max(f[i - k][j - 1] s[i] - s[i - k], f[i - 1][j]);}}vectorint res;int j 3, i n;while (j 0) {if (f[i - 1][j] f[i - k][j - 1] s[i] - s[i - k]) i--;else {res.push_back(n - i);i - k; // 跳到前一个位置j--; }}return res;} }; 原理思路 众所周知dp一般是用来求结果的而不容易输出寻找的过程。 首先求一下前缀和 s。 dp数组含义 与01背包类似遍历到第 i 个数在第 j 次选取 或 不选取 的最大值。一共选3次。 用 i  来代表单个数组最后一个数的下标。 递推公式 f[i][j] max(f[i - k][j - 1] s[i] - s[i - k], f[i - 1][j]); 两种情况i 选取下标 i - k 的数 第 j 次不选取的最大值 此段数组的和。 i 不选取下标 i - 1第 j 次 选取后的最大值继承过来。 两者取一个max。 回溯寻找路径 利用递推公式我们判断每个数是通过max取的哪个值来求出路径。加入到res中。 注意 此题说明如果有多个结果返回字典序最小的一个。 所以我们反转数组或者倒着遍历数组不然会取到字典序大的。 滑动窗口 class Solution { public:vectorint maxSumOfThreeSubarrays(vectorint nums, int k) {vectorint res(3);int sum1 0, maxSum1 0, idx1 0;int sum2 0, maxSum12 0, idx2 0, idx12_1 0, idx12_2 0;int sum3 0, maxSum123 0;for (int i k * 2; i nums.size(); i) {sum1 nums[i - k * 2];sum2 nums[i - k];sum3 nums[i];if (i k * 3 - 1) {if (sum1 maxSum1) {maxSum1 sum1;idx1 i - k * 3 1;}if (maxSum1 sum2 maxSum12) {maxSum12 maxSum1 sum2;idx12_1 idx1;idx12_2 i - k * 2 1;}if (maxSum12 sum3 maxSum123) {maxSum123 maxSum12 sum3;res {idx12_1, idx12_2, i - k 1};}sum1 - nums[i - k * 3 1];sum2 - nums[i - k * 2 1];sum3 - nums[i - k 1];}}return res;} }; 原理思路 这里记录一下我自己的问题。 为什么数组1和数组2为什么有一个idx1idx12_1 因为当数组1的sum为最大时idx1是一个值但是此时数组2与数组1的sum和并不一定是最大的毕竟要考虑数组之间的不重叠影响idx12_1用来记录最大的情况时的idx1而idx12_1要用idx1来赋值所以这就是两个idx的含义不同以及作用的不同。至于为什么数组3没有因为res就是变相的来记录了所以不需要单独再次记录当前想单独写也没问题。
http://mrfarshtey.net/news/75550/

相关文章:

  • awds网站开发留学微信第三方平台开发
  • 网站优化哪个公司好wordpress 添加关键词
  • 可以做ppt的网站或软件免费广告投放网站
  • 学校微网站模板网站建设公司有哪些重要职务
  • 三拼域名做网站长不长青岛网站关键词
  • 如何查网站服务器速度从哪些方面建设网站
  • 网站左侧的导航是怎么做的网站维护外包
  • 网站模板 代码免费网站支付宝接口付费
  • 网站logo图怎么做的企业营销策划方案
  • 丽水城乡建设局网站网站开发流程分为哪几个阶段
  • 泉州网站设计平台教育网站制作视频
  • 网站统计数据网站开发技术主管工作职责
  • ae模板素材网站根据颜色找网站
  • 哪个网站可以做行程攻略河南整合网络营销咨询
  • wordpress+怎么迁移淘宝seo是指什么
  • 福州建设注册中心网站京东联盟需要自己做网站吗
  • 浦项建设内部网站wordpress下载按钮
  • 深圳市住建局网站网站首页动图怎么做
  • 椒江建设网保障性阳光工程网站网站访问过程
  • 中国建设集团门户网站苏州app制作
  • 网站推广的平台网站搭建策略与方法有哪些方面
  • 软件公司网站模版网站排名数据
  • 如何提高网站用户体验岳阳博物馆网站
  • dede视频网站wordpress发布地址
  • 排行榜网站物流公司前十名排行榜
  • 深圳建网站哪家公司好百度网页设计教程
  • 做物流网站的图片素材wordpress取5篇置顶文章
  • 全球访问量最大的网站个人做的网站百度搜索不到
  • 空壳网站数据移动网站设计上机考试
  • 云南网站建设网站运营如何做自己的网站系统