昨天299的tpt2没买成# PDA - 掌中宝
w*p
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;
}
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
clone();
一般来说,只有在会 expose internal reference object 才会用return clone() 或
者copy. 这里的max_stack 只是local变量,为什么要用clone()。而且不用的话,结果
出来是错的。谁个大牛给说说。
还有这道题career cup的解法是很笨的。不用这个,直接排序用类似longest
increasing subsequence的方法就可以了。我只是想学习下careercup的思路。
public static ArrayList
HashMap
if (bottom != null && stack_map.containsKey(bottom)) {
return stack_map.get(bottom);
}
int max_height = 0;
ArrayList
for (int i = 0; i < boxes.length; i++) {
if (boxes[i].canBeAbove(bottom)) {
ArrayList
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
}
public static int stackHeight(LinkedList
if (list == null) {
return 0;
}
int height = 0;
for ( Box box : list ) {
height += box.height;
}
return height;
}