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

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

目录
打赏
0
0
0
0
24
分享
相关文章
Python入门:2.注释与变量的全面解析
在学习Python编程的过程中,注释和变量是必须掌握的两个基础概念。注释帮助我们理解代码的意图,而变量则是用于存储和操作数据的核心工具。熟练掌握这两者,不仅能提高代码的可读性和维护性,还能为后续学习复杂编程概念打下坚实的基础。
Python入门:2.注释与变量的全面解析
课时7:Java程序基本概念(注释)
课时7介绍了Java程序中的注释。编程语言有其语法和语义,注释有助于理解代码需求,防止断档。Java支持三类注释:单行(//)、多行(/* */)和文档注释(/** */)。注释不会被编译器编译。范例中展示了如何在代码中使用注释,并强调了注释对项目文档管理的重要性。
Java 方法注释:规范、实用和高质量的写法
本文深入探讨了如何编写高质量的 Java 方法注释
112 11
|
5月前
|
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
66 0
|
3月前
|
Java 中的注释
1. 单行注释:// 2. 多行注释:/* */ 3. 文档注释::/** **/
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
💡Java 零基础 | 深入理解注释的重要性与应用
【10月更文挑战第10天】本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
63 5
|
5月前
|
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
56 2
|
6月前
|
Go
go语言注释,标识符 | 17
go语言注释,标识符 | 17
|
5月前
|
【python从入门到精通】-- 第二战:注释和有关量的解释
【python从入门到精通】-- 第二战:注释和有关量的解释
76 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等