128、【贪心算法】leetcode ——376. 摆动序列（c++版本）-爱代码爱编程

2023-01-31 分类: # 贪心算法 leetcode c++ 贪心算法数据结构与算法刷题

题目描述

解题思路

将此问题用图示方式，转化为山坡和山峰模型来研究。采用贪心算法，找到每一个小山峰，从而找到所有的小山峰即可。

对于单向上升或下降的坡，可视为一个摆动序列，对应的最长子序列长度为2。

可能会出现的坡形有三种：

上下坡中有平坡
数组首尾两端
单调坡度有平坡
全平坡
此时，数组中的数全为0，对应的最长子序列长度为1。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() <= 1)            return nums.size();
        // 当nums.size()≥2时，res从1开始，满足条件时则加一不满足时，则减一
        int prediff = 0, curdiff= 0, res = 1;
        for(int i = 0; i < nums.size() - 1; i++) {
            // 记录当前峰值差
            curdiff = nums[i + 1] - nums[i];
            // 前一个峰值差有等于的原因是因为初值为0，只要当前与前一个有正负差异即可。
            if((prediff <= 0 && curdiff > 0) || (prediff >= 0 && curdiff < 0)) {
                res++;
                prediff = curdiff;
            }
        }
        return res;
    }
};

参考文章：376. 摆动序列

本文链接：https://blog.csdn.net/qq_41094332/article/details/128821592

【leetcode】376. 摆动序列结题报告 (c++)-爱代码爱编程

2019-03-15 分类: leetcode

原题地址：https://leetcode-cn.com/problems/wiggle-subsequence/submissions/ 题目描述：给定一个整数序列，返回作为摆动序列的最长子序列的长度。通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。示例 1: 输入: [1,7,4,9,2,5] 输出:

leetcode 376. 摆动序列解题思路及c++实现_paninigu的博客-爱代码爱编程

2019-05-19 分类: leetcode

