首页 > 代码库 > LeetCode---Gas Station

LeetCode---Gas Station

2024-07-02 18:14:01   226人阅读

明知道明早要考试，可还是忍不住打开电脑想水一题。不过还是在这题上WA了好几次....看见自己有多渣！

有个道理发现了很久，直到今天才意识到它的严重性，反复的做题只能让你不断的巩固已有的知识，而对于

新知识的探索是少只又少，所以必须要通过多读书来获取新的知识，这样才能够扩充知识面。而之前的我就

是忽略了读书，我的想法是：也许通过做题会发现一些新的东西呢！ 但事实证明，此举效率极低。

以此警示自己：多读书！

 

本题为贪心思想。

附上代码：

 1 class Solution {
 2 public:
 3     int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
 4         // length of vector
 5         unsigned int n = gas.size();
 6         // sum[i] keeps the value of 0...i
 7         vector<int> tmp((n<<1) + 5);
 8         
 9         for (unsigned int i = 0; i < n; i++) {
10             tmp[i] = tmp[i+n] = (gas[i] - cost[i]);
11         }
12         for (unsigned int i = 1; i < (n<<1); i++) {
13             tmp[i] += tmp[i-1];
14         }
15 
16         // cnt: count the continous number of tmp[i] where tmp[i] >= 0
17         // beg: the begining index of the cnt continous numbers
18         int cnt = 0, beg = 0;
19         for (unsigned int i = 0; i < (n<<1); i++) {
20             // pay attention... f keeps the value of tmp[beg-1]
21             int f = beg == 0 ? 0 : tmp[beg-1];
22             if (tmp[i] - f >= 0) {
23                 if (cnt == 0) {
24                     beg = i;
25                 }
26                 cnt++;
27             } else {
28                 cnt = 0;
29                 beg = i + 1;
30             }
31             if (cnt >= n) {
32                 return beg;
33             }
34         }
35         return -1;
36     }
37 };

 


联系
我们