代码随想录算法训练营第32天

LeetCode 122.买卖股票的最佳时机 II

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result=0;
        for(int i=1;i<prices.size();i++){
            if(prices[i]-prices[i-1]>=1){
                result+=prices[i]-prices[i-1];
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

简单

LeetCode 55. 跳跃游戏

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size()<=1)return true;
        int cover=0;
        for(int i=0;i<=cover;i++){
            cover=max(cover,i+nums[i]);
            if(cover>=nums.size()-1)return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

这个题目思路有点吊。

LeetCode 45.跳跃游戏 II

以下两段是我自己写的代码自己分析的

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()<=1)return 0;
        int cover=nums[0],count=0;
        for(int i=0;i<nums.size();){
            int n=cover;
            int x=i;
            if(nums[i]+i>=nums.size()-1){
                count++;
                break;
            }
            for(int j=i;j<=n;j++){
                if(nums[j]+j>=cover){
                    x=j;
                    cover=nums[j]+j;
                }
            }
            cover=x+nums[x];
            i=x;
            count++;
            if(cover>=nums.size()-1){
                count++;
                break;
            }
        }
        return count;
    }
};
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

上面跟下面的代码是把

if(nums[i]+i>=nums.size()-1){
                count++;
                break;
            }
1
2
3
4

这一段做了一个位置上的变化，一个放在上面的代码放在了for循环函数中间，下面的代码放在了开始。
这一段和if(nums.size()<=1)return 0;都是为了限定临界情况，一个是只有一个数，返回0，另一个是如例子[1,2]，只走一步就可以，但是在for函数中，对count是加了两次的，因为实际上在for中，cover是当前i位置后面所能覆盖的范围，所以在最后break时再对count进行了+1操作。

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()<=1)return 0;
        int cover=nums[0],count=0;
        if(nums[0]>=nums.size()-1){
                count++;
                return count;
            }
        for(int i=0;i<nums.size();){
            int n=cover;
            int x=i;
            
            for(int j=i;j<=n;j++){
                if(nums[j]+j>=cover){
                    x=j;
                    cover=nums[j]+j;
                }
            }
            cover=x+nums[x];
            i=x;
            count++;
            if(cover>=nums.size()-1){
                count++;
                break;
            }
        }
        return count;
    }
};
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

主要思路：不用常规的i++对i进行变换，这里我用了个x来记录x的变换，内层for（j）这个循环是为了选取i位置向后走的值再向后走一步能走到的最远位置，用x记录下一个位置并更新i。

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

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=0;i<nums.size();i++){
            if(nums[i]<0 && k>0){
                nums[i]*=-1;
                k--;
            }
        }
        if(k%2==1)nums[nums.size()-1]*=-1;
        int result=0;
        for(int a:nums)result+=a;
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

按绝对值从大到小排序