LeetCode加油站(贪心算法/暴力,分析其时间和空间复杂度)


题目描述

 一.原本暴力算法

最初的想法是:先比较gas数组和cost数组的大小,找到可以作为起始点的站点(因为如果你起始点的油还不能到达下一个站点,就不能作为起始点)。当找到过后,再去依次顺序跑一圈,如果剩余的油为负数,再去寻找下一个满足条件的起始站点。

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int index = -1; //定义初始起点int left = 0; //定义剩余油量bool flag = false;int n = gas.size();//寻找起始位置for(int i = 0;i<n;i++){if(gas[i] < cost[i]) {continue;}else{index = i; int j = index;int count = 0;cout<<"index="<<index<<endl;while(true){j = j%n;cout<<"j="<<j<<endl;if(left < 0) {left = 0;break;}if(count == n){flag = true;return index;}left = left + gas[j] - cost[j];cout<<"left="<<left<<endl;count++;j++;}   }}//判断if(flag){return index;}else{return -1;}}
};

但是代码最后超时了!!

时间复杂度是O(N^2) 因为循环遍历寻找起始站点,找到过后再去循环遍历走一圈是O(N^2)的时间复杂度!

巧妙思路算法二能通过的

转子大佬的代码。

  • 情况一:如果gas的总和小于cost总和,那么无论从哪里出发,一定是跑不了一圈的

  • 情况二:rest[i] = gas[i]-cost[i]为一天剩下的油,i从0开始计算累加到最后一站,如果累加没有出现负数,说明从0出发,油就没有断过,那么0就是起点。

  • 情况三:如果累加的最小值是负数,汽车就要从非0节点出发,从后向前,看哪个节点能把这个负数填平,能把这个负数填平的节点就是出发节点。

  • class Solution {
    public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int min = INT_MAX; // 从起点出发,油箱里的油量最小值for (int i = 0; i < gas.size(); i++) {int rest = gas[i] - cost[i];curSum += rest;if (curSum < min) {min = curSum;}}if (curSum < 0) return -1;  // 情况1if (min >= 0) return 0;     // 情况2// 情况3for (int i = gas.size() - 1; i >= 0; i--) {int rest = gas[i] - cost[i];min += rest;if (min >= 0) {return i;}}return -1;}
    };

    在这里时间复杂度O(N)

  • 空间复杂度O(1)没有开辟新的空间

二.贪心算法

每个加油站的剩余量rest[i]为gas[i] - cost[i]。

