当前位置: 首页 > news >正文

376. 摆动序列——【Leetcode每日刷题】

376. 摆动序列

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

  • 例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

  • 相反,[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。

给你一个整数数组 nums ,返回 nums 中作为 摆动序列最长子序列的长度

示例 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

提示:

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

进阶:你能否用 O(n) 时间复杂度完成此题?

思路:

法一:动态规划

本题大家都很容易想到用动态规划来求解,求解的过程类似最长上升子序列。

  • 不过是需要判断两个序列;
  • 且需要nums相同长度的数组dp, flg,分别存放记录包括nums[i]在内的最长摆动序列及记录nums[j]与上一个数的差值符号。

法二:贪心

维护峰顶最大,峰谷最小:

  • 设立一个 flg 记录前一次 序列摆动的趋势,趋势相反,序列长度 加 1;
  • 如果相等元素跳过;
  • 如果一直递增,序列长度不变,最后一个值一直更新当前最大值;(这样才有更多的机会遇到较小的值)
  • 如果一直递减,序列长度不变,最后一个值一直更新当前最小值。(这样才有更多的机会遇到较大的值)

代码:(Java)

法一:动态规划

import java.util.Arrays;public class WiggleMaxLength {public static void main(String[] args) {// TODO Auto-generated method stubint[] nums = {1,17,5,10,13,15,10,5,16,8};System.out.println(wiggleMaxLength(nums));}public static int wiggleMaxLength(int[] nums) {int n = nums.length;int[] dp = new int[n];//记录包括nums[i]在内的最长摆动序列int[] flg = new int[n];//记录nums[i]与上一个数的差值符号Arrays.fill(dp, 1);Arrays.fill(flg, 0); // 1表示和上一个数的差为正数,-1 表示和上一个数之差为负数 ,0表示相等for(int i = 1; i < n; i++) {for(int j = 0; j < i; j++) {if(nums[i] != nums[j] && flg[j] != (nums[i] > nums[j] ? 1 : -1) && dp[j] + 1 > dp[i]){flg[i] = nums[i] > nums[j] ? 1 : -1;dp[i] = dp[j] + 1;}}}return dp[n - 1];}
}

法二:贪心

public class WiggleMaxLength {public static void main(String[] args) {// TODO Auto-generated method stubint[] nums = {1,17,5,10,13,15,10,5,16,8};System.out.println(wiggleMaxLength(nums));}public static int wiggleMaxLength(int[] nums) {int n = nums.length;int flg = 0;//记录nums[i]与上一个数的差值符号int len = 1;for(int i = 1; i < n; i++) {if(nums[i] == nums[len - 1]) {continue;}else if(flg != (nums[i] > nums[len - 1] ? 1 : -1)){flg = nums[i] > nums[len - 1] ? 1 : -1;nums[len] = nums[i];len++;}else {nums[len - 1] = nums[i];}}return len;}
}

运行结果:

在这里插入图片描述

复杂度分析

法一:动态规划

  • 时间复杂度:O(n2)O(n^2)O(n2),其中 n 是序列的长度。我们需要两重 for 循环。
  • 空间复杂度:O(n)O(n)O(n)。我们需要nums相同长度的数组dp, flg,分别存放记录包括nums[i]在内的最长摆动序列及记录nums[j]与上一个数的差值符号。

法二:贪心

  • 时间复杂度:O(n)O(n)O(n),其中 n 是序列的长度。我们只需要遍历该序列一次。
  • 空间复杂度:O(1)O(1)O(1)。我们只需要常数空间来存放若干变量。
类似题解题目:

646. 最长数对链
300. 最长递增子序列

注:仅供学习参考!

题目来源:力扣。

相关文章:

376. 摆动序列——【Leetcode每日刷题】

376. 摆动序列 如果连续数字之间的差严格地在正数和负数之间交替&#xff0c;则数字序列称为 摆动序列 。第一个差&#xff08;如果存在的话&#xff09;可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。 例如&#xff0c; [1, 7, 4, 9, 2, 5] 是一个…...

mgre实验

实验思路 1、首先根据拓扑结构合理分配IP地址&#xff0c;并对各个路由器的IP地址和R5环回接口的IP地址进行配置。 2、让私网中的边界路由器对ISP路由器做缺省路由。 3、根据实验要求&#xff0c;对需要配置不同类型认证的路由器进行认证配置&#xff0c;和需要不同封装的协议…...

一文彻底了解Zookeeper(介绍篇)

zookeeper 是什么&#xff1f; zookeeper是一个分布式协作框架&#xff0c;提供高可用&#xff0c;高性能&#xff0c;强一致等特性 zookeeper 有哪些应用场景&#xff1f; 分布式锁&#xff1a;分布式锁是指在分布式环境中&#xff0c;多个进程或线程需要互斥地访问某个共享…...

1. ELK Stack 理论篇之什么是ELK Stack?

ELK Stack 理论篇之什么是ELK Stack?1.1 什么是 ELK Stack&#xff1f;1.2 ELK Stack的发展史1.2.1 Elasticsearch1.2.2 引入 Logstash 和 Kibana&#xff0c;产品更强大1.2.3 社区越来越壮大&#xff0c;用例越来越丰富1.2.4 然后我们向 ELK 中加入了 Beats1.2.5 那么&#x…...

两道有关链表的练习

目录 一、分割链表 二、奇偶链表 一、分割链表 给你一个链表的头节点 head 和一个特定值 x &#xff0c;请你对链表进行分隔&#xff0c;使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你不需要 保留 每个分区中各节点的初始相对位置。 示例 1&#xff1a; 输…...

Python uiautomator2安卓自动化测试

一、前言 uiautomator2是Python对Android设备进行UI自动化的库&#xff0c;支持USB和WIFI链接&#xff0c;可以实现获取屏幕上任意一个APP的任意一个控件属性&#xff0c;并对其进行任意操作。 重点是它可以实现安卓自动化采集&#xff0c;甚至是群控采集&#xff0c;且安装和…...

Leetcode. 160相交链表

文章目录指针解法指针解法 核心思路 &#xff1a; 先 分别求两个链表的长度 然后长的链表先走 差距步&#xff08;长-短&#xff09; 最后长链表和短链表同时走 &#xff0c;第一地址相同的就是交点 &#xff0c;注意一定是地址相同 不可能出现上图这种情况 &#xff0c;因为C1…...

MDPs —— 马尔可夫决策定义与算法

文章目录MDPs 定义——由实例开始时序决策问题给游戏增点乐子*为什么要有折扣游戏的解——原则所以&#xff0c;什么是 MDPs&#xff1f;MDPs 的基本原理、表示光环原理效用的求解是反向传播的原则不变条件MDPs 的表示MDPs 求解效用迭代法缺点原则迭代法MDPs 定义——由实例开始…...

【C++】图

本文包含了图的基本概念 1.相关概念 1.1 无/有向 无向图&#xff1a;每一个顶点之间的连线没有方向 有向图&#xff1a;连线有方向&#xff08;类似离散数学的二元关系 <A,B>代表从A到B的边&#xff0c;有方向&#xff09; <A,B>中A为始点&#xff0c;B为终点在…...

尾递归优化

文章目录1. 前言2. 什么尾调用&#xff08;Tail Call&#xff09;&#xff1f;3. 尾调用优化4. Linux内核下的尾递归优化使用5. 参考资料1. 前言 限于作者能力水平&#xff0c;本文可能存在谬误&#xff0c;对此给读者带来的损失&#xff0c;作者不错任何承诺。 2. 什么尾调用…...

P1120 小木棍(搜索+剪枝)

题目链接&#xff1a;P1120 小木棍 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 样例输入&#xff1a; 9 5 2 1 5 2 1 5 2 1 样例输出&#xff1a; 6 分析&#xff1a;这道题一看数据范围就知道是搜索&#xff0c;但关键是需要剪枝。 首先我们求出所有木棍的长度和&am…...

【专项训练】动态规划-3

动态规划:状态转移方程、找重复性和最优子结构 分治 + 记忆化搜索,可以过度到动态规划(动态递推) function DP():# DP状态定义# 需要经验,需把现实问题定义为一个数组,一维、二维、三维……dp =[][] # 二维情况for i = 0...M:...

【Linux】信号+再谈进程地址空间

目录 一、Linux中的信号 1、Linux中的信号 2、进程对信号的处理 3、信号的释义 二、信号的捕捉 1、信号的捕捉signal() 2、信号的捕捉sigaction() 三、信号如何产生&#xff1f; 1、kill()用户调用kill向操作系统发送信号 通过命令行参数模仿写一个kill命令 2、rais…...

C++回顾(二十一)—— list容器

21.1 list概述 list是一个双向链表容器&#xff0c;可高效地进行插入删除元素。list不可以随机存取元素&#xff0c;所以不支持at.(pos)函数与[]操作符。It(ok) it5(err)需要添加头文件&#xff1a;#include <list> 21.2 list构造 &#xff08;1&#xff09;默认构造…...

爱国者一体机电脑蓝屏怎么U盘重装系统教学?

爱国者一体机电脑蓝屏怎么U盘重装系统教学&#xff1f;有用户使用的爱国者一体机电脑开机了之后突然变成了蓝屏的了。而且无法继续使用了&#xff0c;那么遇到这样的蓝屏问题怎么去进行系统的重装呢&#xff1f;一起来看看以下的U盘重装系统教学吧。 准备工作&#xff1a; 1、U…...

Vue学习笔记(9)

9.1 axios 9.1.1 概述 Axios是一个流行的基于Promise的HTTP客户端&#xff0c;用于在浏览器和Node中发送HTTP请求。它可以用于处理各种请求类型&#xff0c;例如GET&#xff0c;POST等。Axios可以很容易地与现代前端框架和库集成&#xff0c;例如React&#xff0c;Vue等。 A…...

中值滤波+Matlab仿真+频域响应分析

中值滤波 文章目录中值滤波理解中值滤波的过程Matlab 实现实际应用频域分析中值滤波是一种滤波算法&#xff0c;其目的是去除信号中的噪声&#xff0c;而不会对信号本身造成太大的影响。它的原理非常简单&#xff1a;对于一个给定的窗口大小&#xff0c;将窗口内的数值排序&…...

自然语言处理中数据增强(Data Augmentation)技术最全盘点

与“计算机视觉”中使用图像数据增强的标准做法不同&#xff0c;在NLP中&#xff0c;文本数据的增强非常少见。这是因为对图像的琐碎操作&#xff08;例如将图像旋转几度或将其转换为灰度&#xff09;不会改变其语义。语义上不变的转换的存在是使增强成为Computer Vision研究中…...

PINN解偏微分方程实例1

PINN解偏微分方程实例11. PINN简介2. 偏微分方程实例3. 基于pytorch实现代码4. 数值解参考资料1. PINN简介 PINN是一种利用神经网络求解偏微分方程的方法&#xff0c;其计算流程图如下图所示&#xff0c;这里以偏微分方程(1)为例。 ∂u∂tu∂u∂xv∂2u∂x2\begin{align} \frac{…...

【python 基础篇 十二】python的函数-------函数生成器

目录1.生成器基本概念2.生成器的创建方式3.生成器的输出方式4.send()方法5.关闭生成器6.注意事项1.生成器基本概念 是一个特色的迭代器&#xff08;迭代器的抽象层级更高&#xff09;所以拥有迭代器的特性 惰性计算数据 节省内存 ----就是不是立马生成所有数据&#xff0c;而是…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...