文档章节

Problem Statement for ZigZag

WuXueyang
 WuXueyang
发布于 2014/03/03 22:38
字数 326
阅读 163
收藏 0

Problem Statement



A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag 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 zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

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



Definition



Class: ZigZag
Method: longestZigZag
Parameters: int[]
Returns: int
Method signature: int longestZigZag(int[] sequence)
(be sure your method is public)






Constraints


- sequence contains between 1 and 50 elements, inclusive.
- Each element of sequence is between 1 and 1000, inclusive.


Examples


0)

{ 1, 7, 4, 9, 2, 5 }
Returns: 6
The entire sequence is a zig-zag sequence.
1)

{ 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }
Returns: 7
There are several subsequences that achieve this length. One is 1,17,10,13,10,16,8.
2)

{ 44 }
Returns: 1

3)

{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }
Returns: 2

4)

{ 70, 55, 13, 2, 99, 2, 80, 80, 80, 80, 100, 19, 7, 5, 5, 5, 1000, 32, 32 }
Returns: 8

5)

{ 374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 
600, 947, 978, 46, 100, 953, 670, 862, 568, 188,
67, 669, 810, 704, 52, 861, 49, 640, 370, 908,
477, 245, 413, 109, 659, 401, 483, 308, 609, 120,
249, 22, 176, 279, 23, 22, 617, 462, 459, 244 }
Returns: 36


本文转载自:http://community.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493

上一篇: 14. 数据结构映射
下一篇: 13.文件I/O简介
WuXueyang
粉丝 1
博文 44
码字总数 31678
作品 0
闵行
私信 提问
[leetcode] ZigZag Conversion

The string"PAYPALISHIRING"is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H ......

jdflyfly
2014/06/24
72
0
Leetcode_6. Zigzag convertion

6. Zigzag convertion 对输入的字符串做锯齿形变换,并输出新的字符串,所谓zigzag变化如下图所示。 将"ABCDEFGHIJKL"做4行的锯齿变换,新的字符串为:AGBFHLCEIKDJ" 实现一个根据输入字符串...

gexin1023
2018/06/28
0
0
[LeetCode] Zigzag Iterator 之字形迭代器

Given two 1d vectors, implement an iterator to return their elements alternately. For example, given two 1d vectors: v1 = [1, 2]v2 = [3, 4, 5, 6] By calling next repeatedly unti......

机器的心脏
2017/12/15
0
0
LeetCode-ZigZag conversion

Zigzag Conversion Solution mind path We can notice that it has a pattern. Every zigzag pattern is composed by a list of structures.As of example 2, Let's write the zigzag positi......

Quan全
2018/07/10
23
0
编码原理详解(五)---熵编码(CAVAL)

上一篇我们讲到了ZigZag扫描,经过这一扫描之后,发现原本是4*4的像素矩阵,就变成了一连串的数字,可以说是二维到一维的一个转换吧,而且经过ZigZag扫描后,一连串的数字的最后大部分为0,以...

mmlf
2018/02/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

查看线上日志常用命令

cat 命令(文本输出命令) 通常查找出错误日志 cat error.log | grep 'nick' , 这时候我们要输出当前这个日志的前后几行: 显示file文件里匹配nick那行以及上下5行 cat error.log | grep -C ...

xiaolyuh
35分钟前
5
0
六、Java设计模式之工厂方法

工厂方法定义: 定义一个创建对象的接口,但让实现这个接口的类来决定实例化哪个类,工厂方法让类的实例化推迟到子类中进行 类型:创建型 工厂方法-使用场景: 创建对象需要大量重复的代码 ...

东风破2019
42分钟前
5
0
win服务器管理遇到的一系列问题记录

有些小伙伴在使用iis7远程桌面管理工具的时候总是会遇到一系列的问题,下面就是为大家介绍一下服务器日常管理过程中出现的问题及我的解决办法和心得。希望能帮到大家。   拒绝服务器重新启...

1717197346
49分钟前
6
0
flutter 剪切板 复制粘贴

复制粘贴功能 import 'package:flutter/services.dart'; Clipboard.setData(ClipboardData(text:_text));Clipboard.getData;...

zdglf
51分钟前
4
0
如何保证消息的可靠性传输?或者说,如何处理消息丢失的问题?

面试题 如何保证消息的可靠性传输?或者说,如何处理消息丢失的问题? 面试官心理分析 这个是肯定的,用 MQ 有个基本原则,就是数据不能多一条,也不能少一条,不能多,就是前面说的重复消费...

米兜
52分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部