文档章节

叠罗汉

一贱书生
 一贱书生
发布于 2016/11/24 08:48
字数 505
阅读 1
收藏 0
点赞 0
评论 0

/**
 * 功能:有个马戏团正在设计叠罗汉的表演节目,一个人要站在另一个人的肩膀上。出于实际和美观的考虑,在上面的人一定要比下面的人矮一点、轻一点。
 * 已知马戏团每个人的身高和体重,计算叠罗汉最多能够叠几个人。

 */

 

[java] view plain copy

 

  1. /** 
  2.  * 思路:去掉细枝末节,真正的题目是:给定一个列表,每个元素由一对项目组成。找出最长的子序列,其中第一项和第二项均以非递减的顺序排列。 
  3.  * 1、子问题:最长递增子序列:找出以元素i结尾的最长递增子序列。 
  4.  *           以A[i]结尾的最长子序列可以通过检查先前全部解法得出,只要将A[i]附加到最长且“有效”的那个序列即可。有效指A[i]>list.tail的任意序列。 
  5.  * 2、真正的子问题;最长递增子序列,每个元素均为一对数据。 
  6.  * @param items 
  7.  * @return 
  8.  */  
  9. public static ArrayList<Actor> getIncreasingSequence(ArrayList<Actor> items){  
  10.     Collections.sort(items);  
  11.     return longestIncreasingSubsequence(items);  
  12. }  
  13.   
  14. public static ArrayList<Actor> longestIncreasingSubsequence(ArrayList<Actor> array) {  
  15.     // TODO Auto-generated method stub  
  16.     ArrayList<Actor>[] solutions=new ArrayList[array.size()];  
  17.     longestIncresingSubsequence(array,solutions,0);  
  18.       
  19.     ArrayList<Actor> bestSequence=new ArrayList<Actor>();  
  20.     for(ArrayList<Actor> sol:solutions){  
  21.         bestSequence=seqWithMaxLength(bestSequence,sol);  
  22.     }  
  23.       
  24.     return bestSequence;  
  25. }  
  26.   
  27. public static void longestIncresingSubsequence(ArrayList<Actor> array,ArrayList<Actor>[] solutions, int currentIndex) {  
  28.     // TODO Auto-generated method stub  
  29.     if(currentIndex>=solutions.length||currentIndex<0)  
  30.         return;  
  31.       
  32.     Actor currentElement=array.get(currentIndex);  
  33.       
  34.     //找出可以附加currentElement的最长子序列  
  35.     ArrayList<Actor> bestSequence=new ArrayList<Actor>();  
  36.     for(int i=0;i<currentIndex;i++){  
  37.         if(array.get(i).isBefore(currentElement))  
  38.             bestSequence=seqWithMaxLength(bestSequence, solutions[i]);  
  39.     }  
  40.       
  41.     //附加currentElement  
  42.     ArrayList<Actor> newSolution=new ArrayList<Actor>();  
  43.     if(bestSequence!=null)  
  44.         newSolution.addAll(bestSequence);  
  45.     newSolution.add(currentElement);  
  46.       
  47.     //加入到列表中,然后递归  
  48.     solutions[currentIndex]=newSolution;  
  49.     longestIncresingSubsequence(array, solutions, currentIndex+1);  
  50.       
  51. }  
  52.   
  53. //返回较长的序列  
  54. public static ArrayList<Actor> seqWithMaxLength(ArrayList<Actor> seq1, ArrayList<Actor> seq2) {  
  55.     // TODO Auto-generated method stub  
  56.     if(seq1==null)  
  57.         return seq2;  
  58.     if(seq2==null)  
  59.         return seq1;  
  60.     return seq1.size()>seq2.size()?seq1:seq2;  
  61. }  

 

[java] view plain copy

 

  1. class Actor implements Comparable{  
  2.     int height;  
  3.     int weight;  
  4.       
  5.     @Override  
  6.     public int compareTo(Object s) {  
  7.         // TODO Auto-generated method stub  
  8.         Actor second=(Actor) s;  
  9.         if(this.height!=second.height)  
  10.             return ((Integer)this.height).compareTo(second.height);  
  11.         else   
  12.             return ((Integer)this.weight).compareTo(second.weight);  
  13.     }  
  14.       
  15.     public boolean isBefore(Actor other){  
  16.         if(this.height<other.height&&this.weight<other.weight)  
  17.             return true;  
  18.         return false;  
  19.     }  
  20.       
  21. }

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 722
码字总数 600072
作品 0
创新梦工厂笔试题2013年校园招聘

