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

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

相关文章
|
12天前
|
机器学习/深度学习 人工智能 算法
基于Python深度学习的眼疾识别系统实现~人工智能+卷积网络算法
眼疾识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了4种常见的眼疾图像数据集(白内障、糖尿病性视网膜病变、青光眼和正常眼睛) 再使用通过搭建的算法模型对数据集进行训练得到一个识别精度较高的模型,然后保存为为本地h5格式文件。最后使用Django框架搭建了一个Web网页平台可视化操作界面,实现用户上传一张眼疾图片识别其名称。
61 4
基于Python深度学习的眼疾识别系统实现~人工智能+卷积网络算法
|
1月前
|
机器学习/深度学习 人工智能 算法
猫狗宠物识别系统Python+TensorFlow+人工智能+深度学习+卷积网络算法
宠物识别系统使用Python和TensorFlow搭建卷积神经网络,基于37种常见猫狗数据集训练高精度模型,并保存为h5格式。通过Django框架搭建Web平台,用户上传宠物图片即可识别其名称,提供便捷的宠物识别服务。
283 55
|
22天前
|
存储 缓存 监控
局域网屏幕监控系统中的Python数据结构与算法实现
局域网屏幕监控系统用于实时捕获和监控局域网内多台设备的屏幕内容。本文介绍了一种基于Python双端队列(Deque)实现的滑动窗口数据缓存机制,以处理连续的屏幕帧数据流。通过固定长度的窗口,高效增删数据,确保低延迟显示和存储。该算法适用于数据压缩、异常检测等场景,保证系统在高负载下稳定运行。 本文转载自:https://www.vipshare.com
117 66
|
2月前
|
搜索推荐 Python
利用Python内置函数实现的冒泡排序算法
在上述代码中,`bubble_sort` 函数接受一个列表 `arr` 作为输入。通过两层循环,外层循环控制排序的轮数,内层循环用于比较相邻的元素并进行交换。如果前一个元素大于后一个元素,就将它们交换位置。
147 67
|
2月前
|
存储 搜索推荐 Python
用 Python 实现快速排序算法。
快速排序的平均时间复杂度为$O(nlogn)$,空间复杂度为$O(logn)$。它在大多数情况下表现良好,但在某些特殊情况下可能会退化为最坏情况,时间复杂度为$O(n^2)$。你可以根据实际需求对代码进行调整和修改,或者尝试使用其他优化策略来提高快速排序的性能
139 61
|
2月前
|
算法 数据安全/隐私保护 开发者
马特赛特旋转算法:Python的随机模块背后的力量
马特赛特旋转算法是Python `random`模块的核心,由松本真和西村拓士于1997年提出。它基于线性反馈移位寄存器,具有超长周期和高维均匀性,适用于模拟、密码学等领域。Python中通过设置种子值初始化状态数组,经状态更新和输出提取生成随机数,代码简单高效。
129 63
|
1月前
|
机器学习/深度学习 人工智能 算法
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
宠物识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了37种常见的猫狗宠物种类数据集【'阿比西尼亚猫(Abyssinian)', '孟加拉猫(Bengal)', '暹罗猫(Birman)', '孟买猫(Bombay)', '英国短毛猫(British Shorthair)', '埃及猫(Egyptian Mau)', '缅因猫(Maine Coon)', '波斯猫(Persian)', '布偶猫(Ragdoll)', '俄罗斯蓝猫(Russian Blue)', '暹罗猫(Siamese)', '斯芬克斯猫(Sphynx)', '美国斗牛犬
188 29
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
|
19天前
|
算法 安全 Go
Go 语言中实现 RSA 加解密、签名验证算法
随着互联网的发展,安全需求日益增长。非对称加密算法RSA成为密码学中的重要代表。本文介绍如何使用Go语言和[forgoer/openssl](https://github.com/forgoer/openssl)库简化RSA加解密操作,包括秘钥生成、加解密及签名验证。该库还支持AES、DES等常用算法,安装简便,代码示例清晰易懂。
53 12
|
19天前
|
算法 网络协议 Python
探秘Win11共享文件夹之Python网络通信算法实现
本文探讨了Win11共享文件夹背后的网络通信算法,重点介绍基于TCP的文件传输机制,并提供Python代码示例。Win11共享文件夹利用SMB协议实现局域网内的文件共享,通过TCP协议确保文件传输的完整性和可靠性。服务器端监听客户端连接请求,接收文件请求并分块发送文件内容;客户端则连接服务器、接收数据并保存为本地文件。文中通过Python代码详细展示了这一过程,帮助读者理解并优化文件共享系统。
|
24天前
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
50 5

热门文章

最新文章