首页 > 其他分享 >leetcode 加油站——一次遍历

leetcode 加油站——一次遍历

时间:2023-09-17 15:55:49浏览次数:41  
标签:遍历 records int gas rest 加油站 cost leetcode

 

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n=len(gas)
        max_gas=0
        rest=0
        records=[]
        start=0
        for i in range(n):
            tmp=gas[i]-cost[i]
            records.append(tmp)
        if sum(records)<0:
            return -1
        for i in range(n):
            if rest>=0:
                rest=rest+records[i]
            #1、从非负处,才能开始出发。
            #2、若从x到y,不能到达,则从x,到y,中间出发也不能达到y。
            #当总gas>总cost,一次遍历可找出出发点。
            if rest<0:
                start=i+1
                rest=0
        if rest>=0:
            return start
        return -1
            

  

标签:遍历,records,int,gas,rest,加油站,cost,leetcode
From: https://www.cnblogs.com/tanyuanqing/p/17708921.html

相关文章

  • 【LeetCode】删除数对后的最小数组长度
    题目给你一个下标从0开始的非递减整数数组nums。你可以执行以下操作任意次:选择两个下标i和j,满足i<j且nums[i]<nums[j]。将nums中下标在i和j处的元素删除。剩余元素按照原来的顺序组成新的数组,下标也重新从0开始编号。请你返回一个整数,表示执行......
  • leetcode 二叉树的最小深度
    给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明:叶子节点是指没有子节点的节点。示例1:输入:root=[3,9,20,null,null,15,7]输出:2示例2:输入:root=[2,null,3,null,4,null,5,null,6]输出:5解题思路如果当前节点为null,返......
  • leetcode 平衡二叉树
    给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。示例1:输入:root=[3,9,20,null,null,15,7]输出:true示例2:输入:root=[1,2,2,3,3,null,null,4,4]输出:false示例3:输入:root......
  • 多叉树应用 包括构建 dfs遍历
    力扣17.电话号码的字母组合给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下(与电话按键相同)。注意1不对应任何字母。示例1:输入:digits="23"输出:["ad","ae","af","bd","be","bf","cd","ce&quo......
  • [LeetCode] 1222. Queens That Can Attack the King
    Ona 0-indexed 8x8 chessboard,therecanbemultipleblackqueensadonewhiteking.Youaregivena2Dintegerarray queens where queens[i]=[xQueeni,yQueeni] representsthepositionofthe ith blackqueenonthechessboard.Youarealsogivena......
  • #yyds干货盘点# LeetCode程序员面试金典:2 的幂
    题目:给你一个整数 n,请你判断该整数是否是2的幂次方。如果是,返回 true ;否则,返回 false 。如果存在一个整数 x 使得 n==2x ,则认为 n 是2的幂次方。 示例1:输入:n=1输出:true解释:20=1示例2:输入:n=16输出:true解释:24=16示例3:输入:n=3输出:false示例4:输入......
  • #yyds干货盘点# LeetCode程序员面试金典:强密码检验器
    1.简述:满足以下条件的密码被认为是强密码:由至少 6 个,至多 20 个字符组成。包含至少 一个小写 字母,至少 一个大写 字母,和至少 一个数字 。不包含连续三个重复字符(比如 "Baaabb0" 是弱密码,但是 "Baaba0" 是强密码)。给你一个字符串 password ,返回 将 password......
  • LeetCode-Java题解 209. Minimum Size Subarray Sum
    题目地址:209.MinimumSizeSubarraySum解题思路:    看到这道题,心里本身是有双指针这个概念的,但是不知道怎么用,脑子里第一反应就是暴力解法,双for一把梭,然后时间就超时了...看了题解才知道滑动窗口这个解法,不禁直呼妙啊!感觉和双指针非常类似,其核心点在于避免了暴力算法的枚......
  • leetcode1466
    分析:它是有n个节点,n-1条边所以两个节点连接的边只有一条,那么要么是可以从这条边的起点开始能够到达0,要么是不能,不会有回路的情况对于数据结构使用哈希表值为vector容器intbfs(vector<vector<int>>&connections){unordered_map<int,vector<int>>m;for(auto&v:co......
  • 二叉树的遍历
    总结深度优先与广度优先的区别1、区别1)二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列。2)深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深度优先遍历比较特殊,可以......