w********p
发帖数: 948 | 1 不好意思，很丢脸的来问一句。
9.10 you have a stack of n boxes, with widths w, height h and depth d. The
boxes can not be rotated and can only be stacked on top of one another if
each box in the stack is strictly larger than the box above it in width,
height and depth. Implement a method to build the tallest stack possible.
where the height of a stack is the sum of the heights of each box
career cup 9.10堆盒子。答案的最后一句为啥是return (ArrayList)max_stack.
clone();
一般来说，只有在会 expose internal reference object 才会用return clone() 或
者copy. 这里的max_stack 只是local变量，为什么要用clone()。而且不用的话，结果
出来是错的。谁个大牛给说说。
还有这道题career cup的解法是很笨的。不用这个，直接排序用类似longest
increasing subsequence的方法就可以了。我只是想学习下careercup的思路。
public static ArrayList createStackDP(Box[] boxes, Box bottom,
HashMap> stack_map) {
if (bottom != null && stack_map.containsKey(bottom)) {
return stack_map.get(bottom);
}
int max_height = 0;
ArrayList max_stack = null;
for (int i = 0; i < boxes.length; i++) {
if (boxes[i].canBeAbove(bottom)) {
ArrayList new_stack = createStackDP(boxes, boxes[i], stack_
map);
int new_height = stackHeight(new_stack);
if (new_height > max_height) {
max_stack = new_stack;
max_height = new_height;
}
}
}
if (max_stack == null) {
max_stack = new ArrayList();
}
if (bottom != null) {
max_stack.add(0, bottom);
}
stack_map.put(bottom, max_stack);
//*********************************Why return clone()????
return (ArrayList)max_stack.clone();
}
public static int stackHeight(LinkedList list) {
if (list == null) {
return 0;
}
int height = 0;
for ( Box box : list ) {
height += box.height;
}
return height;
} | w********p
发帖数: 948 | | c********t
发帖数: 5706 | 3 因为如果不clone, 调用他的上一层操作 add(0,bottom)就会在同一个list上操作，map
里的list也就变了。
stack.
【在 w********p 的大作中提到】
: 不好意思，很丢脸的来问一句。
: 9.10 you have a stack of n boxes, with widths w, height h and depth d. The
: boxes can not be rotated and can only be stacked on top of one another if
: each box in the stack is strictly larger than the box above it in width,
: height and depth. Implement a method to build the tallest stack possible.
: where the height of a stack is the sum of the heights of each box
: career cup 9.10堆盒子。答案的最后一句为啥是return (ArrayList)max_stack.
: clone();
: 一般来说，只有在会 expose internal reference object 才会用return clone() 或
: 者copy. 这里的max_stack 只是local变量，为什么要用clone()。而且不用的话，结果
| w********p
发帖数: 948 | 4 谢谢，一下就点醒了。
map
【在 c********t 的大作中提到】
: 因为如果不clone, 调用他的上一层操作 add(0,bottom)就会在同一个list上操作，map
: 里的list也就变了。
:
: stack.
| c********t
发帖数: 5706 | 5 不客气。
【在 w********p 的大作中提到】
: 谢谢，一下就点醒了。
:
: map
| w********p
发帖数: 948 | 6 我又想，还是没太想通。上一层操作的时候，下一层已经计算完毕。
影响不到的。
化了半天时间发现，careercup 的代码是错的。
createStackR（。。。）和 createStackDP（。。。）计算出来的结果不一样。
Box[] boxes = { new Box(1, 7, 4), new Box(2, 6, 9), new Box(4, 9, 6) , new
Box(2, 10, 16) };
createStackR（。。。）结果是对的
Box(1,7,4)
Box(2,10,16)
****************
createStackDP（。。。）结果是错的。
Box(1,7,4)
Box(4,9,6)
Box(2,10,16)
不去给他debug了。这题已经化了我太多时间。有大牛要是能fix这个bug， 就拜谢了。
createStackR （...）的code:
public static ArrayList createStackR(Box[] boxes, Box bottom) {
int max_height = 0;
ArrayList max_stack = null;
for (int i = 0; i < boxes.length; i++) {
if (boxes[i].canBeAbove(bottom)) {
ArrayList new_stack = createStackR(boxes, boxes[i]);
int new_height = stackHeight(new_stack);
if (new_height > max_height) {
max_stack = new_stack;
max_height = new_height;
}
}
}
if (max_stack == null) {
max_stack = new ArrayList();
}
if (bottom != null) {
max_stack.add(0, bottom);
}
return max_stack;
}
map
【在 c********t 的大作中提到】
: 因为如果不clone, 调用他的上一层操作 add(0,bottom)就会在同一个list上操作，map
: 里的list也就变了。
:
: stack.
| j********g
发帖数: 31 | | c********t
发帖数: 5706 | 8 我以前写的，你看看有什么问题吗？与书上有什么不同？
public static ArrayList createStack(Box[] boxes, Box bottom,
HashMap> map) {
if (map.containsKey(bottom))
return map.get(bottom);
ArrayList result = new ArrayList();
int maxLen = 0;
for (int i = 0; i < boxes.length; i++) {
if (boxes[i].canBeAbove(bottom)) {
ArrayList list = createStack(boxes, boxes[i], map);
if (list.size() > maxLen) {
maxLen = list.size();
result = list;
}
}
}
if (bottom != null) {
result = new ArrayList(result);
result.add(0, bottom);
map.put(bottom, result);
}
return result;
}
new
【在 w********p 的大作中提到】
: 我又想，还是没太想通。上一层操作的时候，下一层已经计算完毕。
: 影响不到的。
: 化了半天时间发现，careercup 的代码是错的。
: createStackR（。。。）和 createStackDP（。。。）计算出来的结果不一样。
: Box[] boxes = { new Box(1, 7, 4), new Box(2, 6, 9), new Box(4, 9, 6) , new
: Box(2, 10, 16) };
: createStackR（。。。）结果是对的
: Box(1,7,4)
: Box(2,10,16)
: ****************
| w********p
发帖数: 948 | 9 99％正确。没有书上第二解犯的错。code 很简洁。记下来，学习。
但是有个小问题导致case 结果不是100％正确。
问题处在比较上。是小问题。if (list.size() > maxLen) { maxLen = list.size();
是比较盒子累积的高度，不是盒子个数。
您的code运行结果。
Box(1,7,4)
Box(4,9,6)
****************
书上第一解的运行结果。
Box(1,7,4)
Box(2,10,16)
---------
改了一点点骑士同学的code, 就对了。但是还没明白为啥mm的是对的，职业杯的是错的。
public static ArrayList createStack(Box[] boxes, Box bottom,
HashMap> map) {
if (map.containsKey(bottom))
return map.get(bottom);
ArrayList result = new ArrayList();
int maxLen = 0;
for (int i = 0; i < boxes.length; i++) {
if (boxes[i].canBeAbove(bottom)) {
ArrayList list = createStack(boxes, boxes[i], map);
int newHeight = stackHeight(list);
if (newHeight > maxLen) {
maxLen = maxLen;
result = list;
}
}
}
if (bottom != null) {
result = new ArrayList(result);
result.add(0, bottom);
map.put(bottom, result);
}
return result;
}
突然瞥到骑士同学的签名档， 我想到的事。不求大富大贵，但求题题能做。。。
【在 c********t 的大作中提到】
: 我以前写的，你看看有什么问题吗？与书上有什么不同？
: public static ArrayList createStack(Box[] boxes, Box bottom,
: HashMap> map) {
: if (map.containsKey(bottom))
: return map.get(bottom);
: ArrayList result = new ArrayList();
: int maxLen = 0;
: for (int i = 0; i < boxes.length; i++) {
: if (boxes[i].canBeAbove(bottom)) {
: ArrayList list = createStack(boxes, boxes[i], map);
| w********p
发帖数: 948 | 10 又对比了一遍code, 大概知道问题出在哪里了。
之所以有结果如下：
Box(1,7,4)
Box(4,9,6)
Box(2,10,16)
是因为 Box(2,10,16) 比Box(1,7,4)大，所以 Box(2,10,16) 把 Box(1,7,4)的
stackmap都加上了。
if (bottom != null) {
//问题在于这句，加上就ok。
max_stack = new ArrayList(max_stack);
max_stack.add(0, bottom);
}
stack_map.put(bottom, max_stack);
return max_stack;
max_stack = new ArrayList(max_stack); 貌似是 max_stack和原答案clon
()的道理是一样的。自我拷贝下，改改地址， 挂在map上，防止上个level运算对其修
改。
书上出错，是挂到Map上以后再clone， 这个map就出错了。
再次谢谢coldknight (冷骑士) 。
【在 c********t 的大作中提到】
: 我以前写的，你看看有什么问题吗？与书上有什么不同？
: public static ArrayList createStack(Box[] boxes, Box bottom,
: HashMap> map) {
: if (map.containsKey(bottom))
: return map.get(bottom);
: ArrayList result = new ArrayList();
: int maxLen = 0;
: for (int i = 0; i < boxes.length; i++) {
: if (boxes[i].canBeAbove(bottom)) {
: ArrayList list = createStack(boxes, boxes[i], map);
| c********t
发帖数: 5706 | 11 哦，原来是比较高度，多谢。
还有注意称呼，俺不是mm啊。
【在 w********p 的大作中提到】
: 99％正确。没有书上第二解犯的错。code 很简洁。记下来，学习。
: 但是有个小问题导致case 结果不是100％正确。
: 问题处在比较上。是小问题。if (list.size() > maxLen) { maxLen = list.size();
: 是比较盒子累积的高度，不是盒子个数。
: 您的code运行结果。
: Box(1,7,4)
: Box(4,9,6)
: ****************
: 书上第一解的运行结果。
: Box(1,7,4)
| w********p
发帖数: 948 | 12 不好意思头像是个美女，一直以为你是个mm.
【在 c********t 的大作中提到】
: 哦，原来是比较高度，多谢。
: 还有注意称呼，俺不是mm啊。
| c********t
发帖数: 5706 | 13 头像是ld
【在 w********p 的大作中提到】
: 不好意思头像是个美女，一直以为你是个mm.
| c********t
发帖数: 5706 | 14 明白了。我一般凡是要clone的，都写在修改之前。
【在 w********p 的大作中提到】
: 又对比了一遍code, 大概知道问题出在哪里了。
: 之所以有结果如下：
: Box(1,7,4)
: Box(4,9,6)
: Box(2,10,16)
: 是因为 Box(2,10,16) 比Box(1,7,4)大，所以 Box(2,10,16) 把 Box(1,7,4)的
: stackmap都加上了。
: if (bottom != null) {
: //问题在于这句，加上就ok。
: max_stack = new ArrayList(max_stack);
|
|
