题目描述
卡车有两个油箱。给你两个整数,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
思路及实现
方式一:模拟法
思路
直接根据题意进行模拟,主油箱 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)。
方式二:数学法
思路
通过数学运算来直接计算出汽车能够行驶的总距离,而不是通过循环来模拟每次消耗油和补充油的过程。这种方法利用了数学关系来简化问题,使得代码更简洁、更高效。
具体思路如下:
- 计算可完整使用的副油箱数量:
(mainTank - 1) / 4
这部分代码计算了在主油箱的油量中,可以完整使用多少个副油箱。因为每消耗5升油才能使用一个副油箱,所以需要减去1来避免在mainTank
小于5时计算错误。例如,如果mainTank
是6,那么(6 - 1) / 4
的结果是1,表示可以完整使用一个副油箱。 - 取实际副油箱数量和可完整使用数量的最小值:
Math.min((mainTank - 1) / 4, additionalTank)
这部分代码确保不会使用超过实际拥有的副油箱数量。例如,如果有3个副油箱但实际上只能完整使用1个,那么这里会取1。 - 计算总油量:
将可完整使用的副油箱数量加到mainTank
上,得到总油量。这是因为每个副油箱可以为主油箱补充1升油。 - 计算总行驶距离:
最后,将总油量乘以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 |
这些题目都涉及到加油或行驶距离的计算,难度从简单到困难不等。其中有些题目要求计算最小的加油次数或最大的行驶距离,有些则需要处理更复杂的情况,如加油站之间的距离、汽车的油耗等。通过解决这些相似题目,可以加深对总行驶距离计算问题的理解,并提升算法设计和分析能力。