【经典算法】LeetCode 2739. 总行驶距离(Java/C/Python3/Go实现含注释说明,Easy)

简介: 【经典算法】LeetCode 2739. 总行驶距离(Java/C/Python3/Go实现含注释说明,Easy)

题目描述

卡车有两个油箱。给你两个整数,mainTank 表示主油箱中的燃料(以升为单位)
,additionalTank 表示副油箱中的燃料(以升为单位)。
该卡车每耗费 1 升燃料都可以行驶 10 km。每当主油箱使用了 5 升燃料时,
如果副油箱至少有 1 升燃料,则会将 1 升燃料从副油箱转移到主油箱。
返回卡车可以行驶的最大距离。
注意:从副油箱向主油箱注入燃料不是连续行为。这一事件会在每消耗 5 升燃料时突然且立即发生。
示例 1:
输入:mainTank = 5, additionalTank = 10
输出:60
解释:
在用掉 5 升燃料后,主油箱中燃料还剩下 (5 - 5 + 1) = 1 升,行驶距离为 50km 。
在用掉剩下的 1 升燃料后,没有新的燃料注入到主油箱中,主油箱变为空。
总行驶距离为 60km 。
示例 2:
输入:mainTank = 1, additionalTank = 2
输出:10
解释:
在用掉 1 升燃料后,主油箱变为空。
总行驶距离为 10km 。
提示:
1 <= mainTank, additionalTank <= 100

原题:LeetCode 2739 总行驶距离

思路及实现

方式一:模拟法

思路

直接根据题意进行模拟,主油箱 mainTank 每减少 5 个单位,可以行驶 50 千米,此时如果副油箱 additionalTank 存在燃料,则从副油箱中减少 1 个单位的燃料累加到主油箱 mainTank,直到主油箱 mainTank 的值小于 5 时,则退出循环,最终历程需要累加 10×mainTank,返回最终结果即可。

代码实现

Java版本
class Solution {
    public int distanceTraveled(int mainTank, int additionalTank) {
        int ans = 0;
        //考虑主油箱和副油箱都有的情况
        while (mainTank >= 5) {
            mainTank -= 5;
            ans += 50;
            if (additionalTank > 0) {
                additionalTank--;
                mainTank++;
            }
        }
        //只有主油箱的情况
        return ans + mainTank * 10;
    }
}
C语言版本
int distanceTraveled(int mainTank, int additionalTank){
    int ans = 0;
    while (mainTank >= 5) {
        mainTank -= 5;
        ans += 50;
        if (additionalTank > 0) {
            additionalTank--;
            mainTank++;
        }
    }
    return ans + mainTank * 10;
}

说明:

和java类似

Python3版本
class Solution:
    def distanceTraveled(self, mainTank: int, additionalTank: int) -> int:
        ans = 0
        while mainTank >= 5:
            mainTank -= 5
            ans += 50
            if additionalTank > 0:
                additionalTank -= 1
                mainTank += 1
        return ans + mainTank * 10
Go语言
func distanceTraveled(mainTank int, additionalTank int) int {
    ans := 0
    for mainTank >= 5 {
        mainTank -= 5
        ans += 50
        if additionalTank > 0 {
            additionalTank--
            mainTank++
        }
    }
    return ans + mainTank*10
}

复杂度分析

  • 时间复杂度:O(mainTank),mainTank 即为给定的主油箱中的初始燃料。实际计算时,最多循环计算 mainTank/4 次。
  • 空间复杂度:O(1)。

方式二:数学法

思路

通过数学运算来直接计算出汽车能够行驶的总距离,而不是通过循环来模拟每次消耗油和补充油的过程。这种方法利用了数学关系来简化问题,使得代码更简洁、更高效。

具体思路如下:

  1. 计算可完整使用的副油箱数量
    (mainTank - 1) / 4 这部分代码计算了在主油箱的油量中,可以完整使用多少个副油箱。因为每消耗5升油才能使用一个副油箱,所以需要减去1来避免在mainTank小于5时计算错误。例如,如果mainTank是6,那么(6 - 1) / 4的结果是1,表示可以完整使用一个副油箱。
  2. 取实际副油箱数量和可完整使用数量的最小值
    Math.min((mainTank - 1) / 4, additionalTank) 这部分代码确保不会使用超过实际拥有的副油箱数量。例如,如果有3个副油箱但实际上只能完整使用1个,那么这里会取1。
  3. 计算总油量
    将可完整使用的副油箱数量加到mainTank上,得到总油量。这是因为每个副油箱可以为主油箱补充1升油。
  4. 计算总行驶距离
    最后,将总油量乘以10(因为每升油能行驶10公里),得到汽车能够行驶的总距离。

这种方法避免了显式的循环,直接通过数学表达式得出了结果。它假设了每消耗5升油(包括副油箱补充的油)汽车可以行驶50公里,每升油可以行驶10公里。这种假设简化了计算过程,使得代码更加紧凑。

代码实现

Java版本
class Solution {  
  
    /**  
     * 计算汽车能够行驶的总距离  
     *   
     * @param mainTank 主油箱中的油量(单位:升)  
     * @param additionalTank 副油箱中的油量(单位:个,每个副油箱能补充1升油)  
     * @return 汽车能够行驶的总距离(单位:公里)  
     */  
    public int distanceTraveled(int mainTank, int additionalTank) {  
          
        // 使用数学表达式计算总距离  
        // 10 * (mainTank + Math.min((mainTank - 1) / 4, additionalTank))  
        // 首先,计算副油箱能为主油箱补充的油量  
        // (mainTank - 1) / 4 表示在消耗完所有5升一组的油后,剩余油量能组成的完整5升组的数量  
        // 减去1是为了避免在mainTank小于5时产生非0值  
        // Math.min确保不会使用超过actual additionalTank数量的副油箱  
        // 然后,将这个补充的油量加到mainTank上  
        // 最后,乘以10得到总距离(因为每升油能行驶10公里)  
  
        return 10 * (mainTank + Math.min((mainTank - 1) / 4, additionalTank));  
  
    }  
  
}

