想要精通算法和SQL的成长之路 - 填充书架
想要精通算法和SQL的成长之路 - 填充书架
- 前言
- 一. 填充书架
- 1.1 优化
前言
想要精通算法和SQL的成长之路 - 系列导航
一. 填充书架
原题链接



题目中有一个值得注意的点就是:
- 需要按照书本顺序摆放。
- 每一层当中,只要厚度不够了,当前层最高的那一本书籍就视为本层的高度。
那么我们假设dp[i]: 代表从 book[0] 摆到 book[i] 的时书架的最小高度。
- 假设最后一层的第一本书的下标是
j,那么之前所有书本摆放的最小高度就是dp[j-1]。 - 我们再计算出,下标在
[j,i](最后一层)的书本中,高度最高的那一本书(同时满足厚度不超过shelfWidth),高度为maxHeight。 - 那么当前的最小总高度是
res = Max(dp[i-1]+maxHeight,res)。即之前的总高度+最后一层的最高高度。
我们递归,从后往前递归。入参为遍历的书本下标。
- 终止条件:下标 <0。代表没有书本了,停止递归。
- 递归做的事情:循环
[0,i]之间的所有元素,从后往前把书本放入最后一层,一旦厚度超出,终止遍历。否则,计算当前层的最高高度以及最小总高。
public class Test1105 {public int[][] books;public int shelfWidth;public int minHeightShelves(int[][] books, int shelfWidth) {this.books = books;this.shelfWidth = shelfWidth;return dfs(books.length - 1);}public int dfs(int i) {// 终止条件if (i < 0) {return 0;}int res = Integer.MAX_VALUE, maxHeight = 0, width = shelfWidth;for (int j = i; j >= 0; j--) {// 从后往前放书本width -= books[j][0];// 厚度不能超过 shelfWidth ,超过就代表放不下了if (width < 0) {break;}// 当前层最高高度maxHeight = Math.max(maxHeight, books[j][1]);// 更新总最低书架高度 = 上层最小总高度 + 当前层最高高度res = Math.min(res, dfs(j - 1) + maxHeight);}return res;}
}
这个解答其实对于用例比较多的情况,是会超时的。
1.1 优化
我们来看下上面代码的不好的点:
- 每次
dfs的时候,循环的范围是:[0,j]。 - 循环内部又每次调用了
dfs递归,即dfs[j-1]。
整个递归函数,只用到了一个索引的参数,我们可以发现,索引为1,2,3…的递归,被重复调用了非常多次。以当前索引为3为例:
- 第一次递归范围:[0,3]。
- 第二次递归范围:[0,2]。
- 第三次递归范围:[0,1]。
- …
那么我们可以用一个全局的变量去记录每次dfs返回的结果即可:
public class Test1105 {public int[][] books;public int shelfWidth;// 缓存dfs的结果public int[] dfsCache;public int minHeightShelves(int[][] books, int shelfWidth) {this.books = books;this.shelfWidth = shelfWidth;// 初始化dfsCache = new int[books.length];// 给个初始值,-1代表没有被执行过,即没有缓存Arrays.fill(dfsCache, -1);return dfs(books.length - 1);}public int dfs(int i) {// 终止条件if (i < 0) {return 0;}// 如果是-1,代表这层值没有执行过,往下走。否则,说明有缓存了,直接返回if (dfsCache[i] != -1) {return dfsCache[i];}int res = Integer.MAX_VALUE, maxHeight = 0, width = shelfWidth;for (int j = i; j >= 0; j--) {// 从后往前放书本width -= books[j][0];// 厚度不能超过 shelfWidth ,超过就代表放不下了if (width < 0) {break;}// 当前层最高高度maxHeight = Math.max(maxHeight, books[j][1]);// 更新总最低书架高度 = 上层最小总高度 + 当前层最高高度res = Math.min(res, dfs(j - 1) + maxHeight);}// 缓存下当前结果dfsCache[i] = res;return dfsCache[i];}
}
相关文章:
想要精通算法和SQL的成长之路 - 填充书架
想要精通算法和SQL的成长之路 - 填充书架 前言一. 填充书架1.1 优化 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 填充书架 原题链接 题目中有一个值得注意的点就是: 需要按照书本顺序摆放。每一层当中,只要厚度不够了,当前层最高…...
【ROS入门】ROS的核心概念
文章结构 通信机制节点(Node)——执行单元节点管理器(ROS Master)——控制中心话题通信——异步通信机制话题(Topic)消息(Message)——话题数据 服务通信——同步通信机制服务(Service) 话题和服务的区别参数(Parameter)——全局共享字典 文件系统功能包(Package&am…...
Python爬虫从端到端抓取网页
网页抓取和 REST API 简介 网页抓取是使用计算机程序以自动方式从网站提取和解析数据的过程。这是创建用于研究和学习的数据集的有用技术。虽然网页抓取通常涉及解析和处理 HTML 文档,但某些平台还提供 REST API 来以机器可读格式(如 JSON)检…...
这10款类似Stable Diffusion的ai绘图软件,你了解多少?
Stable Diffusion这款ai软件有哪些可以替代的软件?好用的类似Stable Diffusion的ai软件推荐,那么今天就跟着赞奇云工作站小编一起来看看吧。 什么是Stable Diffusion? 称为“Stable Diffusion”的文本到图像模型可以将任何文本转换为逼真、…...
部署ik分词器
部署ik分词器 案例版本:elasticsearch-analysis-ik-8.6.2 ES默认自带的分词器对中文处理不够友好,创建倒排索引时可能达不到我们想要的结果,然而IK分词器能够很好的支持中文分词 因为是集群部署,所以每台服务器中的ES都需…...
基于STM32+华为云IOT设计的智能垃圾桶
一、项目介绍 在商业街、小吃街和景区等人流密集的场所,垃圾桶的及时清理对于提供良好的游客体验至关重要。然而,传统的垃圾桶清理方式通常是定时或定期进行,无法根据实际情况进行及时响应,导致垃圾桶溢满,影响环境卫…...
板子接线图
1.ST-LINK V2接线 2.对抗板子刷蓝牙固件 接USB转TTL,用镊子短接两个孔 2.对抗板子用串口测试蓝牙AT命令 短接白色箭头,接TX,RX,电源...
Python练习之选择与循环
目录 1、编写程序,运行后用户输入4位整数作为年份,判断其是否为闰年。提示:如果年份能被400整除,则为闰年;如果年份能被4整除但不能被100整除也为闰年。2、编写程序,用户从键盘输入小于 1000 的整数&#x…...
MySQL5.7开启通用日志功能
起因: 因项目数据库占用异常,查询数据库有哪些IP地址连接使用(Windows环境下)。 操作步骤: 1、修改MySQL服务的my.ini 文件 # 开启通用查询日志 general_log 1 log_output …...
WPF控件模板
在过去,Windows开发人员必须在方便性和灵活性之间做出选择。为得到最大的方便性,他们可以使用预先构建好的控件。这些控件可以工作的足够好,但可定制性十分有限,并且几乎总是具有固定的可视化外观。偶尔,某些控件提供了…...
vue移动端页面适配
页面的适配,就是一个页面能在PC端正常访问,同时也可以在移动端正正常访问。 现在我们可以通过弹性布局【Flexible布局】、媒体查询和响应式布局。除此之外,还可以通过rem和vw针对性地解决页面适配问题。 响应式布局 响应式布局的核心&…...
Ei Scopus 双检索 |第三届信息与通信工程国际会议国际会议(JCICE 2024)
会议简介 Brief Introduction 2024年第三届信息与通信工程国际会议国际会议(JCICE 2024) 会议时间:2024年5月10日-12日 召开地点:中国福州 大会官网:JCICE 2024-2024 International Joint Conference on Information and Communication Engin…...
ChatGPT实战-Embeddings打造定制化AI智能客服
本文介绍Embeddings的基本概念,并使用最少但完整的代码讲解Embeddings是如何使用的,帮你打造专属AI聊天机器人(智能客服),你可以拿到该代码进行修改以满足实际需求。 ChatGPT的Embeddings解决了什么问题? …...
C语言指针,深度长文全面讲解
指针对于C来说太重要。然而,想要全面理解指针,除了要对C语言有熟练的掌握外,还要有计算机硬件以及操作系统等方方面面的基本知识。所以本文尽可能的通过一篇文章完全讲解指针。 为什么需要指针? 指针解决了一些编程中基本的问题。…...
云桌面打开部署在linux的服务特别卡 怎么解决
云桌面打开部署在 Linux 服务器上的服务卡顿可能是由多种因素引起的,包括服务器性能、网络连接、应用程序配置等。以下是一些可能的解决方法,可以帮助您缓解云桌面访问部署在 Linux 服务器上的服务时的卡顿问题: 优化服务器性能: …...
day5ARM
循环点亮三个led灯 方法1 ------------------led.h---------------- #ifndef __LED_H__ #define __LED_H__#define RCC (*(volatile unsigned int *)0x50000A28) #define GPIOE ((GPIO_t *)0x50006000) #define GPIOF ((GPIO_t *)0x50007000)//结构体封装 typedef struct {vo…...
旋转链表-双指针思想-LeetCode61
题目要求:给定链表的头结点,旋转链表,将链表每个节点向右移动K个位置。 示例: 输入:head [1,2,3,4,5], k2 输出:[4,5,1,2,3] 双指针思想: 先用双指针策略找到倒数K的位置,也就是(…...
使用自定义XML配置文件在.NET桌面程序中保存设置
本文将详细介绍如何在.NET桌面程序中使用自定义的XML配置文件来保存和读取设置。除了XML之外,我们还将探讨其他常见的配置文件格式,如JSON、INI和YAML,以及它们的优缺点和相关的NuGet类库。最后,我们将重点介绍我们为何选择XML作为…...
1787_函数指针的使用
全部学习汇总:GitHub - GreyZhang/c_basic: little bits of c. 前阵子似乎写了不少错代码,因为对函数指针的理解还不够。今天晚上似乎总算是梳理出了一点眉目,在先前自己写过的代码工程中做一下测试。 先前实现过一个归并排序算法,…...
解决nomachine扫描不出ip问题
IP扫描工具Advanced IP Scanner 快速的扫描局域网中存在ip地址以及pc机的活跃状态,还能列出局域网计算机的相关信息。并且ip扫描工具(Advanced IP Scanner)还能够单击访问更多有用的功能- 远程关机和唤醒 软件下载地址...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving
地址:LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂,正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...
深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙
WebGL:在浏览器中解锁3D世界的魔法钥匙 引言:网页的边界正在消失 在数字化浪潮的推动下,网页早已不再是静态信息的展示窗口。如今,我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室,甚至沉浸式的V…...
