由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - careerup 150 上一道题 答案没看懂?
相关主题
请教careercup上的一道题G电面面经
其实我很想知道, 多少软工能45分钟内把quicksort写下来请问关于 OPT 和 H1b 大家帮忙回答2个问题
最长递增子array的算法下个月微软onsite~ 有疑问 求帮助与祝福
问个题再来一道简单的bit运算题
career cup 上9.4题答案是否正确找程序员工作吗,用我的iPhone程序吧!
Cracking Ed4里的9.7 答案有错吗?问个careerup的题
请教 Cracking the Coding Interview 上一道题Amazon has more than 200 questions in
再来cc150一问问个很有难度的矩阵算法问题
相关话题的讨论汇总
话题: htwt话题: arraylist话题: nextunfit话题: int
进入JobHunting版参与讨论
1 (共1页)
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
11
这题答案错了,应该用DP来解
参考这里的第四题:
http://people.csail.mit.edu/bdean/6.046/dp/
z***e
发帖数: 209
12
书里一些的问题,比如这道,大概没搞清楚原题是什么.
感觉是根据自己的认为解体思路,一边解释,一边加限制条件.
1 (共1页)
进入JobHunting版参与讨论
相关主题
问个很有难度的矩阵算法问题career cup 上9.4题答案是否正确
弱问一个c++编程题Cracking Ed4里的9.7 答案有错吗?
++请问哪里有database面试的题目++请教 Cracking the Coding Interview 上一道题
报个小Offer,同时分享找工作的经历再来cc150一问
请教careercup上的一道题G电面面经
其实我很想知道, 多少软工能45分钟内把quicksort写下来请问关于 OPT 和 H1b 大家帮忙回答2个问题
最长递增子array的算法下个月微软onsite~ 有疑问 求帮助与祝福
问个题再来一道简单的bit运算题
相关话题的讨论汇总
话题: htwt话题: arraylist话题: nextunfit话题: int