【微软算法面试高频题】堆箱子

2021/7/15 12:06:08

本文主要是介绍【微软算法面试高频题】堆箱子,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

微软和谷歌的几个大佬组织了一个面试刷题群,可以加管理员VX:sxxzs3998(备注CSDN),进群参与讨论和直播

1. 题目

给你一堆n个箱子,箱子宽 w i w_i wi​、深 d i d_i di​、高 h i h_i hi​。箱子不能翻转,将箱子堆起来时,下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法,搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

输入使用数组 [ w i , d i , h i ] [w_i, d_i, h_i] [wi​,di​,hi​]表示每个箱子。

示例1:
 输入:box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
 输出:6
示例2:
 输入:box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]
 输出:10

2. 解析

2.1 回溯算法

先想出暴力解法,即以每个箱子为最底下的箱子。然后在余下的箱子中寻找下一个箱子,下一个箱子自然是比前一个要小的,而后再寻找更小的。这就是一个 dfs 的过程。

选择一个箱子作为作为底之后,可以把问题转换为在约束条件下,求其余箱子能叠出的最大高度。可以把子问题的解(以每个箱子为底所能得到的最大高度)缓存下来,以加速计算。另外,可以在维度上进行升序排列,这样当前箱子后面的所有箱子都不可能处于该箱子之上。 所以操作如下:

  • 排序(升序)
  • 遍历,将各个箱子作为底
  • 在剩下的箱子中,以2步骤的箱子为底和约束条件下,寻找合适的箱子,递归重复2,直到所有箱子。计算高度和。
  • 在高度和中取最大值。
class Solution {
public:
    int pileBox(vector<vector<int>>& box) {
        sort(box.begin(), box.end(), [](auto& a, auto& b){
            return a[0] < b[0];
        });
        vector<int> cache(box.size(), -1);
        int max_height = 0;
        for(int i = 0; i < box.size(); i++){
            max_height = max(max_height, dfs(box, i, cache));
        }
        return max_height;
    }

    int dfs(vector<vector<int>>& box, int bottom_box_i, vector<int>& cache){
        if(cache[bottom_box_i] != -1){
            return cache[bottom_box_i];
        }
        int ret = 0;
        vector<int> &bottom_box = box[bottom_box_i];
        for(int i = 0; i < bottom_box_i; i++){
            if(small(box[i], bottom_box)){
                ret = max(ret, dfs(box, i, cache));
            }
        }
        ret = ret + bottom_box[2];
        cache[bottom_box_i] = ret;
        return ret;
    }
    
    bool small(const vector<int> &box1, const vector<int> &box2){
        for(int i = 0;i<box1.size();i++){
            if(box1[i] >= box2[i]){
                return false;
            }
        }
        return true;
    }
};

2.2 动态规划

本题类似于俄罗斯套娃,都属于最长递增子串问题。也就是在一维的数组中找到该数列的递增次序,如下图所示:

image.png

最终紫色的序列1,2,3就是最后的最长递增子串。放到这道题来讲,我们先要将三维的排序,对于第一维相同的,就采用第二维的子串递增,如果第二维也相同,那么就找第三维的子串递增序列。下图是一个二维的示例:

image.png

image.png

所以对于该题的算法操作如下:

  • 先将数组按照任何一条边降序重排,目的是为了降低里层循环次数。
  • 使用dp一维数组记录以序号 i i i箱子为顶时的最大高度。
  • 计算每个箱子 i i i时,在约束条件下,找到所有箱子 k k k( i i i可以放在 k k k的上面),并计算以k为顶最大高度与 i i i的高度之和,取最大值。
  • 所有箱子都操作完后,取dp数组元素的最大值
class Solution {
public:
    int pileBox(vector<vector<int>>& box) {
        sort(box.begin(), box.end(), [](auto& a, auto& b){
            return a[0] < b[0];
        });
        vector<int> dp(box.size(), 0);
        dp[0] = box[0][2];
        int ret = dp[0];
        for(int i = 1; i < box.size(); i++){
            int max_height = 0;
            for(int j = 0; j < i; j++){
                if(small(box[j], box[i])){
                    max_height = max(max_height, dp[j]);
                }
            }
            dp[i] = max_height + box[i][2];
            ret = max(ret, dp[i]);
        }
        return ret;
    }
    
    bool small(const vector<int> &box1, const vector<int> &box2){
        for(int i = 0;i<box1.size();i++){
            if(box1[i] >= box2[i]){
                return false;
            }
        }
        return true;
    }
};

微软和谷歌的几个大佬组织了一个面试刷题群,可以加管理员VX:sxxzs3998(备注CSDN),进群参与讨论和直播



这篇关于【微软算法面试高频题】堆箱子的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程