最近面试遇到这样的一个机试题
小王最近利用假期在外地旅游，在某个小镇碰到一个马戏团表演，精彩的表演结束后发现团长正和大伙在帐篷前激烈讨论，小王打听了下了解到， 马戏团正打算出一个新节目“最高罗汉塔”，即马戏团员叠罗汉表演。考虑到安全因素，要求叠罗汉过程中，站在某个人肩上的人应该既比自己矮又比自己瘦，或相 等。 团长想要本次节目中的罗汉塔叠的最高，由于人数众多，正在头疼如何安排人员的问题。小王觉得这个问题很简单，于是统计了参与最高罗汉塔表演的所有团员的身 高体重，并且很快找到叠最高罗汉塔的人员序列。 现在你手上也拿到了这样一份身高体重表，请找出可以叠出的最高罗汉塔的高度，这份表中马戏团员依次编号为1到N。
输入描述:
首先一个正整数N，表示人员个数。
之后N行，每行三个数，分别对应马戏团员编号，体重和身高。
输出描述:
正整数m，表示罗汉塔的高度。
思路分析
在这道题目中，要求就是在下边的人要比在上边的人体重重并且身高要高，或者一样。所以首先要进行一次排序，排序完之后再统计从每一个位置开始往后算，若是以此人为最底下的那个人，按照要求最高可以叠几个人，最后再取最大值。
编码
排序（需要按照考虑身高和体重两种情况）
在JDK1.8之前的排序：1
2
3
4
5
6prosonList.sort(new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
return o1.getWeight() == o2.getWeight()? o1.getHeight() - o2.getHeight():o1.getWeight() - o2.getWeight();
}
});
我们需要使用sort方法传入一个Comparator，并重写内部的compare方法，如果两人体重相等时，则根据身高排序，如果体重不相等，就直接根据体重排序
在JDK1.8我们可以用lanbda表达式对list进行排序：1
prosonList.sort(Comparator.comparingInt(Person::getHeight).thenComparingInt(Person::getWeight).reversed());
分析排序后的数据
在这时候，我们应该了解题目的几点：
1.并不是从下标为0的开始才是可以叠最高的，因为当身高较低时，对后边的有限制。
2.当后一个不符合时，并不代表后边的后边的不符合。
3.如果当前可以叠最高的长度大于剩余的长度，那么当前这个长度就是最大长度。
按照这几点我做了以下的操作：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24// 最高层数，初始为0
int len = 0;
for(int i = 0;i<prosonList.size();i++){
// 如果当前的最大层数大于剩余的长度，则直接返回len。
if(len>prosonList.size()-i){
return len;
}
// 最少层数为1
int lenTemp = 1;
// 当前起点的人的体重
int weight = prosonList.get(i).getWeight();
// 以i为起点，计算最多可以叠多少层
for(int j = i;j<prosonList.size()-1;j++){
// 如果后边的一个人的重量小于当前当前的重量，就把lenTemp加一,并把当前人的体重设为weight以供后面比较
if(weight>prosonList.get(j+1).getWeight()){
lenTemp += 1;
weight = prosonList.get(j+1).getWeight();
}
}
// 如果从i开始可以叠的层数大于从之前开始的最大的层数，则把从i开始可以叠的层数设为最大的层数
if(lenTemp>len){
len = lenTemp;
}
}
外部的循环是依次从下标为0的开始排，可以排lenTemp层，内部的循环是代表从i处开始排，当后边的体重大于当前体重时，把lenTemp加一，代表后边的可以往上爹，然后再以后边的体重为后边的后边的比较参数，以此类推，如果从i开始可以排的层数lenTemp大于len，则把lenTemp的值赋予len，如果当前的最高长度大于剩余还没有排的长度，则直接返回len，因为后边就算可以全部叠上去，那么长度也不可能超过len了。
全部代码
Person类：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
34
35
36
37
38package com.lizx.highest;
/**
* 马戏团员
*
* @date 2018/3/19 20:08:55
* @auther Pyctay
*/
public class Person {
private int id;
private int height;
private int weight;
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
}
Highest: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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70package com.lizx.highest;
import java.util.*;
/**
* 最高罗汉塔
*
* @date 2018/3/19 20:10:29
* @auther Pyctay
*/
public class Highest {
public static void main(String[] args) {
ArrayList<Person> prosonList = new ArrayList<Person>();
Scanner sc = new Scanner(System.in);
Person person = null;
while (true) {
System.out.println("请输入（编号、体重、身高，以逗号分隔，结束输入请输入#end）");
String input = sc.next();
if ("#end".equals(input))
break;
String[] arr = input.split(",");
if (arr.length != 3) {
System.out.println("格式错误，请重新输入");
continue;
}
person = new Person();
person.setId(Integer.parseInt(arr[0]));
person.setWeight(Integer.parseInt(arr[1]));
person.setHeight(Integer.parseInt(arr[2]));
prosonList.add(person);
}
int len = getHighest(prosonList);
System.out.println(len);
}
/**
* 计算最高罗汉塔
* @param prosonList
* @return 最高罗汉塔层数
*/
private static int getHighest(ArrayList<Person> prosonList){
// 按照身高、体重排序（优先按照身高）
prosonList.sort(Comparator.comparingInt(Person::getHeight).thenComparingInt(Person::getWeight).reversed());
// 最高层数，初始为0
int len = 0;
for(int i = 0;i<prosonList.size();i++){
// 如果当前的最大层数大于剩余的长度，则直接返回len。
if(len>prosonList.size()-i){
return len;
}
// 最少层数为1
int lenTemp = 1;
// 当前起点的人的体重
int weight = prosonList.get(i).getWeight();
// 以i为起点，计算最多可以叠多少层
for(int j = i;j<prosonList.size()-1;j++){
// 如果后边的一个人的重量小于当前当前的重量，就把lenTemp加一,并把当前人的体重设为weight以供后面比较
if(weight>prosonList.get(j+1).getWeight()){
lenTemp += 1;
weight = prosonList.get(j+1).getWeight();
}
}
// 如果从i开始可以叠的层数大于从之前开始的最大的层数，则把从i开始可以叠的层数设为最大的层数
if(lenTemp>len){
len = lenTemp;
}
}
return len;
}
}
同时欢迎关注我的微信公众号：猿人族永不为奴。
二维码：