lc-day14

发表于

45 跳跃游戏2

题目

我好蠢，我好蠢，我好蠢，我好蠢，我好蠢，我好蠢，我好蠢，我好蠢，我好蠢…………

别人的更新方式各种ac，我的各种卡死

写了好久，最后还是看题解了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int jump(vector<int>& nums) {
        int start = 0, end = 1;
        int ans = 0;
        int maxPos = 0;
        while(end < nums.size()){
            for(int j = start; j < end; j++){	//左闭右开区间， 循环体更新maxpos
                maxPos = max(maxPos, j + nums[j]);
            }
            start = end;			//更新区间左右端点
            end = maxPos + 1;
            ans++;
        }
        return ans;
    }
};

这个作者的代码，严格遵循了左闭右开的习惯，在第二层循环中遍历完区间，然后更新左右端点

ver2.0

这个代码的优化版本 tql

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int jump(vector<int>& nums) {
        int ans = 0;
        int end = 0;
        int maxpos = 0;
        for(int i = 0; i < nums.size() - 1; i++){
            maxpos = max(maxpos, i + nums[i]);
            if(end == i){	// 遇到当前覆盖的最远距离下标
                ans++;			//步数加1
                end = maxpos;	// 更新覆盖最远距离的下标
            }
        }
        return ans;
    }
};

1005. K 次取反后最大化的数组和

题目

写了这么多题目，感觉还是啥也不会，想到了第一层，没想到第二层，想到了排序没想到取绝对值，想到了第一层没想到第二层，题目还是做少了，我是sb

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    static bool cmp(int a, int b){
        return abs(a) < abs(b);
    }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), cmp);
        for(int i = nums.size() - 1; i >= 0; i--){		//第一步局部最优， 负数取反
            if(nums[i] < 0 && k > 0) {
                k--;
                nums[i] = -nums[i];
            }
        }
        if(k % 2 == 1) nums[0] = -nums[0];		// 如果负数用完了，就判断k的奇偶性，判断是否要给绝对值最小的
        									//数取反
        int ans = 0;
        for(int &i : nums) ans += i;
        return ans;
    }
};

134. 加油站

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int rest = 0;
        int total = 0;
        int start = 0; 
        for(int i = 0; i < gas.size(); i++){
            rest += gas[i] - cost[i];
            total += gas[i] - cost[i];
            if(rest < 0) {
                start = i + 1;
                rest = 0;
            }
        }
        if(total < 0) return -1;
        return start;
    }
};

总结：如果x到不了y+1（但能到y），那么从x到y的任一点出发都不可能到达y+1。因为从其中任一点出发的话，相当于从0开始加油，而如果从x出发到该点则不一定是从0开始加油，可能还有剩余的油。既然不从0开始都到不了y+1，那么从0开始就更不可能到达y+1了…