首页 > 代码库 > LeetCode---Gas Station
LeetCode---Gas Station
明知道明早要考试,可还是忍不住打开电脑想水一题。不过还是在这题上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 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。