解题思路：使用贪心算法的思想。在例子 [1,17,5,10,13,15,10,5,16,8]中，[1, 17]、[17, 5]这前面的两个序列就直接都选择了，没有问题，对于后面[5, 10, 13, 15]这样的子序列，数值连续增大，则利用贪心的思想选取差值最大的两个数，即[5, 15]，删除(不选）数字10和13，再往后的序列[15, 10, 5

leetcode刷题97-376. 摆动序列(c++详细解法！！！)_hanxiao_101的博客-爱代码爱编程_leetcode 376 c++

2019-06-08 分类: leetcode c++ leetcode从零开始

Come from : [https://leetcode-cn.com/problems/assign-cookies/] 376. Wiggle Subsequence 1.Question 2.

【LeetCode】No.376 摆动序列（C++实现贪心算法）-爱代码爱编程

2019-12-31 标签: leetcode 贪心算法摆动序列分类: leetcode

分析：其实题意分析起来不难，上图中diff分别为nums[i]-nums[i-1],如果大于零就表示为1，小于零就表示为-1。知道找到最长的不连续的 1和-1序列即可，如上图中的三个连续的1删除左边的10和12，两个连续的-1删除10。而且很容易就能写出事件复杂度为O(n)的程序，但重点就在于空间复杂度，能不能用O(1)的空间复杂度完成编程

[贪心算法]LeetCode 376.摆动序列-爱代码爱编程

2020-07-13 标签: c++分类: 贪心

题面如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它

leetcode 376. 摆动序列-爱代码爱编程

2020-12-12 标签: c++ leetcode 贪心算法分类: leetcode

首先预祝大家今天四六级都考100分呐（狗头保命） class Solution { public: int wiggleMaxLength(vector<int>& nums) { if (nums.size() <= 1) { return nums.size(); } int pre = 0,cur = 0;

19、【顺序表】删除顺序表内所有指定元素（C++版）-爱代码爱编程

2021-01-04 分类: 算法刷题算法 c++

题目描述对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。 // 顺序表结构如下 typedef struct SeqList{ ElemType* data; int length,MaxSize; } SeqList; 题目分析最终实现的结果是不存在目标元素的顺序表

leetcode刷题/贪心算法 376. 摆动序列-爱代码爱编程

2021-08-19 分类: leetcode 算法数据结构 c++ 贪心算法 leetcode刷题/贪

376. 摆动序列题意: 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。例如， [1, 7, 4, 9, 2, 5] 是一个摆动序列，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。相反，[

LeetCode.376.摆动序列（贪心）-爱代码爱编程

2022-02-03 分类: 算法 c++ 贪心算法

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。例如， [1, 7, 4, 9, 2, 5] 是一个摆动序列，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。相反，[1, 4, 7, 2, 5] 和

Leetcode-376. 摆动序列-爱代码爱编程

2022-03-19 分类: leetcode 算法 # leetcode（贪

链接 376. 摆动序列题目如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。例如， [1, 7, 4, 9, 2, 5] 是一个摆动序列，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。相

leetcode-376.摆动序列-爱代码爱编程

2022-03-28 分类: leetcode 算法数据结构 c++ 贪心算法

贪心算法题目详情如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。例如， [1, 7, 4, 9, 2, 5] 是一个摆动序列，因为差值 (6, -3, 5, -7, 3)是正负交替出现的。相反，[1, 4, 7, 2,

Leecode 376. 摆动序列贪心-爱代码爱编程

2022-04-20 分类: LeeCode leetcode c++ 贪心算法

原题链接：Leecode 376. 摆动序列的确贪心用pre表示前面得连续数字之间的差是正数(1)还是负数(-1)，贪心的思想体现在变量last，用last记录序列中的前一个数字，如果出现了连续递增的序列，那么last表示的是递增序列中的最大值，如果接下来的数字小于了这个最大值，序列就出现了摆动，长度加一；如果出现了连续递减的序列，那么last表示的是

c++刷题笔记(32)——贪心算法、leetcode455、376、53、122、55、45_stateabc的博客-爱代码爱编程

2022-05-25 分类: leetcode 算法数据结构 c++ 贪心算法不知道能不能混口饭的c嘎

贪心算法贪心算法理论基础局部最优推出全局最优题目1：455.分发饼干根据示例可知就是尽量满足每个孩子局部最优就是大饼干给胃口大的，全局最优就是尽量满足多的孩子。先将饼干和小孩数组排序，然后从后往前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。 class Solution { public: int findC

leetcode：贪心算法_lucky-wz的博客-爱代码爱编程

2022-06-10 分类: leetcode 算法贪心算法

LeetCode：贪心算法求解最优化的问题常常会有一系列的步骤，而每个步骤往往会面临着选择。贪心算法在每一步都做出最优解，寄希望于通过局部最优解来获得全局最优解。贪心算法往往是这种自顶向下的设计，先做出一个选择，然后再求解下一个问题，而不是自底向上解出许多子问题，然后再做出选择。在做贪心选择时，我们直接做出当前问题中看起来最优的解s，而不是考虑到子

leetcode 376.摆动序列贪心法求解（c++版本）_学不完了ccccc的博客-爱代码爱编程

2022-11-11 分类: leetcode 算法 c++

题目描述这道题虽然看着简单，但是个人感觉真的不好理解（我是第一次没理解正确）明确以下几点差值需要是正数或者负数才算这两个数构成一个摆动序列，0不算可以删除原始序列中的一些点，说明序列可以跳着取，序列不一定要连续可

day31.贪心算法：分发饼干、摆动序列、最大子序和_izwmain的博客-爱代码爱编程

2022-11-26 分类: 代码随想录 leetcode 算法数据结构 c++ 贪心算法

Day31.贪心算法：分发饼干、摆动序列、最大子序和 0455.分发饼干链接：0455.分发饼干对两个数组排序，那么饼干和需求数组的大值都在数组后面。用当前最大的饼干尽可能满足最大的需求。从后向前遍历g数组

leetcode刷题复盘笔记—一文搞懂贪心算法之376. 摆动序列问题（贪心算法系列第二篇）-爱代码爱编程

2023-01-15 分类: leetcode c++ 动态规划程序人生贪心算法

今日主要总结一下贪心算法的一道题目，376. 摆动序列问题题目：376. 摆动序列 Leetcode题目地址题目描述：如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的

leetcode·376.摆动序列·贪心·动态规划-爱代码爱编程

2022-09-06 分类: Leetcode刷题笔记 leetcode 算法贪心算法

链接：https://leetcode.cn/problems/wiggle-subsequence/solution/-by-xun-ge-v-nh8y/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。题目示例思路解题思路【贪心】贪心思维在于局部最优推出全局最优对

27.贪心(1) | 分发饼干、摆动序列、最大子序和(h)-爱代码爱编程

2023-07-16 分类: 代码随想录 leetcode 算法数据结构 c++ 贪心算法

今天是贪心算法的第1天，但题目做的却比较艰难。学到的贪心算法的套路就是没有套路，每一道题都可能是新的套路。过于详细的理论推导没有必要，举例验证即可。贪心题目大多是会就会，不会就不会的，所以在做的时候也不用太纠结，不会的话去看题解就行。第1题（455. 分发饼干）相对容易，自己实现的贪心策略是从优先用小饼