由于博客更新不及时，现全都放在GiuHub

134. 加油站

题解：https://leetcode-cn.com/u/mctw/

有一个环形路上有n个站点； 每个站点都有一个好人或一个坏人； 好人会给你钱，坏人会收你一定的过路费，如果你带的钱不够付过路费，坏人会跳起来把你砍死； 问：从哪个站点出发，能绕一圈活着回到出发点?

首先考虑一种情况：如果全部好人给你 的钱加起来 小于 坏人收的过路费之和，那么总有一次你的钱不够付过路费，你的结局注定会被砍死。

假如你随机选一点 start 出发，那么你肯定会选一个有好人的站点开始，因为开始的时候你没有钱，遇到坏人只能被砍死；

现在你在start出发，走到了某个站点end，被end站点的坏人砍死了，说明你在 [start, end) 存的钱不够付 end点坏人的过路费，因为start站点是个好人，所以在 (start, end) 里任何一点出发，你存的钱会比现在还少，还是会被end站点的坏人砍死；

于是你重新读档，聪明的选择从 end+1点出发，继续你悲壮的征程； 终于有一天，你发现自己走到了尽头（下标是n-1)的站点而没有被砍死； 此时你犹豫了一下，那我继续往前走，身上的钱够不够你继续走到出发点Start?

当然可以，因为开始已经判断过，好人给你的钱数是大于等于坏人要的过路费的，你现在攒的钱完全可以应付 [0, start) 这一段坏人向你收的过路费。 这时候你的嘴角微微上扬，眼眶微微湿润，因为你已经知道这个世界的终极奥秘：Start就是这个问题的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>

using namespace std;


class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        vector<int> r(gas.size());
        int total = 0;
        for (int i = 0; i < gas.size(); i++) {
            r[i]=gas[i]-cost[i];
            total+=gas[i]-cost[i];
        }
        if (total<0) return -1;
        int start=0;
        total=0;
        for (int i = 0; i < gas.size(); i++) {
            total+=r[i];
            if (total<0){
                total=0;
                start=i+1;
            }

        }
        return start;
    }

};
int main() {
    vector<int> gas = {5,1,2,3,4};
    vector<int> cost = {4,4,1,5,1};
    Solution s = Solution();
    int ret = s.canCompleteCircuit(gas,cost);
    cout << ret <<endl;

    return 0;
}

75. 颜色分类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
// https://leetcode-cn.com/problems/sort-colors
using namespace std;
class Solution {
public:
    void sortColors(vector<int>& nums) {
        // [2,0,2,1,1,0]
        int z = -1,t=nums.size();
        for (int i = 0; i < t;) {
            if (nums[i]==1){
                i++;
            } else if (nums[i]==2){
                swap(nums[i],nums[--t]);
            } else
                swap(nums[i++],nums[++z]);

        }
    }
};
int main() {
    vector<int> a = {2,0,2,1,1,0};
    Solution s =  Solution();
    s.sortColors(a);
    for (int i = 0; i < a.size(); i++) {
        cout<<a[i]<<endl;
    }
    return 0;
}

283. 移动零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include "vector"

using namespace std;
// v1
/*
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        vector<int> NonZeroElements;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i]){
                NonZeroElements.push_back(nums[i]);
            }
        }
        for (int i = 0; i < NonZeroElements.size(); i++) {
            nums[i]= NonZeroElements[i];
        }
        for (int i =NonZeroElements.size();i<nums.size();i++){
            nums[i]=0;
        }

    }
};
 */

// v2
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int j = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i]){
                if (i!=j)
                    swap(nums[j++],nums[i]);
                else
                    j++;
            }
        }

    }
};

int main() {

    vector<int> a = {2,1,0,0,3};
    Solution().moveZeroes(a);
    for (int i = 0; i < a.size(); i++) {
        cout << a[i] <<endl;
    }

    return 0;
}

26 删除有序数组中的重复项

思路，快慢指针

题目明确是升序排列的。 快指针遍历，慢指针代表当前值； 遇到不相等元素时，如果i和j相差超过2说明中间肯定有重复的元素，慢指针自增1然后更新数组元素。

如果没有超过2说明没有重复，单纯让慢指针自增1，不更新数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>

using namespace std;
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty())
            return 0;
        int j=0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i]!=nums[j]){
                if (i-j>1)
                    nums[++j]=nums[i];
                else
                    j++;
            }
        }
        return j+1;

    }
};

int main() {
    vector<int> a ={1,2};
    Solution s = Solution();
    int ret = s.removeDuplicates(a);
    for (int i = 0; i < a.size(); i++) {
        cout << a[i] <<endl;

    }
    cout << ret <<endl;
    return 0;
}