[CareerCup] 9.10 Stack Boxes 垒箱子问题

简介:

9.10 You have a stack of n boxes, with widths w., heights hir and depths drThe boxes cannot 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.

开始看到这题时,以为是3.4 Towers of Hanoi 汉诺塔,其实不太一样,这道题只是单纯的让我们垒箱子而已,大的在最底下,问我们能垒出的最大高度是多少。也是一道用递归来解的题,首先我们要先实现箱子类Box,里面包含了箱子的尺寸宽,高和深度,然后还要有一个成员函数canBeAbove,用来判断当前箱子能否放到另一个箱子的上面,还有一个静态函数,是求一摞箱子的总高度的。然后我们对每个箱子都调用一次递归,然后维护一个最大值,每次递归都更新这个最大值,那么最终递归结束后这个最大值就是所求,参见代码如下:

解法一:

class Box {
public:
    int _width, _depth, _height;
    Box(int w, int d, int h): _width(w), _depth(d), _height(h) {}
    bool canBeAbove(Box *bottom) {
        if (bottom == nullptr) return true;
        return _width > bottom->_width && _depth > bottom->_depth && _height > bottom->_height;
    }
    static int stackHeight(vector<Box*> stack) {
        int res = 0;
        for (auto &a : stack) {
            res += a->_height;
        }
        return res;
    }
};

class Solution {
public:
    vector<Box*> createStack(vector<Box*> boxes) {
        return createStack(boxes, nullptr);
    }
    vector<Box*> createStack(vector<Box*> boxes, Box *bottom) {
        vector<Box*> res;
        int max_height = 0;
        for (auto &a : boxes) {
            if (a->canBeAbove(bottom)) {
                vector<Box*> new_stack = createStack(boxes, a);
                int new_height = Box::stackHeight(new_stack);
                if (new_height > max_height) {
                    res = new_stack;
                    max_height = new_height;
                }
            }
        }
        if (bottom != nullptr) res.push_back(bottom);
        return res;
    }
};

上述代码虽然正确,但是不高效,像之前那道9.8 Represent N Cents 美分的组成一样,我们也可以用哈希表来优化,保存我们之前算过的最优解,那么在递归调用需要相同的结果时,就可以直接从哈希表中调用,参见代码如下:

解法二:

class Solution {
public:
    vector<Box*> createStack(vector<Box*> boxes) {
        unordered_map<Box*, vector<Box*> > m;
        return createStack(boxes, nullptr, m);
    }
    vector<Box*> createStack(vector<Box*> &boxes, Box *bottom, unordered_map<Box*, vector<Box*>  > &m) {
        if (bottom != nullptr && m.find(bottom) != m.end()) {
            return m[bottom];
        }
        vector<Box*> res;
        int max_height = 0;
        for (auto &a : boxes) {
            if (a->canBeAbove(bottom)) {
                vector<Box*> new_stack = createStack(boxes, a, m);
                int new_height = Box::stackHeight(new_stack);
                if (new_height > max_height) {
                    res = new_stack;
                    max_height = new_height;
                }
            }
        }
        if (bottom != nullptr) {
            res.push_back(bottom);
            m[bottom] = res;
        }
        return res;
    }
};

本文转自博客园Grandyang的博客,原文链接:垒箱子问题[CareerCup] 9.10 Stack Boxes,如需转载请自行联系原博主。

相关文章
HDU 1506 Largest Rectangle in a Histogram(单调栈)
HDU 1506 Largest Rectangle in a Histogram(单调栈)
POJ 3494 Largest Submatrix of All 1’s(单调栈)
POJ 3494 Largest Submatrix of All 1’s(单调栈)
POJ-1475,Pushing Boxes(双BFS)
POJ-1475,Pushing Boxes(双BFS)
|
人工智能
Codeforces 220B-Little Elephant and Array-扫描线 & 树状数组
题意: 给出一个长度为n的数组,有m个询问,每次询问给出一个区间,问这个区间内有多少个数x恰好出现x次
125 0
Codeforces 220B-Little Elephant and Array-扫描线 & 树状数组
【1105】Spiral Matrix (25分)【螺旋矩阵】
【1105】Spiral Matrix (25分)【螺旋矩阵】 【1105】Spiral Matrix (25分)【螺旋矩阵】
121 0
LeetCode 118:杨辉三角 II Pascal's Triangle II
公众号:爱写bug(ID:icodebugs)作者:爱写bug 给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。 Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle. Note that the row index starts from 0. 在杨辉三角中,每个数是它左上方和右上方的数的和。
918 0
Leetcode 118:Pascal's Triangle 杨辉三角
118:Pascal's Triangle 杨辉三角 Given a non-negative integer numRows, generate the first numRows of Pascal's triangle. 给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
981 0
|
Java 数据安全/隐私保护
[LintCode] Number of Islands(岛屿个数)
描述 给一个01矩阵,求不同的岛屿的个数。 0代表海,1代表岛,如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 样例 在矩阵: [ [1, 1, 0, 0, 0], [0, 1, 0, 0, 1], [0, 0, 0, 1, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 1] ] 中有 3 个岛。
1249 0
1128. N Queens Puzzle (20) 判断是否是对角线
The "eight queens puzzle" is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other.
1139 0