LeetCode 1739. 放置盒子(数学)

简介: LeetCode 1739. 放置盒子(数学)

文章目录


1. 题目

2. 解题


1. 题目


有一个立方体房间,其长度、宽度和高度都等于 n 个单位。

请你在房间里放置 n 个盒子,每个盒子都是一个单位边长的立方体。放置规则如下:


你可以把盒子放在地板上的任何地方。

如果盒子 x 需要放置在盒子 y 的顶部,那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。

给你一个整数 n ,返回接触地面的盒子的 最少 可能数量。


示例 1:

image.png


image.png

输入:n = 3
输出:3
解释:上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角,对应左侧位置。

image.pngimage.png



2. 解题


  • 根据题意,靠着墙角是最好的方法
  • 先假设这个完整的斜坡能摆满,多少层能超过 n
  • 然后多余出来的,第一次增加一个底部的可以摆 1 个,第二次增加一个底部的可以增加 2 个积木,依次类推
class Solution {
public:
    int minimumBoxes(int n) {
        int ct = 1, layer = 1;
        while(ct < n)
        {
            layer++;
            ct += layer*(layer+1)/2;//每一层的个数
        }
        if(ct == n) return layer*(layer+1)/2;
        ct -= layer*(layer+1)/2;
        int left = n-ct;//多出来的
        layer--;
        int bottom = layer*(layer+1)/2, delta = 1;
        while(left>0)
        {
            bottom++;//每放下一个底部积木
            left -= delta++;//可以依次增加放置积木1,2,3,4。。。个
        }
        return bottom;
    }
};

0 ms 5.9 MB C++

相关文章
|
算法 Android开发 Python
LeetCode 周赛上分之旅 #43 计算机科学本质上是数学吗?
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
64 0
LeetCode 周赛上分之旅 #43 计算机科学本质上是数学吗?
|
6月前
|
存储 算法 数据挖掘
python 数学+减治、下一个排列法、DFS回溯法实现:第 k 个排列【LeetCode 题目 60】
python 数学+减治、下一个排列法、DFS回溯法实现:第 k 个排列【LeetCode 题目 60】
|
6月前
|
存储 算法
力扣每日一题 6/20 数学+数组
力扣每日一题 6/20 数学+数组
36 1
|
6月前
|
算法
力扣每日一题 6/16 字符串 + 随机一题 动态规划/数学
力扣每日一题 6/16 字符串 + 随机一题 动态规划/数学
48 0
|
7月前
leetcode:292. Nim 游戏(数学推理)
leetcode:292. Nim 游戏(数学推理)
36 0
|
7月前
|
算法 测试技术 C#
【数学】LeetCode1526: 形成目标数组的子数组最少增加次数
【数学】LeetCode1526: 形成目标数组的子数组最少增加次数
|
7月前
|
算法 测试技术 C++
【数学】LeetCode1526: 形成目标数组的子数组最少增加次数
【数学】LeetCode1526: 形成目标数组的子数组最少增加次数
|
存储
力扣119杨辉三角 II:代码实现 + 方法总结(数学规律法 & 记忆法/备忘录)
力扣119杨辉三角 II:代码实现 + 方法总结(数学规律法 & 记忆法/备忘录)
95 0
|
Java C++ Python
力扣题目-Z字形变幻(数学规律法、hash法,c++,python,Java实现)
力扣题目-Z字形变幻(数学规律法、hash法,c++,python,Java实现)
118 0