leetcode 1011. Capacity To Ship Packages Within D Days(D天内运送包裹的容量)


数组的每个元素代表每个货物的重量,注意这个货物是有先后顺序的,先来的要先运输,所以不能改变这些元素的顺序。
要days天内把这些货物全部运输出去,问所需船的最小载重量。
思路:
数组内数字顺序不能变,就相当于拿days-1个隔板,把数组隔成days个部分,
每部分求和,这些和的最小值就是最小载重量。
暴力方法的话需要每固定一个隔板,然后调节剩下的隔板,
找出每个隔板内数字和的最小值,需要O(n^days)的复杂度。
如果提前有一个值供参考的话就好多了,比如参考值是平均值sum/days,
但这个值是不靠谱的,因为每个重量都是整数,有时大有时小,可能就凑不出来平均值。
那有没有一种方法提供一个参考的载重量,然后在实际过程中可调节呢。
比如说小于这个载重量就装船,超过了就加一天,第2天再装船,
最后发现天数超过了days,说明这个载重量不够,要加大。
反之载重量可以进一步缩小。
那每次要加大多少,减小多少呢,肯定不是1。
假如我们知道最大可能的载重量,比如是Integer的最大值,
然后在0和最大值之间找一个载重量,
能在days内装船就缩小,把最大载重量调节到现在值,
不能装就把最小载重量调节到现在的值,
这个是不是似曾相识的binary search.
最大载重量设为Integer的最大值是不是有点浪费?
观察一下,如果days内要运送完,把days-1个隔板平均放到数组中,
每部分货物的个数是n/days,
而且weight[i] <= 500, 那每个货物就按最大的500算,
所以最大载重量就是500 * (n/days+1).
public int shipWithinDays(int[] weights, int days) {int left = 0;int right = 500 * (weights.length / days+1);while(left < right) {int mid = left + (right - left) / 2;if(canShip(weights, mid, days)) {right = mid;} else {left = mid + 1;}}return left;}boolean canShip(int[] weights, int capacity, int totalDays) {int sum = 0;int days = 1;for(int weight : weights) {if(weight > capacity) return false;sum += weight;if(sum > capacity){days ++;if(days > totalDays) return false;sum = weight;}}return true;}
相关文章:
leetcode 1011. Capacity To Ship Packages Within D Days(D天内运送包裹的容量)
数组的每个元素代表每个货物的重量,注意这个货物是有先后顺序的,先来的要先运输,所以不能改变这些元素的顺序。 要days天内把这些货物全部运输出去,问所需船的最小载重量。 思路: 数组内数字顺序不能变,就…...
支持向量机SVM详细原理,Libsvm工具箱详解,svm参数说明,svm应用实例,神经网络1000案例之15
目录 支持向量机SVM的详细原理 SVM的定义 SVM理论 Libsvm工具箱详解 简介 参数说明 易错及常见问题 SVM应用实例,基于SVM的股票价格预测 支持向量机SVM的详细原理 SVM的定义 支持向量机(support vector machines, SVM)是一种二分类模型&a…...
Mac 上搭建 iOS WebDriverAgent 环境
文章目录Mac环境搭建配置 Xcode 生成 WDA常见问题brew 安装失败Mac环境搭建 macOS 系统电脑:12.6.2 Xcode:14.0.1(xcodebuild -version) appium Desktop:1.21.0 (下载链接) Appium Desktop 1.22.0 ,从该版…...
python学习笔记之例题篇NO.3
获得用户输入的一个整数N,输出N中所出现不同数字的和。 s list(set(list(input())))# ① r…...
【Kubernetes】第七篇 - Service 服务介绍和使用
一,前言 上一篇,通过配置一个 Deployment 对象,在内部创建副本集对象,副本集帮我们创建了 3 个 pod 副本 由于 pod 存在 IP 漂移现象,pod 的创建和重启会导致 IP 变化; 本篇,介绍 Service 服…...
Linux 终端复用器Tmux
目录 Tmux讲解 配置tmux 配置tmux会话 配置tmux窗口(在会话界面进行配置) 配置tmux面板 配置窗口共享同步 Tmux讲解 RHEL5/6/7使用的是screen软件包 RHEL8使用的是tumx软件包(功能更强大,更易用) tmux的三个基本…...
Hadoop集群模式安装(Cluster mode)
1、Hadoop源码编译 安装包、源码包下载地址 Index of /dist/hadoop/common/hadoop-3.3.0为什么要重新编译Hadoop源码? 匹配不同操作系统本地库环境,Hadoop某些操作比如压缩、IO需要调用系统本地库(*.so|*.dll) 修改源码、重构源码 如何…...
PTA L1-054 福到了(详解)
前言:内容包括:题目,代码实现,大致思路,代码解读 题目: “福”字倒着贴,寓意“福到”。不论到底算不算民俗,本题且请你编写程序,把各种汉字倒过来输出。这里要处理的每…...
python -- 魔术方法
魔术方法就算定义在类里面的一些特殊的方法 特点:这些func的名字前面都有两个下划线 __new__方法 相当于一个类的创建一个对象的过程 __init__方法 相当于为这个类创建好的对象分配地址初始化的过程 __del__方法 一个类声明这个方法后,创建的对象如果…...
「JVM 编译优化」提前编译器
1996 年 JDK 1.0 发布,同年 7 月 外挂即时编译器发布(JDK 1.0.2),而 Java 提前编译发布在之后几个月(IBM High Performance Compiler for Java),1998 年 GNU 组织公布 GCC 家族新成员 GNU Compi…...
Golang channel 用法与实现原理
文章目录1.简介2.用法3.三种状态4.实现原理数据结构原理概述5.小结参考文献1.简介 Golang channel 是一种并发原语,用于在不同 goroutine 之间进行通信和同步。本质上,channel 是一种类型安全的 FIFO 队列,它可以实现多个 goroutine 之间的同…...
jackson 序列化、反序列化的时候第一个大写单词变成小写了(属性设置不成功)
参考链接:https://www.baeldung.com/jackson-annotations 遇到的问题 之前和第三方对接,返回的接口中的属性名称是拼音字母大写,奇怪,反序列化的时候好多字段都为空,没设置进去。 因为对接前,我先用 IntelliJ IDEA …...
如何判断机器学习数据集是否是线性的
首先,线性和非线性函数之间的区别: 左边是线性函数,右边是非线性函数。 线性函数:可以简单定义为始终遵循以下原则的函数: 输入/输出=常数。 线性方程总是1次多项式(例如x+2y+3=0)。在二维情况下,它们总是形成直线;在其他维度中,它们也可以形成平面、点或超平面。它们的…...
后端基础SQL
SQL基础语法: sql对大小写不敏感,eg: SELECT 等效于 select;select: select用于从表中查找数据,select 列名 from 表名 —> 结果集::仅有查询列的结果表; SELECT * FROM 表名称 ----> 结果集: 查找表的所有数据…...
Ubuntu 18.04 上编译和安装内核(内核源码版本)
Ubuntu 18.04 上编译和安装内核(内核源码版本) linux发行版本为,ubuntu18.04。内核版本为5.15.7。其他版本类似。 1.下载内核源代码。可以从官方网站下载最新的内核源代码,也可以使用 Git 命令从 Linux 内核的 Git 仓库中获取最新…...
day 53|● 1143.最长公共子序列 ● 1035.不相交的线 ● 53. 最大子序和 动态规划
1143. 最长公共子序列 给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些…...
运维工程师必知的十项Linux常识
1、GNU和GPL GNU计划(又称革奴计划),是由Richard Stallman(理查德斯托曼)在1983年9月27日公开发起的软件集体协作计划。它的目标是创建一套完全的操作系统。GNU也称为软件工程项目。GPL是GNU的通用公共许可证…...
C++ 11 之右值引用和移动语义
文章目录左值引用与右值引用1、左值与右值2、纯右值、将亡值3、左值引用与右值引用4、右值引用和 std::move 使用场景引用限定符移动语义—std::move()完美转发emplace_back 减少内存拷贝和移动总结c11中引用了右值引用和移动语义,可以避免无谓的复制,提…...
【第一章:Spring概述、特点、IOC容器、IOC操作bean管理(基于xml方式)】
第一章:Spring概述、特点、IOC容器、IOC操作bean管理(基于xml方式) 1.Spring是什么? ①Spring是一款主流的java EE 轻量级开源框架。 ②广义的Spring:Spring技术栈,Spring不再是一个单纯的应用框架&#x…...
CSS变量
前端的开发工作中,CSS 是不可或缺的部分;实际工作中,我们通过JavaScript 来进行数据和交互工作,CSS 为用户呈现可视化的界面。有时,CSS 来进行部分交互效果是不是会比 JavaScript 更高效、更省事呢? 一、变…...
宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...
elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
API网关Kong的鉴权与限流:高并发场景下的核心实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...
云原生周刊:k0s 成为 CNCF 沙箱项目
开源项目推荐 HAMi HAMi(原名 k8s‑vGPU‑scheduler)是一款 CNCF Sandbox 级别的开源 K8s 中间件,通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度,为容器提供统一接口,实现细粒度资源配额…...
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章 摘要: 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言,受限于 C 语言本身的内存安全和并发安全问题,开发复杂模块极易引入难以…...
【阅读笔记】MemOS: 大语言模型内存增强生成操作系统
核心速览 研究背景 研究问题:这篇文章要解决的问题是当前大型语言模型(LLMs)在处理内存方面的局限性。LLMs虽然在语言感知和生成方面表现出色,但缺乏统一的、结构化的内存架构。现有的方法如检索增强生成(RA…...
EEG-fNIRS联合成像在跨频率耦合研究中的创新应用
摘要 神经影像技术对医学科学产生了深远的影响,推动了许多神经系统疾病研究的进展并改善了其诊断方法。在此背景下,基于神经血管耦合现象的多模态神经影像方法,通过融合各自优势来提供有关大脑皮层神经活动的互补信息。在这里,本研…...
未授权访问事件频发,我们应当如何应对?
在当下,数据已成为企业和组织的核心资产,是推动业务发展、决策制定以及创新的关键驱动力。然而,未授权访问这一隐匿的安全威胁,正如同高悬的达摩克利斯之剑,时刻威胁着数据的安全,一旦触发,便可…...
【题解-洛谷】P10480 可达性统计
题目:P10480 可达性统计 题目描述 给定一张 N N N 个点 M M M 条边的有向无环图,分别统计从每个点出发能够到达的点的数量。 输入格式 第一行两个整数 N , M N,M N,M,接下来 M M M 行每行两个整数 x , y x,y x,y,表示从 …...
2025 后端自学UNIAPP【项目实战:旅游项目】7、景点详情页面【完结】
1、获取景点详情的请求【my_api.js】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http(/login/getWXSessionKey, {code,avatar}); };//…...
