leetcode

leetcode刷题Day02

Posted by wzc on 2021-04-07

leetcode刷题Day02

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

题目链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

第一天当然没有利润，至少要第二天才会有利润，所以利润的序列比股票序列少一天！

从图中可以发现，其实我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。

那么只收集正利润就是贪心所贪的地方！

局部最优：收集每天的正利润，全局最优：求得最大利润。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//思路：将利润分为每天，选择每天的正利润之和
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result=0;
        int cur;
        for(int i=0;i<prices.size()-1;i++)
        {
            cur=prices[i+1]-prices[i];
            if(cur>0)
                result+=cur;
        }
        return result;
    }
};

55.跳跃游戏

题目链接：https://leetcode-cn.com/problems/jump-game/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//求是否可以跳到最后一个下标
//思路：转化为覆盖范围是否大于等于数组的长度-1
//每次更新覆盖范围：比较cover是否大于i+nums[i]
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int t;
        int cover=0;
        for(int i=0;i<=cover;i++)
        {
            t=nums[i]+i;
            cover=cover>t?cover:t;
            if(cover>=nums.size()-1)
                return true;
        }
        return false;
    }
};

45.跳跃游戏II

题目链接：https://leetcode-cn.com/problems/jump-game-ii/

思路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
//使用最少的次数到达最后一个位置
//总是可以到达最后一个位置
//思路1:遍历数组，统计每个最大范围中的最大值，比较是否到达了最终结点，其中，当遍历到最大范围结点时，需要将步数加一
class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()<2)
            return 0;
        int end=0;//记录最远距离
        int k=0;//记录中间最大值
        int step=0;
        for(int i=0;i<nums.size();i++)
        {
            k=k>nums[i]+i?k:nums[i]+i;
            if(k>=nums.size()-1)
                return step+1;
            if(end==i)//最远的点
            {
                step++;
                end=k;
            }
        }
        return step;

    }
};

思路2: 对思路1进行简化，题目中假设数据都可以到达，那么如果最大范围大于nums.size()-2，必定是可以到达的，也即最大范围结点大于nums.size()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()<2)
            return 0;
        int end=0;//记录最远距离
        int k=0;//记录中间最大值
        int step=0;
        for(int i=0;i<nums.size()-1;i++)
        {
            k=k>nums[i]+i?k:nums[i]+i;
            if(end==i)//最远的点
            {
                step++;
                end=k;
            }
        }
        return step;

    }
};

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

题目链接：https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/

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
//思路很简单，如果有负数，依次将最小负数取反，没有负数，则将最小正数依次取反
//暴力求解法：每次从小到大排序，总是改变第一个元素，然后再排序
//优化：只排一次序，按照绝对值从大到小排序，遍历数组，遇到负数取反，若遍历到最后k仍大于0，只对最后一个反复操作即可
class Solution {
    static bool cmp(int a,int b)//设定比较条件
    {
        return abs(a)>abs(b);
    }
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(),A.end(),cmp);//按照绝对值排序

        int i=0;
        while(K>0&&i<A.size())
        {
            if(A[i]<0)
            {
                A[i]=-A[i];
                K--;
            }
            i++;
        }
        if(K%2==1)//奇数
            A[i-1]=-A[i-1];
        int result=0;
        for(i=0;i<A.size();i++)
        {
            result+=A[i];
        }
        return result;
    }
};

另一种思路：由于数组大小绝对值不大于100，因此可使用桶排序进行优化，算法复杂度为O(n)

CATALOG
    FEATURED TAGS
    leetcode
    FRIENDS