时间:2012年9月27日 地点:鼎好大厦10层 考试时长:1小时 一, 选择题 1,求z的结果 1 [cpp] view plaincopyprint?23 #define N 3 4 #define Y(n) ((N+1)*n) 5 z = 2*(N+Y(5+1)); 解答:4...

夏雪冬日
2012/12/13
0
0
快速学习ggplot2

R语言里面一个比较重要的绘图包——ggplot2,是由Hadley Wickham于2005年创建,于2012年四月进行了重大更新,作者目前的工作是重写代码,简化语法,方便用户开发和使用。ggplot2的核心理念是...

wzgl__wh
2016/07/15
0
0
Hinton神经网络公开课16 Recent applications of deep neural nets

目录 学习图像和标题的联合模型 组合3个RBM形成DBM Hierarchical coordinate frames 为何CNN注定要完 The hierarchical coordinate frame approach Two layers in a hierarchy of parts pose......

码农场
2017/06/05
0
0
电子垃圾回收处置 蛋糕虽大为何难啃?

乔布斯将“计划性淘汰”推向了一个新高度。随着IPhone5S等诸多产品的推出,尽管用了一年的智能手机完好无损,市民王先生再次排起长龙去购买最新手机。 像王先生这样的消费者不在少数,来自中...

qq_41892675
05/07
0
0
多隆:从工程师到合伙人 | 阿里技术人纪录片

你简单,世界就会跟着简单。 冬意深浓之际,我们一起走进阿里合伙人多隆的技术世界。 “去了,还是写代码的吗?” 2003年初春,杭州空气多了一丝暖意。10分钟前,还在电脑前写代码的小伙子,...

安和林
2017/12/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多
OSChina 周一乱弹 —— 如果是你喜欢的女同学找你借钱

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @guanglun :分享Michael Learns To Rock的单曲《Fairy Tale》 《Fairy Tale》- Michael Learns To Rock 手机党少年们想听歌,请使劲儿戳(这...

小小编辑
42分钟前
11
3
NNS域名系统之域名竞拍

0x00 前言 其实在官方文档中已经对域名竞拍的过程有详细的描述,感兴趣的可以移步http://doc.neons.name/zh_CN/latest/nns_protocol.html#id30 此处查阅。 我这里主要对轻钱包开发中会用到的...

暖冰
今天
0
0
32.filter表案例 nat表应用 (iptables)

10.15 iptables filter表案例 10.16/10.17/10.18 iptables nat表应用 10.15 iptables filter表案例: ~1. 写一个具体的iptables小案例,需求是把80端口、22端口、21 端口放行。但是,22端口我...

王鑫linux
今天
0
0
shell中的函数&shell中的数组&告警系统需求分析

20.16/20.17 shell中的函数 20.18 shell中的数组 20.19 告警系统需求分析

影夜Linux
今天
0
0
Linux网络基础、Linux防火墙

Linux网络基础 ip addr 命令 :查看网口信息 ifconfig命令:查看网口信息,要比ip addr更明了一些 centos 7默认没安装ifconfig命令,可以使用yum install -y net-tools命令来安装。 ifconfig...

李超小牛子
今天
1
0
[机器学习]回归--Decision Tree Regression

CART决策树又称分类回归树,当数据集的因变量为连续性数值时,该树算法就是一个回归树,可以用叶节点观察的均值作为预测值;当数据集的因变量为离散型数值时,该树算法就是一个分类树,可以很...

wangxuwei
昨天
1
0
Redis做分布式无锁CAS的问题

因为Redis本身是单线程的,具备原子性,所以可以用来做分布式无锁的操作,但会有一点小问题。 public interface OrderService { public String getOrderNo();} public class OrderRe...

算法之名
昨天
11
0
143. Reorder List - LeetCode

Question 143. Reorder List Solution 题目大意:给一个链表,将这个列表分成前后两部分,后半部分反转,再将这两分链表的节点交替连接成一个新的链表 思路 :先将链表分成前后两部分,将后部...

yysue
昨天
1
0
数据结构与算法1

第一个代码,描述一个被称为BankAccount的类,该类模拟了银行中的账户操作。程序建立了一个开户金额,显示金额,存款,取款并显示余额。 主要的知识点联系为类的含义,构造函数,公有和私有。...

沉迷于编程的小菜菜
昨天
1
0
从为什么别的队伍总比你的快说起

在机场候检排队的时候,大多数情况下,别的队伍都要比自己所在的队伍快,并常常懊悔当初怎么没去那个队。 其实,最快的队伍只能有一个,而排队之前并不知道那个队快。所以,如果有六个队伍你...

我是菜鸟我骄傲
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部