COMP9517 Week 4 Pattern Recognition Part 1

问题传送门：https://leetcode.cn/problems/gas-station/description/



常规思路是暴力解法，以每一个点作为起点检索，在路上如果某一个点的油箱容量为负，说明到不了， 直接break到下一个点，直到所有的点都被遍历过。**思路是没问题，就是会超时。**

```C++
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int length = gas.size();
        vector<int> result(length, 0);
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                int index = (i + j) % length;
                result[i] += gas[index] - cost[index];
                if (result[i] < 0) {
                    break;
                }
            }
            if (result[i] >= 0) {
                return i;
            }
        }
        return -1;
    }
};
```

换一种思维方式：

- 相关变量：`total_tank`。如果从0到n点，它所有的油箱总所得，和所有的油箱总支出的差值是负数，那么说明油量不能够支持完成环形遍历，需要返回-1。如果为正数，则一定存在符合条件的点。题目另外也规定了**该点只有一个**。
- 相关变量：`curr_tank`。这个值用于模拟当前油箱的剩余油量，当它小于0的时候，说明当前的点无法到达。
- 相关变量：`start_station`。这个值用于记录当前的起点，并与`i`进行运行模拟。

算法思想是：
1. 初始化各个值，将起点设定为0.
2. `total_tank`记录总的油量数据。
3. `curr_tank`用于记录从`start_station`到`i`的过程中，油箱油量的变化。如果它变为负数，则证明：从`start_station`到`i-1`中的这个区间内的任意一点，都不能到达点`i`。
> 原因很简单：从`start_station`到它的下一站，是有可能有大于0的余油的；但是如果从`start_station+1`开始往`i`走，那么起始油量一定是0。有余油都跑不到`i`，更别提从0开始了。所以中间的所有点会被直接忽略掉。
4. 再次将起始点`start_station`记录为`i+1`，并将`curr_tank`置空，以重新模拟。
5. 最终判定，如果`total_tank`不为负数，说明存在点能够完成，并且最后一定是`start_station`符合条件。如果为负数，返回`-1`。

```C++
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total_tank = 0;
        int curr_tank = 0;
        int start_station = 0;
        
        for (int i = 0; i < gas.size(); i++) {
            total_tank += gas[i] - cost[i];
            curr_tank += gas[i] - cost[i];
            if (curr_tank < 0) {
                // Set Next Station as Start
                // Reset tank info
                start_station = i + 1;
                curr_tank = 0;
            }
        }
        
        return total_tank >= 0 ? start_station : -1;
    }
};
```

Leetcode 134. 加油站

COMP9517 Week 3 Feature Representation Part 2

COMP9517 Week 3 Feature Representation Part 1

COMP9517 Week 2 Image Processing Part 1

script

首页

分类

时间线

关于