个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
25
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章使用java实现LIS算法,出操队形的问题由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
假设有序列：2,1,3,5，求一个最长上升子序列就是2,3,5或者1,3,5，长度都为3.
LIS算法的思想是:
设存在序列a.
① 如果只有一个元素，那么最长上升子序列的长度为1； 。
② 如果有两个元素，那么如果a[1]>a[0]，则最长上升子序列的长度为2，a[1]为该最长上升子序列的最后一个元素;若a[1]<a[0]，则最长上升子序列的长度为1，a[0]和a[1]均为 其最长上升子序列的最后一个元素.
③ 如果由三个元素，那么如果a[2]>a[0],a[2]>a[1],则a[2]可以作为a[0]或者a[1]所在最长上升子序列的最后一个元素。那选择哪一个序列就要看a[0],a[1]哪个所在的序列要更长.
④ 扩展到n个元素，就是看以a[n]为最后一个元素的最长上升子序列的长度是多少.
定义两个数组，一个是a,一个是b.
a存放原始数据，b[i]存放的是以a[i]结尾的最长上升子序列的长度.
代码如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class
Lmax{
public
static
void
Lmax(
int
[] a,
int
[] b){
b[
0
]=
1
;
for
(
int
i=
1
;i<a.length;i++){
int
countmax=
0
;
for
(
int
j=
0
;j<i;j++){
if
(a[i]>a[j]&&b[j]>countmax){
countmax=b[j];
//记录下元素数值比a[i]小的但是对应子序列最长的子序列长度
}
}
b[i]=countmax+
1
;
//a[i]对应的最长子序列长度是
}
}
}
|
2、出操队形 。
题目描述:
在 读高中的时候，每天早上学校都要组织全校的师生进行跑步来锻炼身体，每当出操令吹响时，大家就开始往楼下跑了，然后身高矮的排在队伍的前面，身高较高的就 要排在队尾。突然，有一天出操负责人想了一个主意，想要变换一下队形，就是当大家都从楼上跑下来后，所有的学生都随机地占在一排，然后出操负责人从队伍中 抽取出一部分学生，使得队伍中剩余的学生的身高从前往后看，是一个先升高后下降的“山峰”形状。据说这样的形状能够给大家带来好运，祝愿大家在学习的道路 上勇攀高峰。(注，山峰只有一边也符合条件，如1,1、2,2、1均符合条件) 。
输入:
输入可能包含多个测试样例。 对于每个测试案例，输入的第一行是一个整数n(1<=n<=1000000)：代表将要输入的学生个数。 输入的第二行包括n个整数：代表学生的身高（cm）(身高为不高于200的正整数).
输出:
对应每个测试案例，输出需要抽出的最少学生人数.
样例输入:
6 。
100 154 167 159 132 105 。
5 。
152 152 152 152 152 。
样例输出:
0 。
4 。
在用LIS来解这道题的时候，可以这样考虑:
首先从前向后用LIS求一遍以每一个元素结尾的最长上升子序列的长度，然后将数组逆序，再用LIS求一遍以每一个元素结尾的最长上升子序列的长度.
得到两个数组b1,b2.
b1,b2对应相加再减去重复的一个，就是最长的'山峰'.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
public
class
peak {
public
static
void
main (String[] args)
{
int
n;
int
re;
do
{
Scanner in =
new
Scanner(System.in);
n = in.nextInt();
}
while
(n<
0
||n>
100000
);
int
[]a =
new
int
[n];
//原始数组
int
[]ar =
new
int
[n];
//逆序数组
Scanner in =
new
Scanner(System.in);
for
(
int
i=
0
;i<n;i++){
a[i]=in.nextInt();
}
int
[] b1 =
new
int
[n];
@SuppressWarnings
(
"unused"
)
int
[] b2 =
new
int
[n];
Lmax.Lmax(a, b1);
ar=reverse.reverse(a);
Lmax.Lmax(ar, b2);
//求解逆序数组的最长上升子序列
b2=reverse.reverse(b2);
//将逆序数组的最长上升子序列逆序以便和原始数组的最长上升子序列对应相加
re = result.result(b1, b2);
System.out.print(re);
}
}<br><br><br><br>
|
|
1
2
3
4
5
6
7
8
9
10
11
12
|
class
result{
public
static
int
result(
int
[] a,
int
[] b){
int
max=
0
;
int
[] c =
new
int
[a.length];
for
(
int
i=
0
;i<a.length;i++){
c[i]=a[i]+b[i];
}
Arrays.sort(c);
max=c[c.length-
1
]-
1
;
//对应相加最长的再减去重复的一个人
return
a.length-max;
}
}
|
以上就是小编为大家带来的使用java实现LIS算法,出操队形的问题的全部内容了，希望对大家有所帮助，多多支持我~ 。
最后此篇关于使用java实现LIS算法,出操队形的问题的文章就讲到这里了,如果你想了解更多关于使用java实现LIS算法,出操队形的问题的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
25
4
0
关闭。这个问题是off-topic .它目前不接受答案。 想要改进这个问题？ Update the question所以它是on-topic用于堆栈溢出。 关闭 12 年前。 Improve thi
我有一个动态网格，其中的数据功能需要正常工作，这样我才能逐步复制网格中的数据。假设在第 5 行中，我输入 10，则从第 6 行开始的后续行应从 11 开始读取，依此类推。 如果我转到空白的第一行并输入
我有一个关于我的按钮消失的问题 我已经把一个图像作为我的按钮 用这个函数动画 function example_animate(px) { $('#cont
我有一个具有 Facebook 连接和经典用户名/密码登录的网站。目前，如果用户单击 facebook_connect 按钮，系统即可运行。但是，我想将现有帐户链接到 facebook，因为用户可以选
我有一个正在为 iOS 开发的应用程序，该应用程序执行以下操作 加载和设置注释并启动核心定位和缩放到位置。 map 上有很多注释，从数据加载不会花很长时间，但将它们实际渲染到 map 上需要一段时间。
我被推荐使用 Heroku for Ruby on Rails 托管，到目前为止，我认为我真的会喜欢它。只是想知道是否有人可以帮助我找出问题所在。 我按照那里的说明在该网站上创建应用程序，创建并提交
我看过很多关于 SSL 错误的帖子和信息，我自己也偶然发现了一个。 我正在尝试使用 GlobalSign CA BE 证书通过 Android WebView 访问网页，但出现了不可信错误。 对于大多
我想开始使用 OpenGL 3+ 和 4，但我在使用 Glew 时遇到了问题。我试图将 glew32.lib 包含在附加依赖项中，并且我已将库和 .dll 移动到主文件夹中，因此不应该有任何路径问题。
我已经盯着这两个下载页面的源代码看了一段时间，但我似乎找不到问题。 我有两个下载页面，一个 javascript 可以工作，一个没有。 工作:http://justupload.it/v/lfd7不是
我一直在使用 jQuery，只是尝试在单击链接时替换文本字段以及隐藏/显示内容项。它似乎在 IE 中工作得很好，但我似乎无法让它在 FF 中工作。 我的 jQuery: $(function() {
我正在尝试为 NDK 编译套接字库，但出现以下两个错误: error: 'close' was not declared in this scope 和 error: 'min' is not a m
我正在使用 Selenium 浏览器自动化框架测试网站。在测试过程中，我切换到特定的框架，我们将其称为“frame_1”。后来，我在 Select 类中使用了 deselectAll() 方法。不久之
我正在尝试通过 Python 创建到 Heroku PostgreSQL 数据库的连接。我将 Windows10 与 Python 3.6.8 和 PostgreSQL 9.6 一起使用。 我从“ht
我有一个包含 2 列的数据框，我想根据两列之间的比较创建第三列。 所以逻辑是:第 1 列 val = 3，第 2 列 val = 4，因此新列值什么都没有 第 1 列 val = 3，第 2 列 va
我想知道如何调试 iphone 5 中的 css 问题。 我尝试使用 firelite 插件。但是从纵向旋转到横向时，火石占据了整个屏幕。 有没有其他方法可以调试 iphone 5 中的 css 问题
所以我有点难以理解为什么这不起作用。我正在尝试替换我正在处理的示例站点上的类别复选框。我试图让它做以下事情:未选中时以一种方式出现，悬停时以另一种方式出现(选中或未选中)选中时以第三种方式出现(而不是
Javascript CSS 问题: 我正在使用一个文本框来写入一个 div。我使用以下 javascript 获取文本框来执行此操作: function process_input(){
你好，我很难理解 P、NP 和多项式时间缩减的主题。我试过在网上搜索它并问过我的一些 friend ，但我没有得到任何好的答案。 我想问一个关于这个话题的一般性问题: 设 A,B 为 P 中的语言(或
你好，我一直在研究 https://leetcode.com/problems/2-keys-keyboard/并想到了这个动态规划问题。 您从空白页上的“A”开始，完成后得到一个数字 n，页面上应该
我正在使用 Cocoapods 和 KIF 在 Xcode 服务器上运行持续集成。我已经成功地为一个项目设置了它来报告每次提交。我现在正在使用第二个项目并收到错误: Bot Issue: warnin
我是一名优秀的程序员,十分优秀！