贪心：Wiggle Subsequence 摇摆序列
一个整数序列，如果两个相邻元素的差恰好正负(负正)交替出现，则该序列被称为
摇摆序列。一个小于2个元素的序列直接为摇摆序列。给一个随机序列，求这个序列满足摇摆序列定义的最长子序列的长度：
输入[1,17,5,10,13,15,10,5,16,8]，结果为7([1,17,10,13,10,16,8] )
序列 [1, 7, 4, 9, 2, 5]，相邻元素的差 (6, -3, 5, -7, 3)，则为摇摆序列，结果为6
序列 [1,4,7,2,5] (3, 3, -5, 3)、 [1,7,4,5,5] (6, -3, 1, 0)不是摇摆序列，结果为2
根据贪心算法的核心：
- 寻找数据规律
- 使用最优的迭代策略
分析：
- 规律
很明显，摇摆序列的判定并不支持存在连续三个或者更多元素是递增或者递减的情况；需要连续三个元素中处于中间的元素要么比两边的元素小，要么比两边的元素大 - 迭代策略
当出现连续三个或者更多元素是递增/递减的情况时，选择最优（最后一个递增/递减的元素作为可以假如摇摆序列的转折点，因为最后一个元素最大/最小，相比与下一个元素，有更大的可能使得其也满足摇摆序列）
比如[1,17,5,10,13,15,10,5,16,8] 中 [10,13,15] 三个连续递增，那么选择15则会使得下一个10也能够满足成为摇摆序列中的元素
实现算法（文末有完整测试代码）:方法一
/*if..else if .. else */
int get_swing_seq(vector<int> &seq) {if(seq.size() <= 1) {return seq.size();}int max_len = 1;int i;for (i = 1; i < seq.size()-1; ++i) {if(seq[i-1] > seq[i] && seq[i] < seq[i+1]) { //满足递减转折时max_len ++;} else if(seq[i-1] < seq[i] && seq[i] > seq[i+1]) {//满足递增转折时max_len ++;}}/*handle the last element*/if(seq[i-2] > seq[i-1] && seq[i-1] < seq[i]) {max_len ++;} else if(seq[i-2] < seq[i-1] && seq[i-1] > seq[i]) {max_len ++;}return max_len;
}
实现算法：方法二
状态机的方式：
/*state machine: BEGIN,UP,DOWN*/
int get_swing_seq2(vector<int> &seq) {if(seq.size() <= 1) {return seq.size();}static const int BEGIN = 0;static const int UP = 1;static const int DOWN = 2;int STATE = BEGIN;int max_len = 1;for (int i = 1;i < seq.size(); ++i) {switch (STATE){case BEGIN:if(seq[i-1] > seq[i]) {STATE = DOWN;max_len ++;} else if (seq[i-1] < seq[i]) {STATE = UP;max_len ++;}break;case UP:if(seq[i-1] > seq[i]) {STATE = DOWN;max_len ++;}break;case DOWN:if(seq[i-1] < seq[i]) {STATE = UP;max_len ++;}break;default:break;}}return max_len;
}
实现算法：打印摇摆序列
/*if..else if .. else; return the result seq */
vector<int> get_swing_seq3(vector<int> &seq) {if(seq.size() <= 1) {return seq;}vector<int> seq_result;int i;seq_result.push_back(seq[0]);for (i = 1; i < seq.size()-1; ++i) {if(seq[i-1] > seq[i] && seq[i] < seq[i+1]) {seq_result.push_back(seq[i]);} else if(seq[i-1] < seq[i] && seq[i] > seq[i+1]) {seq_result.push_back(seq[i]);}}/*handle the last element*/if(seq[i-2] > seq[i-1] && seq[i-1] < seq[i]) {seq_result.push_back(seq[i]);} else if(seq[i-2] < seq[i-1] && seq[i-1] > seq[i]) {seq_result.push_back(seq[i]);}return seq_result;
}
测试代码：
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;/*if..else if .. else */
int get_swing_seq(vector<int> &seq) {if(seq.size() <= 1) {return seq.size();}int max_len = 1;int i;for (i = 1; i < seq.size()-1; ++i) {if(seq[i-1] > seq[i] && seq[i] < seq[i+1]) {max_len ++;} else if(seq[i-1] < seq[i] && seq[i] > seq[i+1]) {max_len ++;}}/*handle the last element*/if(seq[i-2] > seq[i-1] && seq[i-1] < seq[i]) {max_len ++;} else if(seq[i-2] < seq[i-1] && seq[i-1] > seq[i]) {max_len ++;}return max_len;
}/*if..else if .. else; return the result seq */
vector<int> get_swing_seq3(vector<int> &seq) {if(seq.size() <= 1) {return seq;}vector<int> seq_result;int i;seq_result.push_back(seq[0]);for (i = 1; i < seq.size()-1; ++i) {if(seq[i-1] > seq[i] && seq[i] < seq[i+1]) {seq_result.push_back(seq[i]);} else if(seq[i-1] < seq[i] && seq[i] > seq[i+1]) {seq_result.push_back(seq[i]);}}/*handle the last element*/if(seq[i-2] > seq[i-1] && seq[i-1] < seq[i]) {seq_result.push_back(seq[i]);} else if(seq[i-2] < seq[i-1] && seq[i-1] > seq[i]) {seq_result.push_back(seq[i]);}return seq_result;
}/*state machine: BEGIN,UP,DOWN*/
int get_swing_seq2(vector<int> &seq) {if(seq.size() <= 1) {return seq.size();}static const int BEGIN = 0;static const int UP = 1;static const int DOWN = 2;int STATE = BEGIN;int max_len = 1;for (int i = 1;i < seq.size(); ++i) {switch (STATE){case BEGIN:if(seq[i-1] > seq[i]) {STATE = DOWN;max_len ++;} else if (seq[i-1] < seq[i]) {STATE = UP;max_len ++;}break;case UP:if(seq[i-1] > seq[i]) {STATE = DOWN;max_len ++;}break;case DOWN:if(seq[i-1] < seq[i]) {STATE = UP;max_len ++;}break;default:break;}}return max_len;
}int main(){vector<int> seq;int tmp;cout << "input seq " << endl;for (int i = 0;i < 10; ++i) {cin >> tmp;seq.push_back(tmp);}cout << "max of the swing seq len is " << get_swing_seq2(seq) << endl;vector<int> result = get_swing_seq3(seq);cout << "max of the swing seq is ";for (int i = 0;i < result.size(); ++i){cout << result[i] << " ";}return 0;
}
输出如下:
input seq
1 17 5 10 13 15 10 5 16 8
max of the swing seq len is 7
max of the swing seq is 1 17 5 15 5 16 8
相关文章：
php 腾讯云实时音视频,腾讯云视频 -实时音视频学习日志
1、实时音视频功能h5只支持ios2、不能主动拉人建群3、pc端的demo研究整体流程可以按照腾讯音视频上面指导的步骤走，申请账号，创建应用，购买套餐。购买好套餐后然后记录sdkappid、accountType。下载密钥。在开发辅助里面有个签名(UserSig)生成…
juery mobile select下来菜单选项提交form问题
注意： data-native-menu"false" 虽然具有渲染作用，但是无法进行js提交。 <script type"text/javascript"> $(function() { $("#category").change(function() { loadData(); }); }); function loadData(){ documen…
android GridView item中组件获取焦点
2019独角兽企业重金招聘Python工程师标准>>> 项目中在使用GridView控件时，里面的item有imageView、buttion等子控件。 但是GridView默认焦点是让item获取焦点，所以要使子控件获取焦点的话，要在gridview的属性中设置： …
Login failed for user 'NT AUTHORITY\SYSTEM'. 原因: 无法打开明确指定的数据库。异常处理...
公司一台SQL Server服务器一直报 "Login failed for user NT AUTHORITY\SYSTEM. 原因: 无法打开明确指定的数据库。"错误，按网上所讲的正常的处理方式都没有解决。 最后是发现一个公司内部人员写的服务造成的，将服务停用即可。转载于:https://…
n-netstat 查看网络状态命令
文章目录前言语法格式输出含义使用实例列出端口占用情况 (包括监听和未监听的)列出所有处于监听状态的 Sockets显示每个协议的统计信息在 netstat 输出中显示 PID 和进程名称在 netstat 输出中不显示主机，端口和用户名 (host, port or user)持续输出 netstat 信息显…
php win memcached 5.4,CentOS 5.4下Memcache的安装步骤(Linux+Nginx+PHP+Memcached) 电脑维修技术网...
一、源码包准备服务器端主要是安装memcache服务器端，目前的最新版本是 memcached-v1.4.4 。下载：http://memcached.googlecode.com/files/memcached-1.4.4.tar.gz另外，Memcache用到了libevent这个库用于Socket的处理，所以还需要安…
LomoX 桌面UI框架更新，增加资源管理
修改： 1.增加lxoption工具类，提供启动的兼容，兼容旧版的，并支持注册资源启动 （蔡东赟）兼容启动项目：main.lx //资源包默认现在用 qrc:/pack/main.html 后面评估，或者等编辑器出来mai…
Python 数据类型：列表
一、列表介绍 1. 列表可以存储一系列的值，使用中括号来定义，每个元素之间用逗号隔开，形如 [a, b, c, d]2. 列表与元组的区别是：列表中的元素是可变的，元组中的元素是不可变的 In [1]: list1 [] # 定义一个空列…
贪心：remove K digits移除K个数字
问题描述： 已知一个使用字符串表示的非负整数num，将num中的k个数字移 除，求移除k个数字后，可以获得的最小的可能的新数字。 例如：num “1432219” , k 3 在去掉3个数字后得到的很多很多可能里，如1432、43…
oracle 分组排序 update,oracle分组排序
oracle 分组排序：这个麻烦：SELECT * FROM (SELECT deptno,ename,sal,ROW_NUMBER() OVER (PARTITION BY deptno ORDER BY sal DESC ) Top3 FROM emp)WHERE Top3 < 3开窗函数也ok：代码简单点：where 11 and status2JOIN( select p…
QLocalServer与QLocalSocket进程通讯
在Qt中，提供了多种IPC方法，作者所用的是QLocalServer和QLocalSocket。看起来好像和Socket搭上点边，实则底层是windows的name pipe。这应该是支持双工通信的。一 QLocalServer#ifndef VXMAINWINDOW_H#define VXMAINWINDOW_H#include <QWidg…
JDBC编程步骤
JDBC编程步骤 JDBC编程大致按如下步骤进行： （1）加载数据库驱动。通常我们使用Class类的forName静态方法来加载驱动。例如如下代码： Class.forName(driverClass) driverClass就是数据库驱动类所对应的字符串 例如加载…
（13）中值滤波和双边滤波
其实中值滤波，就是那九个数值，进行排序，选择中间的数值来代替那九个数的中间位置的值，然后再从左到右，从上到下，这样移动运算 下面是均值滤波和高斯滤波的基础知识 中值滤波基础知识 运用中值滤波&a…
贪心：Jump Game 跳跃游戏
一个数组存储了非负整型数据，数组中的第i个元素a[i]，代表了可以从数组第i个 位置最多向前跳跃a[i]步;已知数组各元素的情况下，求是否可以从数组的第0个位置跳跃到数组的最后一个元素的位置，返回是true或者false判断是否能够跳跃到…
MFC之按键消息（长按处理）
想要实现长按键的一些控制，查了查可以通过捕获键盘事件，然后处理按键时需要进行的操作。下面简单的实现左右按键界面更新数值加减。 1. 重载PreTranslateMessage(MSG* pMsg)函数，在函数中捕获键盘事件并处理响应： BOOL CEditTestD…
服务器oracle11g卸载,卸载Oracle11g步骤详解
卸载Oracle11g步骤详解用Oracle自带的卸载程序不能从根本上卸载Oracle，从而为下次的安装留下隐患，那么怎么才能完全卸载Oracle呢？那就是直接注册表清除，步骤如下：1、 开始－>设置－>控制面板…
Fedora下配置网卡
第一次在fedora下配置静态网卡，首先去网络管理里面添加并设置网卡的IP，子网掩码和默认网关出口，然后保存即可， 也可以在 /etc/sysconfig/network-scripts/ifcfg-eth0 中直接添加这些信息，对应的为网卡的IP，…
echarts相关设置
1.显示隐藏工具栏 注释toolbox即可 /* toolbox: {show : true,feature : {dataView : {show: true, readOnly: false},magicType : {show: true, type: [line, bar]},restore : {show: true},saveAsImage : {show: true}}},*/ 2.鼠标划过数据显示对应的数据 tooltip : {trig…
贪心：jump 游戏（获取最少跳跃的次数以及跳跃路径）
一个数组存储了非负整型数据，数组中的第i个元素a[i]，代表了可以从数组第i个 位置最多向前跳跃a[i]步;已知数组各元素的情况下，求是否可以从数组的第0个位置跳跃到数组的最后一个元素的位置，返回最少跳跃的次数以及跳跃过程的路径&…
ADO.NET事务
在发布System.Transaction命名空间之前，可以直接用ADO.NET创建事务，也可以通过组件、特性和COM运行库（位于System.EnterpriseServices命名空间中）进行事务处理。本文如题所示，介绍在这些传统事务处理方式中较为简单的“…
oracle表中怎么去重复,oracle去掉表重复数据
今天在做项目过程中，碰到数据库表存在重复记录，显示的时候需要去掉重复的数据。想了老半天，最终用rank() over (partition by 分组字段 order by 排序字段 顺序)解决了此问题。一、首先介绍下rank() over (partition by 分组字段 order by 排…
JavaIO操作(1)字节流和字符流-1
3.2、字节流和字符流（核心） 使用File类执行的所有操作都是针对于文件本身，但是却没有针对于文件的内容，而要进行文件内容操作就需要通过Java之中提供的两组类完成： 字节操作流（是在JDK 1.0的时候定义的&am…
7min到40s：SpringBoot 启动优化实践
然后重点排查这些阶段的代码。先看下。
SpringBoot系列教程之Bean之指定初始化顺序的若干姿势
之前介绍了@Order注解的常见错误理解，它并不能指定 bean 的加载顺序，那么问题来了，如果我需要指定 bean 的加载顺序，那应该怎么办呢？本文将介绍几种可行的方式来控制 bean 之间的加载顺序。
在Java中使用WebSocket
WebSocket是一种协议，用于在Web应用程序和服务器之间建立实时、双向的通信连接。它通过一个单一的TCP连接提供了持久化连接，这使得Web应用程序可以更加实时地传递数据。WebSocket协议最初由W3C开发，并于2011年成为标准。
3种方案，模拟两个线程抢票
在多线程编程中，资源竞争是一个常见的问题。资源竞争发生在多个线程试图同时访问或修改共享资源时，可能导致数据不一致或其他并发问题。在模拟两个线程抢票的场景中，我们需要考虑如何公平地分配票，并确保每个线程都有机会成功获取票。本篇文章将通过三种方式来模拟两个线程抢票的过程，以展示不同的并发控制策略。使用 Synchronized 来确保一次只有一个线程可以访问票资源。使用 ReentrantLock 来实现线程间的协调。使用 Semaphore 来限制同时访问票的线程数量。
初级七 委托与事件
1.委托是一种类型，定义委托后想要实现他需要实例化，而事件其实就是委托的一个实例，加了event修饰； 委托实例化可以在 2.委托的作用：可以作为函数的参数传递； 无委托无异步； 委托主要是用来解耦 …
r-route 命令 显示/配置ip路由表
文章目录前言语法格式命令使用输出含义使用实例前言 route命令用于显示和配置IP路由表，在不同节点间的网络通信，想要实现同一局域网之间的通信就需要交换机，不同局域网之间的通信就需要路由器。而路由器的存在是为了提供NAT转换，…
suse oracle 12c安装,用半行代码实现在LINUX(SUSE/RH)下安装ORACLE 12C
最近新到单位的朋友总是抱怨在LINUX下安装ORACLE，实在是太麻烦了，而且这些步骤既不知是什么意思，也记不住；索性，我就分析了一下，经过实践，实现了只用半行代码(确切的说，只消4个字母)…
shell--数组的定义/访问/赋值/遍历
1 #!/bin/bash2 # 数组3 4 # 数组的定义5 a(0 1 2 3)6 # 数组元素的访问7 echo "a[0]:${a[0]}"8 # 数组的长度9 echo "length:${#a[*]}" 10 # 所有元素 11 echo "all element:${a[*]}" 12 # 删除某个元素 13 unset a[1] 14 echo "after uns…