文档章节

leetcode-Wiggle Subsequence-376

梦想游戏人
 梦想游戏人
发布于 2016/09/16 23:10
字数 457
阅读 89
收藏 0

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast,[1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:

Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Input: [1,2,3,4,5,6,7,8,9]
Output: 2

Follow up:
Can you do it in O(n) time?

该题贪心和DP都能做

 

贪心策略1:3个点为一个局部条件,

不满足的去掉中间那么点,只关心3个数的斜率是否满足条件,用3个数来记录下标,记录逻辑上3个评定的数字

ABC时 贪心策略去掉B,反证:如果去掉A 那么A之前的上限提高了,更不会得到更优解,C同理,因此去掉B是最优

同理ACD时去掉C,......

if (nums.size() == 0)return 0;
		if (nums.size() == 1)return 1;
		if (nums.size() == 2)
		{
			if (nums[0] == nums[1])return 1;
			return 2;
		}


		int ret = 1;
		if (nums[0] != nums[1] && nums[1] != nums[2] && nums[2] != nums[0])ret++;
		int d = nums[2] - nums[1];

		int a = 2;
		int b = 1;
		int c = 0;
		int d2 = 0;
		for (int i = 2; i < nums.size(); i++)
		{
			a = i;

			d2 = nums[b] - nums[c];
			int d1 = nums[a] - nums[b];

			if (d1*d2 < 0)
			{
				ret++;
				d = a - b;
			}
			if (d2 != 0 && d1 != 0)
			{
				c = b;//V或者倒V的情况
				b = a;
			}
			else
			{
				if (d1 == 0 && d2 != 0){  b=a; }

				if (d2 == 0 && d1 != 0){ ret++; b = a;  }
				
	

			}
		}
		return ret;

 

还有更快的方法:仔细分析策略1,3个点中,a,b可以合为一个点,点c可以记录上一次有效数字的index

if (nums.size() < 2) return nums.size();

		int p = 0, len = 1;

		for (int i = 0; i < nums.size() - 1; ++i)
		{
			if (nums[i] == nums[i + 1]) continue;

			if ((nums[i] - nums[p])*(nums[i + 1] - nums[i]) <= 0) p = i, ++len;
		}

		return len;

 

 

 

 

© 著作权归作者所有

共有 人打赏支持
梦想游戏人
粉丝 38
博文 444
码字总数 127453
作品 0
成都
私信 提问
Leetcode 376. Wiggle Subsequence

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution First Version Second Version Reference https://leetcode.com/problems/wiggle-subsequence/description/......

SnailTyan
2018/08/13
0
0
数组中最长摆动子序列 Wiggle Subsequence

问题: A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if......

叶枫啦啦
2017/12/28
0
0
leetcode-392. Is Subsequence-DP-NORMAL

Given a string s and a string t, check if s is subsequence of t. You may assume that there is only lower case English letters in both s and t. t is potentially a very long (leng......

梦想游戏人
2016/09/17
24
0
Leetcode 873:最长递增斐波那契子序列

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Flying_sfeng/article/details/82814051 Leetcode 873: Length of Longest Fibonacci Subsequence 题目要求如...

Flying_sfeng
03/03
0
0
Leetcode 674. Longest Continuous Increasing Subsequence

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Reference https://leetcode.com/problems/longest-continuous-increasing-subsequence/description/......

SnailTyan
2018/10/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

C++ vector和list的区别

1.vector数据结构 vector和数组类似,拥有一段连续的内存空间,并且起始地址不变。 因此能高效的进行随机存取,时间复杂度为o(1); 但因为内存空间是连续的,所以在进行插入和删除操作时,会造...

shzwork
52分钟前
2
0
Spring之invokeBeanFactoryPostProcessors详解

Spring的refresh的invokeBeanFactoryPostProcessors,就是调用所有注册的、原始的BeanFactoryPostProcessor。 相关源码 public static void invokeBeanFactoryPostProcessors(Configu......

cregu
昨天
3
0
ibmcom/db2express-c_docker官方使用文档

(DEPRECIATED) Please check DB2 Developer-C Edition for the replacement. What is IBM DB2 Express-C ? ``IBM DB2 Express-C``` is the no-charge community edition of DB2 server, a si......

BG2KNT
昨天
2
0
Ubuntu 18.04.2 LTS nvidia-docker2 : 依赖: docker-ce (= 5:18.09.0~3-0~ubuntu-bionic)

平台:Ubuntu 18.04.2 LTS nvidia-docker2 版本:2.0.3 错误描述:在安装nvidia-docker2的时候报dpkg依赖错误 nvidia-docker2 : 依赖: docker-ce (= 5:18.09.0~3-0~ubuntu-bionic) 先看一下依......

Pulsar-V
昨天
4
0
学习笔记1-goland结构体(struct)

写在前面:若有侵权,请发邮件by.su@qq.com告知。 转载者告知:如果本文被转载,但凡涉及到侵权相关事宜,转载者需负责。请知悉! 本文永久更新地址:https://my.oschina.net/bysu/blog/3036...

不最醉不龟归
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部