【经典算法】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

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

相关文章
|
21小时前
|
算法 数据中心 Python
基于python雪花算法工具类Snowflake-来自chatGPT
基于python雪花算法工具类Snowflake-来自chatGPT
11 4
|
1天前
|
机器学习/深度学习 算法 搜索推荐
Python常用算法详细解释
Python常用算法详细解释
12 0
|
1天前
|
存储 缓存 算法
Python中常用的数据结构与算法优化技巧指南
Python是一种强大而灵活的编程语言,它提供了丰富的数据结构和算法库,但是在处理大规模数据或者需要高效运行的情况下,需要考虑一些优化技巧。本文将介绍一些Python中常用的数据结构与算法优化技巧,并附带代码实例,帮助你更好地理解和运用。
|
1天前
|
机器学习/深度学习 算法 数据挖掘
Python机器学习10大经典算法的讲解和示例
为了展示10个经典的机器学习算法的最简例子,我将为每个算法编写一个小的示例代码。这些算法将包括线性回归、逻辑回归、K-最近邻(KNN)、支持向量机(SVM)、决策树、随机森林、朴素贝叶斯、K-均值聚类、主成分分析(PCA)、和梯度提升(Gradient Boosting)。我将使用常见的机器学习库,如 scikit-learn,numpy 和 pandas 来实现这些算法。
|
2天前
|
存储 机器学习/深度学习 算法
Python算法基础教程
Python算法基础教程
|
3天前
|
机器学习/深度学习 人工智能 算法
海洋生物识别系统+图像识别+Python+人工智能课设+深度学习+卷积神经网络算法+TensorFlow
海洋生物识别系统。以Python作为主要编程语言,通过TensorFlow搭建ResNet50卷积神经网络算法,通过对22种常见的海洋生物('蛤蜊', '珊瑚', '螃蟹', '海豚', '鳗鱼', '水母', '龙虾', '海蛞蝓', '章鱼', '水獭', '企鹅', '河豚', '魔鬼鱼', '海胆', '海马', '海豹', '鲨鱼', '虾', '鱿鱼', '海星', '海龟', '鲸鱼')数据集进行训练,得到一个识别精度较高的模型文件,然后使用Django开发一个Web网页平台操作界面,实现用户上传一张海洋生物图片识别其名称。
79 7
海洋生物识别系统+图像识别+Python+人工智能课设+深度学习+卷积神经网络算法+TensorFlow
|
4天前
|
机器学习/深度学习 人工智能 算法
【昆虫识别系统】图像识别Python+卷积神经网络算法+人工智能+深度学习+机器学习+TensorFlow+ResNet50
昆虫识别系统,使用Python作为主要开发语言。通过TensorFlow搭建ResNet50卷积神经网络算法(CNN)模型。通过对10种常见的昆虫图片数据集('蜜蜂', '甲虫', '蝴蝶', '蝉', '蜻蜓', '蚱蜢', '蛾', '蝎子', '蜗牛', '蜘蛛')进行训练,得到一个识别精度较高的H5格式模型文件,然后使用Django搭建Web网页端可视化操作界面,实现用户上传一张昆虫图片识别其名称。
107 7
【昆虫识别系统】图像识别Python+卷积神经网络算法+人工智能+深度学习+机器学习+TensorFlow+ResNet50
|
4天前
|
机器学习/深度学习 人工智能 算法
【球类识别系统】图像识别Python+卷积神经网络算法+人工智能+深度学习+TensorFlow
球类识别系统,本系统使用Python作为主要编程语言,基于TensorFlow搭建ResNet50卷积神经网络算法模型,通过收集 '美式足球', '棒球', '篮球', '台球', '保龄球', '板球', '足球', '高尔夫球', '曲棍球', '冰球', '橄榄球', '羽毛球', '乒乓球', '网球', '排球'等15种常见的球类图像作为数据集,然后进行训练,最终得到一个识别精度较高的模型文件。再使用Django开发Web网页端可视化界面平台,实现用户上传一张球类图片识别其名称。
95 7
【球类识别系统】图像识别Python+卷积神经网络算法+人工智能+深度学习+TensorFlow
|
6天前
|
存储 算法 Shell
python常用算法(5)——树,二叉树与AVL树(三)
python常用算法(5)——树,二叉树与AVL树
|
6天前
|
算法 Python
python常用算法(5)——树,二叉树与AVL树(二)
python常用算法(5)——树,二叉树与AVL树