h*****g 发帖数: 312 | 1 9.7 A circus is designing a tower routine consisting of people standing atop
one another’s shoulders. For practical and aesthetic reasons, each person
must be both shorter and lighter than the person below him or her. Given the
heights and weights of each person in the circus, write a method to compute
the largest possible number of people in such a tower.
EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: (56,
90) (60,95) (65,100) (68,110) (70,150) (75,190)
pg 66
1 public class Question {
2 ArrayList items;
3 ArrayList lastFoundSeq;
4 ArrayList maxSeq;
5
6 // Returns longer sequence
7 ArrayList seqWithMaxLength(ArrayList seq1,
8 ArrayList seq2) {
9 return seq1.size() > seq2.size() ? seq1 : seq2;
10 }
11
12 // Fills next seq w decreased wts&returns index of 1st unfit item.
13 int fillNextSeq(int startFrom, ArrayList seq) {
14 int firstUnfitItem = startFrom;
15 if (startFrom < items.size()) {
16 for (int i = 0; i < items.size(); i++) {
17 HtWt item = items.get(i);
18 if (i == 0 || items.get(i-1).isBefore(item)) {
19 seq.add(item);
20 } else {
21 firstUnfitItem = i;
22 }
23 }
24 }
25 return firstUnfitItem;
26 }
27
28 // Find the maximum length sequence
29 void findMaxSeq() {
30 Collections.sort(items);
31 int currentUnfit = 0;
32 while (currentUnfit < items.size()) {
33 ArrayList nextSeq = new ArrayList();
34 int nextUnfit = fillNextSeq(currentUnfit, nextSeq);
35 maxSeq = seqWithMaxLength(maxSeq, nextSeq);
36 if (nextUnfit == currentUnfit) break;
37 else currentUnfit = nextUnfit;
38 }
39 }
40 }
currentUnfit 和 nextUnfit 是干什么用的呢?判断它俩相等有何意义?
多谢 | r********r 发帖数: 2912 | 2 I think the solution is wrong. The longest subsequence algorithm given on
wikipedia works.
For instance, the sequence is
40 70 50 60
Starting from 40, the solution can only detect two increasing subsequence
40 70 and 50 60 that are not longest
atop
person
the
compute
,
【在 h*****g 的大作中提到】 : 9.7 A circus is designing a tower routine consisting of people standing atop : one another’s shoulders. For practical and aesthetic reasons, each person : must be both shorter and lighter than the person below him or her. Given the : heights and weights of each person in the circus, write a method to compute : the largest possible number of people in such a tower. : EXAMPLE: : Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) : Output: The longest tower is length 6 and includes from top to bottom: (56, : 90) (60,95) (65,100) (68,110) (70,150) (75,190) : pg 66
| h*****g 发帖数: 312 | 3 9.7 A circus is designing a tower routine consisting of people standing atop
one another’s shoulders. For practical and aesthetic reasons, each person
must be both shorter and lighter than the person below him or her. Given the
heights and weights of each person in the circus, write a method to compute
the largest possible number of people in such a tower.
EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: (56,
90) (60,95) (65,100) (68,110) (70,150) (75,190)
pg 66
1 public class Question {
2 ArrayList items;
3 ArrayList lastFoundSeq;
4 ArrayList maxSeq;
5
6 // Returns longer sequence
7 ArrayList seqWithMaxLength(ArrayList seq1,
8 ArrayList seq2) {
9 return seq1.size() > seq2.size() ? seq1 : seq2;
10 }
11
12 // Fills next seq w decreased wts&returns index of 1st unfit item.
13 int fillNextSeq(int startFrom, ArrayList seq) {
14 int firstUnfitItem = startFrom;
15 if (startFrom < items.size()) {
16 for (int i = 0; i < items.size(); i++) {
17 HtWt item = items.get(i);
18 if (i == 0 || items.get(i-1).isBefore(item)) {
19 seq.add(item);
20 } else {
21 firstUnfitItem = i;
22 }
23 }
24 }
25 return firstUnfitItem;
26 }
27
28 // Find the maximum length sequence
29 void findMaxSeq() {
30 Collections.sort(items);
31 int currentUnfit = 0;
32 while (currentUnfit < items.size()) {
33 ArrayList nextSeq = new ArrayList();
34 int nextUnfit = fillNextSeq(currentUnfit, nextSeq);
35 maxSeq = seqWithMaxLength(maxSeq, nextSeq);
36 if (nextUnfit == currentUnfit) break;
37 else currentUnfit = nextUnfit;
38 }
39 }
40 }
currentUnfit 和 nextUnfit 是干什么用的呢?判断它俩相等有何意义?
多谢 | r********r 发帖数: 2912 | 4 I think the solution is wrong. The longest subsequence algorithm given on
wikipedia works.
For instance, the sequence is
40 70 50 60
Starting from 40, the solution can only detect two increasing subsequence
40 70 and 50 60 that are not longest
atop
person
the
compute
,
【在 h*****g 的大作中提到】 : 9.7 A circus is designing a tower routine consisting of people standing atop : one another’s shoulders. For practical and aesthetic reasons, each person : must be both shorter and lighter than the person below him or her. Given the : heights and weights of each person in the circus, write a method to compute : the largest possible number of people in such a tower. : EXAMPLE: : Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) : Output: The longest tower is length 6 and includes from top to bottom: (56, : 90) (60,95) (65,100) (68,110) (70,150) (75,190) : pg 66
| d*******u 发帖数: 186 | 5 sort according to height (ht), find the longest increasing sequence of
weight (wt).
atop
person
the
compute
,
【在 h*****g 的大作中提到】 : 9.7 A circus is designing a tower routine consisting of people standing atop : one another’s shoulders. For practical and aesthetic reasons, each person : must be both shorter and lighter than the person below him or her. Given the : heights and weights of each person in the circus, write a method to compute : the largest possible number of people in such a tower. : EXAMPLE: : Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) : Output: The longest tower is length 6 and includes from top to bottom: (56, : 90) (60,95) (65,100) (68,110) (70,150) (75,190) : pg 66
| d*******u 发帖数: 186 | 6 sort according to height (ht), find the longest increasing sequence of
weight (wt).
atop
person
the
compute
,
【在 h*****g 的大作中提到】 : 9.7 A circus is designing a tower routine consisting of people standing atop : one another’s shoulders. For practical and aesthetic reasons, each person : must be both shorter and lighter than the person below him or her. Given the : heights and weights of each person in the circus, write a method to compute : the largest possible number of people in such a tower. : EXAMPLE: : Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) : Output: The longest tower is length 6 and includes from top to bottom: (56, : 90) (60,95) (65,100) (68,110) (70,150) (75,190) : pg 66
| z******t 发帖数: 59 | 7 可以先按照升高排序,然后求体重的最长递增子序列。
在下面的博客中,有关于求最长递增子序列长度的详细分析以及代码:
http://codercareer.blogspot.com/2011/10/no-16-maximum-length-of
可以参考。
atop
person
the
compute
,
【在 h*****g 的大作中提到】 : 9.7 A circus is designing a tower routine consisting of people standing atop : one another’s shoulders. For practical and aesthetic reasons, each person : must be both shorter and lighter than the person below him or her. Given the : heights and weights of each person in the circus, write a method to compute : the largest possible number of people in such a tower. : EXAMPLE: : Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) : Output: The longest tower is length 6 and includes from top to bottom: (56, : 90) (60,95) (65,100) (68,110) (70,150) (75,190) : pg 66
| d*******l 发帖数: 338 | 8 如果身高存在相同的话,不能直接用典型的方法求LIS,需要做一些改动
【在 z******t 的大作中提到】 : 可以先按照升高排序,然后求体重的最长递增子序列。 : 在下面的博客中,有关于求最长递增子序列长度的详细分析以及代码: : http://codercareer.blogspot.com/2011/10/no-16-maximum-length-of : 可以参考。 : : atop : person : the : compute : ,
| z******t 发帖数: 59 | 9 排序规则改成:
先按身高排序,如果身高相同,在根据体重排序。
这样是不是就可以了?
【在 d*******l 的大作中提到】 : 如果身高存在相同的话,不能直接用典型的方法求LIS,需要做一些改动
| d*******l 发帖数: 338 | 10 这么排序是没错,但算LIS的时候还是要注意,对每个元素只考虑前面身高更矮的
【在 z******t 的大作中提到】 : 排序规则改成: : 先按身高排序,如果身高相同,在根据体重排序。 : 这样是不是就可以了?
| r****r 发帖数: 37 | | z***e 发帖数: 209 | 12 书里一些的问题,比如这道,大概没搞清楚原题是什么.
感觉是根据自己的认为解体思路,一边解释,一边加限制条件. |
|