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

石英石台面做网单有什么网站b2b免费网站推广平台

石英石台面做网单有什么网站,b2b免费网站推广平台,滨海新区商城网站建设,本地电脑如何做网站上一篇博客算法整理——【贪心算法简述】-CSDN博客,我们介绍了贪心算法的基础知识,现在我们要对此进行进一步练习。 一、跳跃游戏II 例题为45. 跳跃游戏 II - 力扣(LeetCode),给定一个长度为 n 的 0 索引整数数组 nu…

上一篇博客算法整理——【贪心算法简述】-CSDN博客,我们介绍了贪心算法的基础知识,现在我们要对此进行进一步练习。

一、跳跃游戏II

例题为45. 跳跃游戏 II - 力扣(LeetCode),给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]

最理想的情况是每一步尽可能往远跳,这样尽快跳到最后。但是我们不能单纯的取最远的点,因为会存在[2,3,1,1,4]这样的例子,如果在位置0跳到最远位置2,则会需要三步才能到终点。

我们需要引入覆盖范围的思想,覆盖范围是指我们能跳到达的区域都属于覆盖范围,不是具体的某个终点。比如我们可以计算第一次跳跃的覆盖范围、第二次的覆盖范围等等(主要是记录当前步数的覆盖范围的最大值),最终看什么时候终点被包括。基于此,我们现在的贪心思路变成了,每一步尽可能扩大我们的覆盖范围。

代码如下:

class Solution {
public:int jump(vector<int>& nums) {int ret = 0;//记录步数int cur = 0;//记录当前步数最大的覆盖范围int next = 0;//记录下一步可到达的最大覆盖范围if(nums.size() == 1) return 0;for(int i = 0; i<nums.size(); i++){next = max(next, i+nums[i]);if(i == cur){ret++;if(next>=nums.size()-1) return ret;cur = next;}}return ret;}
};

二、加油站

例题为134. 加油站 - 力扣(LeetCode),在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。给定两个整数数组 gas 和 cost ,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1 。如果存在解,则保证它是唯一的。

首先我们可以通过将每点的gas-cost,得到经过该加油站后油量的净增加(或减少)的量dif[i]。如果对所有点的净增加(减少)进行累加,最后结果如果为负,则说明无论从哪一点开始都不能够跑完一圈,此时需要返回-1。如果为正,则需要找到那个起始点。

本题的解题重点为以下的一句思路:我们从0开始累加dif[i],和记为sum,一旦sum小于零,说明i之前的都不能作为起始位置(具体证明可以自己思考)。于是我们需要从i+1开始累加和遍历。本题的局部最优为当前累加dif[i]的和sum一旦小于0,起始位置至少要是i+1。全局最优为找到可以跑一圈的起始位置。

整体代码如下:

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {vector<int> dif(gas.size());int sum = 0;for(int i = 0; i<gas.size(); i++){dif[i] = gas[i]-cost[i];sum+=dif[i];//累计总油量减去总消耗}if(sum<0)//从任何一个点都不可能跑完一圈{return -1;}sum = 0;int ret = 0;for(int i= 0;i<gas.size(); i++){sum+=dif[i];if(sum<0){ret = i+1;sum = 0;   }}return ret;}
};

说明:本文为作者整理知识点用于复习巩固,参考了代码随想录的讲解,有问题可以联系作者欢迎讨论~

http://www.shuangfujiaoyu.com/news/31701.html

相关文章:

  • 网站开发流程包括百度seo软件优化
  • 做网站需要懂什么网络运营推广合作
  • 外贸soho网站制作电商网站怎样优化
  • 事业单位门户网站建设的建议顾问
  • 网站建设运营方案谷歌seo需要做什么的
  • 免费html网站模板国内搜索引擎网站
  • 宇说建筑网站关键词排名监控批量查询
  • 如何在网站上做网页链接宣传软文范例
  • 合肥企业网站建设专家网站多少钱
  • 网站首页设计报价多少大数据分析网站
  • seo自学网windows优化大师官网
  • 如何建立网站教程灰色词快速排名接单
  • 伊犁建设网站公司下载安装
  • 网站分为哪些结构seo搜索优化专员
  • 宁波做百度网站seo排名查询
  • 家用电脑做网站服务器龙岗网站建设公司
  • 个人网站能允许做哪些网络营销环境
  • 通州企业网站建设外贸营销网站制作
  • 福州网站设计服务如何做推广最有效果
  • 广东手机网页制作整站seo外包
  • 做业务员要认识什么批发网站必应搜索引擎国际版
  • 做网站的伪原创怎么弄营销型网站建设流程
  • 给公司建立网站不可以做到的品牌推广的意义
  • 佛山专业网站建设公司百度指数网址是多少
  • 珠海网站建设品牌策划现在网络推广哪家好
  • 企业网站托管技巧宣传渠道有哪些
  • 做推广那个网站比较靠谱西安关键字优化哪家好
  • 百度网站快速收录优化seo厂家
  • 烟台违建举报网站爱站网seo综合查询工具
  • 香港主机做擦边球网站韩国比分预测