说明:

C语言版本
int distanceTraveled(int mainTank, int additionalTank){
    return 10 * (mainTank + fmin((mainTank - 1) / 4, additionalTank));
}

说明

同java

Python3版本
class Solution:
    def distanceTraveled(self, mainTank: int, additionalTank: int) -> int:
        return 10 * (mainTank + min((mainTank - 1) // 4, additionalTank))

说明: 同java

Go版本
func distanceTraveled(mainTank int, additionalTank int) int {
    return 10 * (mainTank + min((mainTank-1)/4, additionalTank))
}

说明: 同java

复杂度分析

  • 时间复杂度:O(1)。
  • 空间复杂度:O(1)。

总结

方法 优点 缺点 时间复杂度 空间复杂度 其他
模拟法 直观易懂 可能存在冗余计算 O(mainTank) O(1) 适合油量较少时,计算步骤明确
数学法 简洁高效 需要一定的数学分析能力 O(1) O(1) 适用于大规模计算,直接得出结果

模拟法通过循环来模拟汽车行驶和补充油的过程,直观易懂,但可能存在冗余计算,特别是在主油箱油量较大时。其时间复杂度与主油箱的油量成正比,空间复杂度为常数。

数学法通过数学表达式直接计算出总行驶距离,避免了循环,代码简洁高效。但需要一定的数学分析能力来理解表达式的含义。其时间复杂度和空间复杂度均为常数。

相似题目

相似题目 难度 链接
加油站 中等 leetcode-63
加油站(进阶版) 困难 leetcode-134
加油站与目的地 中等 leetcode-1464
最小加油次数 困难 leetcode-871
加油站的汽车 中等 lintcode-582

这些题目都涉及到加油或行驶距离的计算,难度从简单到困难不等。其中有些题目要求计算最小的加油次数或最大的行驶距离,有些则需要处理更复杂的情况,如加油站之间的距离、汽车的油耗等。通过解决这些相似题目,可以加深对总行驶距离计算问题的理解,并提升算法设计和分析能力。

相关文章
|
2月前
|
算法 搜索推荐 JavaScript
基于python智能推荐算法的全屋定制系统
本研究聚焦基于智能推荐算法的全屋定制平台网站设计,旨在解决消费者在个性化定制中面临的选择难题。通过整合Django、Vue、Python与MySQL等技术,构建集家装设计、材料推荐、家具搭配于一体的一站式智能服务平台,提升用户体验与行业数字化水平。
|
2月前
|
存储 人工智能 算法
从零掌握贪心算法Java版:LeetCode 10题实战解析(上)
在算法世界里,有一种思想如同生活中的"见好就收"——每次做出当前看来最优的选择,寄希望于通过局部最优达成全局最优。这种思想就是贪心算法,它以其简洁高效的特点,成为解决最优问题的利器。今天我们就来系统学习贪心算法的核心思想,并通过10道LeetCode经典题目实战演练,带你掌握这种"步步为营"的解题思维。
|
2月前
|
存储 监控 算法
监控电脑屏幕的帧数据检索 Python 语言算法
针对监控电脑屏幕场景,本文提出基于哈希表的帧数据高效检索方案。利用时间戳作键,实现O(1)级查询与去重,结合链式地址法支持多条件检索,并通过Python实现插入、查询、删除操作。测试表明,相较传统列表,检索速度提升80%以上,存储减少15%,具备高实时性与可扩展性,适用于大规模屏幕监控系统。
142 5
|
3月前
|
存储 算法 调度
【复现】【遗传算法】考虑储能和可再生能源消纳责任制的售电公司购售电策略(Python代码实现)
【复现】【遗传算法】考虑储能和可再生能源消纳责任制的售电公司购售电策略(Python代码实现)
204 26
|
3月前
|
机器学习/深度学习 算法 机器人
【机器人路径规划】基于D*算法的机器人路径规划(Python代码实现)
【机器人路径规划】基于D*算法的机器人路径规划(Python代码实现)
219 0
|
3月前
|
机器学习/深度学习 算法 机器人
【机器人路径规划】基于改进型A*算法的机器人路径规划(Python代码实现)
【机器人路径规划】基于改进型A*算法的机器人路径规划(Python代码实现)
261 0
|
3月前
|
机器学习/深度学习 编解码 算法
【机器人路径规划】基于迪杰斯特拉算法(Dijkstra)的机器人路径规划(Python代码实现)
【机器人路径规划】基于迪杰斯特拉算法(Dijkstra)的机器人路径规划(Python代码实现)
378 4
|
3月前
|
机器学习/深度学习 算法 机器人
【机器人路径规划】基于A*算法的机器人路径规划研究(Python代码实现)
【机器人路径规划】基于A*算法的机器人路径规划研究(Python代码实现)
539 4
|
3月前
|
机器学习/深度学习 算法 机器人
【机器人路径规划】基于深度优先搜索(Depth-First-Search,DFS)算法的机器人路径规划(Python代码实现)
【机器人路径规划】基于深度优先搜索(Depth-First-Search,DFS)算法的机器人路径规划(Python代码实现)
269 3
|
3月前
|
算法 机器人 定位技术
【机器人路径规划】基于流场寻路算法(Flow Field Pathfinding)的机器人路径规划(Python代码实现)
【机器人路径规划】基于流场寻路算法(Flow Field Pathfinding)的机器人路径规划(Python代码实现)
197 4

热门文章

最新文章

推荐镜像

更多