lc-day13

发表于

376. 摆动序列

卡了一上午

贪心题还是挺麻烦的，至少我知道方法，但是没写出来（用Carl的话说就是：知道题目方法是常识性的东西，但是代码实现困难）

贪心主要方法：手动模拟方法，感觉可行，就试一试

难点1：如何设置寻找差值

有n个数，但是差值只有n-1个，怎么找呢。解决办法是在首部设置一个跟nums[0]相等的虚拟的数，然后就可以从第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
class Solution {
    public int wiggleMaxLength(int[] nums) {

        // 先把结果值+1，因为 n 个数最多形成n - 1 个峰值。
        // 我们的解题逻辑 -> 峰值就是结果
        int result = 1;

        // 假设数组前有一个假元素。值等于数组第一个元素
        // preDiff = (nums[0] - nums[-1]) = 0
        int preDiff = 0;
        int curDiff = 0; 

        for(int i = 1; i < nums.length; i++){
            curDiff = nums[i] - nums[i -1];
            //如果当前差值和上一个差值为一正一负
            // preDiff = 0 是初始状态。
            // curDiff 为 0 时（前后元素相同），不进入if
            if((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)){
                result++;
                preDiff = curDiff;
            }
        }

        return result;
    }
}

难点2：为什么是prediff <= 0? 这个问题我认为应该分开来思考成两种情况，< 0就不说了，一正一负很好理解。

问题是为什么等于零？为什么cur 不等于0，pre可以等于0？题目不是要求一正一负吗？这个问题应该这样思考，pre为0，cur不为零，那么证明此时cur这个点是峰值（低谷）的。反过来，如果cur==0， pre != 0，那就是说当前元素cur跟前一个元素重复了，所以就不对了，这个解法中的pre只会在开始为0，后面pre的取值由cur更新，而cur == 0是不满足if条件的。换句话说，如果数组中有重复元素，它只会取第一个，这也是这个算法的巧妙性

还有一个y总的代码也挺好的，下次更新吧

53. 最大子序和

题目

贪心解法

每次求值都进行选择,是当前的值【num[i]】更好还是【sum+num[i]】更好，局部最优形成全局最优

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

动态规划

核心公式差不多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        int ans = nums[0];
        int n = nums.size();
        int f[nums.size()];
        f[0] = nums[0];
        for(int i = 1; i < nums.size(); i++){
            if(f[i - 1] + nums[i] >= nums[i]) f[i] = f[i - 1] + nums[i];
            else f[i] = nums[i];
            ans = max(ans, f[i]);
        }
        return ans;
    }
};

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

这题有一个误区，就是我能不能在同一天卖，然后再买。题目没说，那就应该是可以的。所以贪心的思路也就出来了，检查每两天的股票差值，是正值就买入，是负值就跳过，从局部最优到全局最优

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

55. 跳跃游戏

题目

贪心题就是难想出来，代码其实挺简单的，这种题最重要的锻炼贪心思维

具体来说就是判断最大覆盖范围，如果在覆盖范围内就更新maxStep，最后结果就出来了

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

结尾

今天终于提起刷题的欲望了，但都是简单题？麻了，学计网去，等书到了开始更新计网的笔记，这种纯理论的东西就是记着玩，就是玩。