i从0开始累加rest[i],和记为curSum,一旦curSum小于零,说明[0, i]区间都不能作为起始位置,因为这个区间选择任何一个位置作为起点,到i这里都会断油,那么起始位置从i+1算起,再从0计算curSum。

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int totalSum = 0;int start = 0;for (int i = 0; i < gas.size(); i++) {curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (curSum < 0) {   // 当前累加rest[i]和 curSum一旦小于0start = i + 1;  // 起始位置更新为i+1curSum = 0;     // curSum从0开始}}if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了return start;}
};

时间复杂度O(N) 

转载于代码随想录,大佬的算法

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/377216.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【代码随想录】【算法训练营】【第64天】 [卡码117]软件构建 [卡码47]参加科学大会

前言 思路及算法思维&#xff0c;指路 代码随想录。 题目来自 卡码网。 day 64&#xff0c;周三&#xff0c;继续ding~ 题目详情 [卡码117] 软件构建 题目描述 卡码117 软件构建 解题思路 前提&#xff1a; 思路&#xff1a; 重点&#xff1a; 代码实现 C语言 [卡码…

GO channel 学习

引言 单纯地将函数并发执行是没有意义的。函数与函数间需要交换数据才能体现并发执行函数的意义。 虽然可以使用共享内存进行数据交换&#xff0c;但是共享内存在不同的goroutine中容易发生竞态问题。为了保证数据交换的正确性&#xff0c;必须使用互斥量对内存进行加锁&#…

喰星云·数字化餐饮服务系统 多处 SQL注入漏洞复现

0x01 产品简介 喰星云数字化餐饮服务系统是一款专为餐饮企业设计的综合性管理软件,旨在通过信息化手段提升餐饮企业的运营效率、降低运营成本,并实现数据驱动的决策管理。该系统包括供应链管理、财务管理、巡店管理、人力资源管理等多个模块,可全面覆盖餐饮企业的日常运营需…

[RoarCTF2019]polyre

参考博客 buu-[RoarCTF2019]polyre&#xff08;控制流平坦化&#xff0c;虚假控制流程&#xff09;-CSDN博客 [RoarCTF2019]Polyre | bypass ollvm - 暖暖草果 - 博客园 (cnblogs.com) buu-[RoarCTF2019]polyre&#xff08;控制流平坦化&#xff0c;虚假控制流程&#xff09…

Java 设计模式系列:外观模式

简介 外观模式&#xff08;Facade Pattern&#xff09;是一种设计模式&#xff0c;又名门面模式&#xff0c;是一种通过为多个复杂的子系统提供一个一致的接口&#xff0c;而使这些子系统更加容易被访问的模式。该模式对外有一个统一接口&#xff0c;外部应用程序不用关心内部…

VUE_TypeError: Cannot convert a BigInt value to a number at Math.pow 解决方法

错误信息 TypeError: Cannot convert a BigInt value to a number at Math.pow vue 或 react package.json添加 "browserslist": {"production": ["chrome > 67","edge > 79","firefox > 68","opera >…

树的结构(b,b+树)

无论线性表&#xff0c;栈还是队列&#xff0c;都是一对一&#xff0c;查询的时候&#xff0c;效率较低&#xff0c;数据量比较的大的情况 1.树的定义 一种数据结构&#xff0c;有层次关系的集合&#xff0c;根朝上&#xff0c;叶朝下 除了根节点外&#xff0c;每个子节点都…

【自动驾驶汽车通讯协议】UART通信详解:理解串行数据传输的基石

文章目录 0. 前言1. 同步通讯与异步通讯1.1 同步通信1.2 异步通信 2. UART的数据格式3. 工作原理3.1 波特率和比特率3.2 UART的关键特性 4. UART在自动驾驶汽车中的典型应用4.1 UART特性4.2应用示例 5. 结语 0. 前言 按照国际惯例&#xff0c;首先声明&#xff1a;本文只是我自…

【周末闲谈】Stable Diffusion会魔法的绘画师

个人主页&#xff1a;【&#x1f60a;个人主页】 系列专栏&#xff1a;【❤️Python】 文章目录 前言Stable Diffusion介绍 使用ComfyUI 和 WebUIComfyUIWebUI 配置需求 Stable Diffusion资源分享吐司AiAUTOMATIC1111Civitai绘世整合包Nenly同学stability.ai 前言 在很早之前&…

香橙派AIpro部署YOLOv5:探索强悍开发板的高效目标检测能力

香橙派AIpro部署YOLOv5&#xff1a;探索强悍开发板的高效目标检测能力 一、香橙派AIpro开箱使用体验 1.1香橙派AIpro开箱 拿到板子后第一件事情就是开箱&#xff1a; 开箱后可以看见一个橘子的标识&#xff0c;也就是香橙派了&#xff0c;并且还有四个大字&#xff1a;为AI…

取消文字默认选中效果

点击的时候会选中文字 .user-select-none {user-select: none;}<div class"model user-select-none" onclick"createRipple(event)">Click me for ripple effect outside </div>点击再快也不会选中了

【C++】——类和对象(上)

文章目录 什么是类和对象类的定义类的访问限定符及其封装类的作用域类的实例化类的对象的大小计算this指针 什么是类和对象 类是一个用户定义的类型&#xff0c;它封装了数据&#xff08;称为属性或成员变量&#xff09;和操作这些数据的方法&#xff08;称为成员函数或方法&a…

Seven layers of the metaverse

看到一篇关于元宇宙的文章&#xff0c;分享给大家&#xff0c;供大家参考。 随着物理世界和数字世界的融合&#xff0c;元宇宙正在推动我们数字能力的新边界。从人类身份、个性和声誉到资产、情感和历史&#xff0c;元宇宙的虚拟现实中可以以全新的方式进行交互、控制和体验。因…

OpenGL笔记十之Shader类的封装

OpenGL笔记十之Shader类的封装 —— 2024-07-10 晚上 bilibili赵新政老师的教程看后笔记 code review! 文章目录 OpenGL笔记十之Shader类的封装1.运行2.目录结构3.main.cpp4.application4.1.CMakeLists.txt4.2.Application.h4.3.Application.cpp 5.assets5.1.shaders&#xf…

【吊打面试官系列-ZooKeeper面试题】简述 Zookeeper 文件系统?

大家好&#xff0c;我是锋哥。今天分享关于 【简述 Zookeeper 文件系统?】面试题&#xff0c;希望对大家有帮助&#xff1b; 简述 Zookeeper 文件系统? Zookeeper 提供一个多层级的节点命名空间&#xff08;节点称为 znode&#xff09;。与文件系统不同的是&#xff0c;这些节…

prometheus+grafana应用监控配置

配置Prometheus 官方地址&#xff1a;Download | Prometheus &#xff08;wegt下载压缩包&#xff0c;解压并重命名prometheus&#xff0c;文件放于/data/prometheus即可&#xff09; 配置 service方法(文件放于 /etc/systemd/system/prometheus.service)&#xff1a; [Unit…

博物馆地图导航系统:高精度地图引擎与AR/VR融合,实现博物馆数字化转型

在人民日益追求精神文化的时代下&#xff0c;博物馆作为传承与展示人类文明的璀璨殿堂&#xff0c;其重要性不言而喻。然而&#xff0c;随着博物馆规模的不断扩大和藏品种类的日益丰富&#xff0c;游客在享受知识盛宴的同时&#xff0c;也面临着“迷路”与“错过”的困扰。博物…

【CUDA】CUDA中缓存机制对计时的影响

笔者在阅读知乎上一个关于CUDA编程的专栏时&#xff0c;发现作者写的很多文章中都会附带计时的模块用于评估程序的运行效率&#xff0c;然而笔者发现&#xff0c;在运行这篇文章中的代码时时&#xff0c;得到的结果和作者的结果有较大差异&#xff0c;主要体现在&#xff1a;使…

前端调试技巧(npm Link,vscode调试,浏览器调试等)

Npm Link 功能&#xff1a; 在本地开发npm模块的时候&#xff0c;我们可以使用npm link命令&#xff0c;将npm 模块链接到对应的运行项目中去&#xff0c;方便地对模块进行调试和测试 断点调试 vscode调试 Debug Vue2 Project 目标&#xff1a;在VSCode中调试项目代码…

巧用 VScode 网页版 IDE 搭建个人笔记知识库!

[ 知识是人生的灯塔&#xff0c;只有不断学习&#xff0c;才能照亮前行的道路 ] 巧用 VScode 网页版 IDE 搭建个人笔记知识库! 描述&#xff1a;最近自己在腾讯云轻量云服务器中部署了一个使用在线 VScode 搭建部署的个人Markdown在线笔记&#xff0c;考虑到在线 VScode 支持终…