专栏首页算法修养LeetCode 1739. Building Boxes

LeetCode 1739. Building Boxes

https://leetcode.com/problems/building-boxes/ 题意:在一个边长是n的立方体中放n个方块,方块可以叠加,但是被叠加的在下方的方块八面必须挨着墙或者别的方块。 问最底部最少可以放多少个方块。

这是一道找规律的题目,我们可以找出底部方块的个数m和最多可以放n个方块的对应关系。比如 m=1,n=1 m=2,n=2 m=3,n=4 当底部为3块方块的时候,上一层可以再放一块,一共就是4块 m=4,n=5 m=5,n=7 m=6,n=10 m=7,n=11 m=8,n=13

可以从中找出n的通向公式,给出m可以快速算出n。这样对于题目给出的N我就可以做二分,找出最后一个小于等于N的n对应的m就是答案。

那么这个通项公式,怎么算呢,很麻烦。可以找下规律, 1 2 4 5 7 10 11 13 16 20 21 ... 1 2 1 2 3 1 2 3 4 1 ... 找到规律,那就开始写代码把。

class Solution {
public:
long long int a[2005];
long long int b[2005];
void init()
{
	for (long long int i = 1; i <= 2000; i++)
	{
		a[i] = (i * (i + 1)) / 2;
        
		b[i] = (i * (i + 1) * (i + 2)) / 6;
	}
}
int fun2(int x)
{
	int l = 1;
	int r = 2000;
	while (l <= r)
	{
		int mid = (l + r) / 2;
		if (x > a[mid])
		{
			l = mid + 1;
		}
		else if (x == a[mid])
		{
			return mid;
		}
		else
		{
			r = mid - 1;
		}
	}

	return r;
}
int fun(int n)
{
	int l = 1;
	int r = a[2000];

	while (l <= r)
	{
		long long int mid = (l + r) / 2;
		int index = fun2(mid);
		int m = mid - a[index];
		long long int y = b[index] + (m * (m + 1 )) / 2;

		if (n > y)
		{
			l = mid + 1;
		}
		else if (n == y)
		{
			return mid;
		}
		else
		{
			r = mid - 1;
		}
	}

	return l;

}
    int minimumBoxes(int n) {
        init();
        return fun(n);
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1117 - Building H2O

    There are two kinds of threads, oxygen and hydrogen. Your goal is to group these...

    Reck Zhang
  • ​LeetCode刷题实战36: 有效的数独

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • LeetCode笔记:Biweekly Contest 41 比赛记录

    第一题倒是一贯的挺简单的,最简单的思路就是直接做个二层循环就是了,不过我在比赛的时候想岔了,想着那样的算法复杂度恐怕有点高,就想着先将它转换为集合来处理,虽然也...

    codename_cys
  • LeetCode Weekly Contest 25 之 507.Perfect Number

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • Microsemi可编程PCIE Switch助力资源池化方案落地

    在去年的2018 ODCC峰会上,腾讯发布了T-Flex PCIE资源池化方案和产品,该产品由腾讯和浪潮联手设计制造。PCIE资源池化的关键的部件就是PCIE ...

    冬瓜哥
  • 初试 iOS 11 新框架:Vision Framework 让文字检测变得更容易

    iOSDevLog
  • 卷积神经网络第三周作业 Autonomous driving application - Car detection - v1

    Welcome to your week 3 programming assignment. You will learn about object detec...

    Steve Wang
  • LeetCode笔记:Weekly Contest 244 比赛记录

    第一题暴力解决就能够搞定了,直接将旋转变换进行实现,然后考察一下旋转之后的结果与目标结果是否完全一致即可。

    codename_cys
  • ​LeetCode刷题实战37: 解数独

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • ​LeetCode刷题实战37: 解数独

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • LeetCode Weekly Contest 44解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode Weekly Contest 25 之 537.Complex Number Multiplication

    依旧没有难度,这道题考的是对字符串的处理,但我又把它想复杂了,浪费了大量时间在解析上,就针对我的解题思路,来慢慢优化。

    用户1147447
  • Leetcode solution 322: Coin Change

    亚马逊的Alexa已经五岁了,经历了野蛮生长之后,Alexa准备开始变现了,包括subscribtion fee for premium content,ski...

    包子面试培训
  • ChainerCV︱堪比Opencv--深度学习工具库(Faster R-CNN、SSD 和 SegNet)

    Preferred Networks 通过其研究博客发布了深度学习计算机视觉实用库 ChainerCV,它基于 Chainer,能够简化计算机视觉的训...

    素质
  • 利用jTessBoxEditor工具进行Tesseract3.02.02样本训练,提高验证码识别率

    前文已经简要介绍tesseract ocr引擎的安装及基本使用,其中提到使用-l eng参数来限定语言库,可以提高识别准确率及识别效率。

    黯然销魂掌
  • 周志华:Learnware 将是机器学习的未来

    【新智元导读】《机器学习》作者、南京大学教授周志华在本文中,针对当前机器学习环境适应低、数据共享难等局限,提出新概念 learnware(学件)。Learnwa...

    新智元
  • 客户关系管理的k-波

    你是否注意到现在是非常时期。最近,我的一个观点是,客户关系管理正渗透到社会中,在社会中扮演着巨大的角色,我将其称为社会的”CRMification”。在经济学中...

    甜甜圈
  • 统计学习导论 Chapter8 -- Tree-Based Methods

    Book: An Introduction to Statistical Learning with Applications in R http:...

    用户1148525
  • CVPR2019 | 15篇论文速递(涵盖目标检测、语义分割和姿态估计等方向)

    【导读】CVPR 2019 接收论文列表已经出来了,但只是一些索引号,所以并没有完整的论文合集。CVer 最近也在整理收集,今天一文涵盖15篇 CVPR 201...

    AI研习社

扫码关注云+社区

领取腾讯云代金券