首页 > 其他分享 >LeetCode 134加油站,是环路,但我不绕圈,秒了。

LeetCode 134加油站,是环路,但我不绕圈,秒了。

时间:2024-06-22 16:29:16浏览次数:21  
标签:出发点 int sum gas cost 绕圈 134 LeetCode 总和

不绕圈是指,不需要看能不能转一圈回到起始点,只需要看能不能到达最后一个元素就行。

在做这一道题的时候,如果判断能不能回到出发点,则需要绕一圈再回来,不仅需要创建临时变量,还要频繁使用%n获得余数,非常的不优雅。下面是优化方法:

由题目很容易得出,如果存在解,则必定有gas总和大于或者等于cost总和。而且只要gas总和大于或者等于cost总和就一定有解,因为前面缺少的油,后面一定会多出一部分。

1.如果无解,即gas总和小于cost总和,直接返回-1。

2.如果有解,则进行如下操作:

        从0开始遍历,如果能进入下一个点,则出发站不变;如果不能进入下一站,出发点更新为此时遍历点的下一位。

因为遍历过的这些点都不能作为出发站点。比如出发点为0,无法走到下标为4的点,那么从0-4之间的任何一个点作为出发点,都不可能到达4,因为0经过1-3这些点时会有燃油余量,说明在这个区间,从0出发已经是最好的选择了。

        当i==n的时候,就说明从出发点可以达到最后一个加油站,直接跳出循环。不需要看能不能回到出发点,因为出发点之前的点都不行,出发点又是剩下的这些点里面的最优解,那就只能是他了。

        最后返回出发点的位置p。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int sum_gas = 0;
        for (int i = 0; i < n; i++) {
            sum_gas+=gas[i]-cost[i];
        }
        if (sum_gas < 0) {
            return -1;
        }
        sum_gas = 0;
        int p = 0;
        for (int i = 0; i < n; i++) {
            sum_gas += gas[i];
            if (sum_gas < cost[i]) {
                p = i + 1;
                sum_gas = 0;
            } else {
                sum_gas -= cost[i];
            }
        }
        return p;
    }
};

标签:出发点,int,sum,gas,cost,绕圈,134,LeetCode,总和
From: https://blog.csdn.net/weixin_68169539/article/details/139883023

相关文章

  • LeetCode 2542. 最大子序列的分数(贪心、小顶堆)
    2542.最大子序列的分数思路:先对nums2按降序排列,然后遍历nums2的最小值,同时在区间[0,i]中选中k个最大的nums1即可。然后找出最大的ansclassSolution{public:typedefpair<int,int>PII;longlongmaxScore(vector<int>&nums1,vector<int>&nums2,intk)......
  • LeetCode刷题day3——链表part1
    203.移除链表元素这个题是二刷了一开始这个思路就是利用虚拟头结点,但是中间很多小细节都考虑不到,例如初始化一个新的链表,循环条件的写法等classSolution{public:structListNode{intval;ListNode*next;ListNode(intx):val(x),next(NULL){};//定义构......
  • LeetCode刷题day4——链表part2
    24.两两交换链表中的节点用pre代表第1个节点,cur代表它后面的相邻节点,tmp存储cur->next。但是问题找不到怎么返回新的节点。想着就循环一次,在第一次交换的时候就确认新的头结点。但还存在很多问题,具体如下:classSolution{public:ListNode*swapPairs(ListNode*he......
  • (nice!!!)LeetCode LCP 20. 快速公交(记忆化搜索+小顶堆+贪心)
    LCP20.快速公交思路:逆向记忆化搜索。思考从target到0所花的最小时间。通过哈希表来进行记忆化搜索,避免重复遍历。细节看注释classSolution{public:typedeflonglongLL;typedefpair<LL,LL>PII;constintmod=1e9+7;intbusRapidTransit(int......
  • LeetCode热题100-第2题
    题目:49.字母异位词分组-力扣(LeetCode)给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。示例1:输入:strs=["eat","tea","tan","ate","nat","bat"]输出:[["bat"],["......
  • 【LeetCode】215.数组中的第K个最大元素
    题目描述给定整数数组nums和整数k,请返回数组中第k个最大的元素。请注意,你需要找的是数组排序后的第k个最大的元素,而不是第k个不同的元素。你必须设计并实现时间复杂度为O(n)的算法解决此问题。示例1:输入:[3,2,1,5,6,4],k=2输出:5示例2:输入:[3,2......
  • LeetCode 热题100 --哈希
    哈希哈希,有限空间映射一个无限的空间。在空间内,有序化进行快速查询。用空间换时间。1.两数之和给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数......
  • leetcode 动态规划 (基础版)打家劫舍
    题意:你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ......
  • leetcode 动态规划(基础版)删除并获得点数
    题目:给你一个整数数组  ,你可以对它进行一些操作。nums每次操作中,选择任意一个  ,删除它并获得  的点数。之后,你必须删除 所有 等于  和  的元素。nums[i]nums[i]nums[i]-1nums[i]+1开始你拥有 个点数。返回你能通过这些操作获得的最大点数。0题解:要会理解......
  • leetcode225用队列实现栈
    本文主要讲解用队列实现栈的要点与细节,按照步骤思考更方便理解,同类型用栈实现队列c++与java代码如下,末尾请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。实现 MyStack 类:voidpush(intx) 将元素x压入栈顶。intp......