力扣题库刷题笔记134-加油站
1、题目如下:
2、个人Python代码实现(当数据量足够大时会超时):
对于第10-11行代码,主要实现的是对于不同下标作为起始加油站时,对于gas和cost重新排序:
对于数组排序还有另一种方式是:
3、基于题解思路的个人Python代码实现
个人的代码逻辑其实没有问题,主要是数据量过大会超时。相较于题解的思路,差异其实在对于数组排序的地方。我的思路是循环找到起始加油站下标,然后将gas和cost重新排序;而题解的思路相同的地方在于找到下标,差异在于他没有进行数组重新排序,直接只从下标往后看,不管下标前的数据。
这里可以再次分析一下代码思路:
a、首先sum(gas) > sum(cost)代表一定有解
b、如果第0个加油站的油小于到第一个加油站的油,那么从第1个加油站作为起始点。这里由于一定有解,所以只需要判断第一个加油站开始,到最后一个加油站油够用就行了,不需要再关心第0个加油站,以此类推。