摆动序列【贪心算法】

这篇具有很好参考价值的文章主要介绍了摆动序列【贪心算法】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  1. 摆动序列
    如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
    摆动序列【贪心算法】,贪心算法,算法
class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length <= 1) {//特殊情况处理,<2的情况统一处理
            return nums.length;
        }
        int cur = 0;
        int pre = 0;//默认造一个平波,易于与后面满足if条件更新数据的形式保持统一
        int count = 1;//(默认,结尾必然存在一个波动,从1开始)

        for (int i = 0; i < nums.length - 1; i++) {
            cur = nums[i + 1] - nums[i];//注意需要根据前后的正负号及逆行判别
            if (pre >= 0 && cur < 0 || pre <= 0 && cur > 0) {
                count++;
                pre = cur;//在if里面,保证了只有发生波动时才进行更新pre的值(主要关注其正负号)
            }
        }
        return count;
    }
}

文章来源地址https://www.toymoban.com/news/detail-676136.html

到了这里,关于摆动序列【贪心算法】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法训练day31贪心算法理论基础Leetcode455分发饼干376摆动序列53最大子序和

    文章链接 代码随想录 (programmercarl.com) 说实话贪心算法并没有固定的套路 。 最好用的策略就是举反例,如果想不到反例,那么就试一试贪心吧 。 面试中基本不会让面试者现场证明贪心的合理性,代码写出来跑过测试用例即可,或者自己能自圆其说理由就行了 。 刷题或者面

    2024年02月20日
    浏览(45)
  • Day31 贪心算法 part01 理论基础 455.分发饼干 376.摆动序列 53.最大子序和

    什么是贪心 贪心的本质是选择每一阶段的局部最优,从而达到全局最优 。 这么说有点抽象,来举一个例子: 例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿? 指定每次拿最大的,最终结果就是拿走最大数额的钱。 每次拿最大的就是局部最优,最

    2024年01月19日
    浏览(43)
  • LeetCode:376. 摆动序列——说什么贪心和动规~

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 题目描述 :如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也

    2024年02月03日
    浏览(39)
  • 算法刷题Day 31 分发饼干+摆动序列+最大子序列和

    分发饼干其实有很多种写法,但是下面这种贪心的解法是最好理解,也最好解释的 我的其他解法 贪心算法 这道题用贪心算法要考虑的细节有很多。 动态规划 有点难(甚至涉及到了线段树),等后面二刷的时候再来学好了 暴力解法 超时了 贪心算法 贪心算法的代码写起来简

    2024年02月15日
    浏览(42)
  • 贪心算法学习——最长单调递增子序列

    目录 ​编辑 一,题目 二,题目接口 三,解题思路和代码 给你一个整数数组  nums  ,找到其中最长严格递增子序列的长度。 子序列  是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如, [3,6,2,7]  是数组  [0,3,1,6,2,2,7]  的子序列。  

    2024年02月08日
    浏览(40)
  • 【贪心算法】334. 递增的三元子序列

    找到的递增序列 不一定是连续的 固定第一个数first 然后开始向后找第二个数second 要求second 大于 first 找到之后 向后找第三个数third 找到 返回true 如果third first 那么更新first = third 重新找 如果只是third first 更新second

    2024年02月16日
    浏览(37)
  • C++ 求最大子序列和(贪心算法)

    #include \\\"iostream\\\" #include \\\"vector\\\" using namespace std; class Solution { // 得到一个最大的负数 int isAllLow(vectorint nums){ int max=nums[0]; for (int i = 1; i nums.size(); ++i) { if(maxnums[i]){ max=nums[i]; } } return max; } public: // 求最大子序列 int maxSubArray(vectorint nums) { int sum=0; int maxsum=this-isAllLow(nums); // 如果是一个

    2024年02月07日
    浏览(40)
  • Leetcode376. 摆动序列

    题目来源:376. 摆动序列 约定: 某个序列被称为「上升摆动序列」,当且仅当该序列是摆动序列,且最后一个元素呈上升趋势。 某个序列被称为「下降摆动序列」,当且仅当该序列是摆动序列,且最后一个元素呈下降趋势。 特别地,对于长度为 1 的序列,它既是「上升摆动

    2024年02月09日
    浏览(32)
  • 摆动序列——力扣376

    题目描述 贪心

    2024年02月13日
    浏览(33)
  • 【学会动态规划】摆动序列(27)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 题目链接:376. 摆动序列 - 力扣(LeetCo

    2024年02月11日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包