LeetCode:376. 摆动序列——说什么贪心和动规~

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

🍎道阻且长,行则将至。🍓

🌻算法,不如说它是一种思考方式🍀


算法专栏: 👉🏻123


一、🌱376. 摆动序列

  • 题目描述:如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
    例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
    相反,[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。
    子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。
    给你一个整数数组 nums ,返回 nums 中作为 摆动序列 的 最长子序列的长度

  • 来源:力扣(LeetCode)

  • 难度:中等

  • 提示:
    1 <= nums.length <= 1000
    0 <= nums[i] <= 1000

  • 示例 1
    输入:nums = [1,7,4,9,2,5]
    输出:6
    解释:整个序列均为摆动序列,各元素之间的差值为 (6, -3, 5, -7, 3) 。
    示例 2
    输入:nums = [1,17,5,10,13,15,10,5,16,8]
    输出:7
    解释:这个序列包含几个长度为 7 摆动序列。
    其中一个是 [1, 17, 10, 13, 10, 16, 8] ,各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
    示例 3
    输入:nums = [1,2,3,4,5,6,7,8,9]
    输出:2

🌴解题

解题思路有贪心和动态规划~

🌾贪心

本题我们要找到就是一个支持 …这样变换的元素顺序序列:
LeetCode:376. 摆动序列——说什么贪心和动规~
于是我们可以添加一个boolean tag作为标记,确定当前状态(tag==true代表当前状态是上行),然后根据当前状态找出下一个状态,for循环遍历这个数组,就统计出符合要求的节点。由于统计的是段,节点数就需要+1。只遍历一遍数组,所以时间复杂度是O(n),没有n相关的数据结构,空间复杂度是O(1)。

for (i = 1; i < nums.length-1; i++) {
    if(tag==true&&nums[i+1]<nums[i]){
        tag=false;
        sum++;
    }
    if(tag==false&&nums[i+1]>nums[i]){
        tag=true;
        sum++;
    }
}

就算其中出现递增 递减或者不变的元素,也是不影响我们这个推理的,大家不妨画图验证一下。
LeetCode:376. 摆动序列——说什么贪心和动规~

  • code
class Solution {
    public int wiggleMaxLength(int[] nums) {
       if(nums.length==1)
            return 1;
        int sum=0;
        boolean tag = false;
        int i=0;
        while (nums[i]==nums[i+1]){
            i++;
            if(i== nums.length-1)
                return 1;
        }
        if(nums[i]>nums[i+1]){
            tag=false;
            sum++;
        }
        if(nums[i]<nums[i+1]){
            tag=true;
            sum++;
        }
        for (; i < nums.length-1; i++) {
            if(tag==true&&nums[i+1]<nums[i]){
                tag=false;
                sum++;
            }

            if(tag==false&&nums[i+1]>nums[i]){
                tag=true;
                sum++;
            }
        }
        return sum+1;
    }
}

LeetCode:376. 摆动序列——说什么贪心和动规~
前面的方法也是一种贪心法,既然出现有状态,就可以使用动态规划法了。

🌾动态规划

首先初始状态(i=0):up=down=1;表示上行和下行段。
遍历数组(i++):
 如果当前段是上行,那么匹配的就是前面的下行状态咯,于是up=down+1
 如果当前段是下行,那么匹配的就是前面的上行状态,于是down=up+1
返回max(up,down)。

  • code
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        int up = 1, down = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            } else if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }
}

宝马雕车香满路。
凤箫声动,玉壶光转,一夜鱼龙舞。

返回第一页。☝


☕物有本末,事有终始,知所先后。🍭

LeetCode:376. 摆动序列——说什么贪心和动规~

🍎☝☝☝☝☝我的CSDN☝☝☝☝☝☝🍓 文章来源地址https://www.toymoban.com/news/detail-435318.html

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

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

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

相关文章

  • leetcode 376. 摆动序列

            本题思路是定义一个 direct变量记录上一次摆动是上坡还是下坡 。 然后在一个for循环中循环判断当前摆动和上一次摆动是否一致,如果不一致则视为一次摆动。 如果前后元素值相等得话,直接continue进入下一次循环。         下面看代码:

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

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

    2024年01月19日
    浏览(43)
  • 摆动序列——力扣376

    题目描述 贪心

    2024年02月13日
    浏览(33)
  • LeetCode刷题笔记【23】:贪心算法专题-1(分发饼干、摆动序列、最大子序和)

    贪心的本质是选择每一阶段的局部最优,从而达到全局最优。 例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿? 指定每次拿最大的,最终结果就是拿走最大数额的钱。 每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。 感觉像

    2024年02月09日
    浏览(50)
  • 代码随想录27|455.分发饼干,376. 摆动序列,53. 最大子序和

    链接地址 链接地址 链接地址

    2024年02月11日
    浏览(42)
  • 算法题:摆动序列(贪心算法解决序列问题)

    这道题是一道贪心算法题,如果前两个数是递增,则后面要递减,如果不符合则往后遍历,直到找到符合的。(完整题目附在了最后) 代码如下: 完整题目: 376. 摆动序列 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为  摆动序列 。 第一个差(如果

    2024年02月07日
    浏览(60)
  • 摆动序列【贪心算法】

    摆动序列 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

    2024年02月11日
    浏览(40)
  • leetcode 121. 买卖股票的最佳时机 (贪心 + 动规

    贪心的思路: 得到最小值,再挨个用数组中的值减去最小值,最终值取一个最大的 动规的思路: 现在觉得做动规的关键点就是找出,当前的状态是否与之前的状态有关,也就是说:当前一般会有两种状态,具体哪一种为最优,需要依靠之前的状态及逆行推导。 比如说本题

    2024年02月02日
    浏览(43)
  • day55 动规.p15 子序列

    - 392.判断子序列  ```cpp class Solution { public:     bool isSubsequence(string s, string t) {         vectorvectorint dp(s.size() + 1, vectorint(t.size() + 1, 0));         for (int i = 1; i = s.size(); i++) {             for (int j = 1; j = t.size(); j++) {                 if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] +

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

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

    2024年02月11日
    浏览(34)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包