careerup 150 上一道题 答案没看懂？# JobHunting - 待字闺中
h*g
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 是干什么用的呢？判断它俩相等有何意义？
多谢
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
3 ArrayList
4 ArrayList
5
6 // Returns longer sequence
7 ArrayList
8 ArrayList
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
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
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 是干什么用的呢？判断它俩相等有何意义？
多谢
