当前位置: 首页 > news >正文

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天内运送包裹的容量)

数组的每个元素代表每个货物的重量&#xff0c;注意这个货物是有先后顺序的&#xff0c;先来的要先运输&#xff0c;所以不能改变这些元素的顺序。 要days天内把这些货物全部运输出去&#xff0c;问所需船的最小载重量。 思路&#xff1a; 数组内数字顺序不能变&#xff0c;就…...

支持向量机SVM详细原理,Libsvm工具箱详解,svm参数说明,svm应用实例,神经网络1000案例之15

目录 支持向量机SVM的详细原理 SVM的定义 SVM理论 Libsvm工具箱详解 简介 参数说明 易错及常见问题 SVM应用实例&#xff0c;基于SVM的股票价格预测 支持向量机SVM的详细原理 SVM的定义 支持向量机&#xff08;support vector machines, SVM&#xff09;是一种二分类模型&a…...

Mac 上搭建 iOS WebDriverAgent 环境

文章目录Mac环境搭建配置 Xcode 生成 WDA常见问题brew 安装失败Mac环境搭建 macOS 系统电脑&#xff1a;12.6.2 Xcode&#xff1a;14.0.1&#xff08;xcodebuild -version&#xff09; appium Desktop&#xff1a;1.21.0 (下载链接) Appium Desktop 1.22.0 &#xff0c;从该版…...

python学习笔记之例题篇NO.3

获得用户输入的一个整数N&#xff0c;输出N中所出现不同数字的和。‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‫‬ s list(set(list(input())))# ① r…...

【Kubernetes】第七篇 - Service 服务介绍和使用

一&#xff0c;前言 上一篇&#xff0c;通过配置一个 Deployment 对象&#xff0c;在内部创建副本集对象&#xff0c;副本集帮我们创建了 3 个 pod 副本 由于 pod 存在 IP 漂移现象&#xff0c;pod 的创建和重启会导致 IP 变化&#xff1b; 本篇&#xff0c;介绍 Service 服…...

Linux 终端复用器Tmux

目录 Tmux讲解 配置tmux 配置tmux会话 配置tmux窗口&#xff08;在会话界面进行配置&#xff09; 配置tmux面板 配置窗口共享同步 Tmux讲解 RHEL5/6/7使用的是screen软件包 RHEL8使用的是tumx软件包&#xff08;功能更强大&#xff0c;更易用&#xff09; tmux的三个基本…...

Hadoop集群模式安装(Cluster mode)

1、Hadoop源码编译 安装包、源码包下载地址 Index of /dist/hadoop/common/hadoop-3.3.0为什么要重新编译Hadoop源码? 匹配不同操作系统本地库环境&#xff0c;Hadoop某些操作比如压缩、IO需要调用系统本地库&#xff08;*.so|*.dll&#xff09; 修改源码、重构源码 如何…...

PTA L1-054 福到了(详解)

前言&#xff1a;内容包括&#xff1a;题目&#xff0c;代码实现&#xff0c;大致思路&#xff0c;代码解读 题目&#xff1a; “福”字倒着贴&#xff0c;寓意“福到”。不论到底算不算民俗&#xff0c;本题且请你编写程序&#xff0c;把各种汉字倒过来输出。这里要处理的每…...

python -- 魔术方法

魔术方法就算定义在类里面的一些特殊的方法 特点&#xff1a;这些func的名字前面都有两个下划线 __new__方法 相当于一个类的创建一个对象的过程 __init__方法 相当于为这个类创建好的对象分配地址初始化的过程 __del__方法 一个类声明这个方法后&#xff0c;创建的对象如果…...

「JVM 编译优化」提前编译器

1996 年 JDK 1.0 发布&#xff0c;同年 7 月 外挂即时编译器发布&#xff08;JDK 1.0.2&#xff09;&#xff0c;而 Java 提前编译发布在之后几个月&#xff08;IBM High Performance Compiler for Java&#xff09;&#xff0c;1998 年 GNU 组织公布 GCC 家族新成员 GNU Compi…...

Golang channel 用法与实现原理

文章目录1.简介2.用法3.三种状态4.实现原理数据结构原理概述5.小结参考文献1.简介 Golang channel 是一种并发原语&#xff0c;用于在不同 goroutine 之间进行通信和同步。本质上&#xff0c;channel 是一种类型安全的 FIFO 队列&#xff0c;它可以实现多个 goroutine 之间的同…...

jackson 序列化、反序列化的时候第一个大写单词变成小写了(属性设置不成功)

参考链接:https://www.baeldung.com/jackson-annotations 遇到的问题 之前和第三方对接&#xff0c;返回的接口中的属性名称是拼音字母大写&#xff0c;奇怪&#xff0c;反序列化的时候好多字段都为空&#xff0c;没设置进去。 因为对接前&#xff0c;我先用 IntelliJ IDEA …...

如何判断机器学习数据集是否是线性的

首先,线性和非线性函数之间的区别: 左边是线性函数,右边是非线性函数。 线性函数:可以简单定义为始终遵循以下原则的函数: 输入/输出=常数。 线性方程总是1次多项式(例如x+2y+3=0)。在二维情况下,它们总是形成直线;在其他维度中,它们也可以形成平面、点或超平面。它们的…...

后端基础SQL

SQL基础语法: sql对大小写不敏感&#xff0c;eg: SELECT 等效于 select&#xff1b;select: select用于从表中查找数据&#xff0c;select 列名 from 表名 —> 结果集:&#xff1a;仅有查询列的结果表&#xff1b; SELECT * FROM 表名称 ----> 结果集: 查找表的所有数据…...

Ubuntu 18.04 上编译和安装内核(内核源码版本)

Ubuntu 18.04 上编译和安装内核&#xff08;内核源码版本&#xff09; linux发行版本为&#xff0c;ubuntu18.04。内核版本为5.15.7。其他版本类似。 1.下载内核源代码。可以从官方网站下载最新的内核源代码&#xff0c;也可以使用 Git 命令从 Linux 内核的 Git 仓库中获取最新…...

day 53|● 1143.最长公共子序列 ● 1035.不相交的线 ● 53. 最大子序和 动态规划

1143. 最长公共子序列 给定两个字符串 text1 和 text2&#xff0c;返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 &#xff0c;返回 0 。 一个字符串的 子序列 是指这样一个新的字符串&#xff1a;它是由原字符串在不改变字符的相对顺序的情况下删除某些…...

运维工程师必知的十项Linux常识

1、GNU和GPL GNU计划&#xff08;又称革奴计划&#xff09;&#xff0c;是由Richard Stallman&#xff08;理查德斯托曼&#xff09;在1983年9月27日公开发起的软件集体协作计划。它的目标是创建一套完全的操作系统。GNU也称为软件工程项目。GPL是GNU的通用公共许可证&#xf…...

C++ 11 之右值引用和移动语义

文章目录左值引用与右值引用1、左值与右值2、纯右值、将亡值3、左值引用与右值引用4、右值引用和 std::move 使用场景引用限定符移动语义—std::move()完美转发emplace_back 减少内存拷贝和移动总结c11中引用了右值引用和移动语义&#xff0c;可以避免无谓的复制&#xff0c;提…...

【第一章:Spring概述、特点、IOC容器、IOC操作bean管理(基于xml方式)】

第一章&#xff1a;Spring概述、特点、IOC容器、IOC操作bean管理&#xff08;基于xml方式&#xff09; 1.Spring是什么&#xff1f; ①Spring是一款主流的java EE 轻量级开源框架。 ②广义的Spring&#xff1a;Spring技术栈&#xff0c;Spring不再是一个单纯的应用框架&#x…...

CSS变量

前端的开发工作中&#xff0c;CSS 是不可或缺的部分&#xff1b;实际工作中&#xff0c;我们通过JavaScript 来进行数据和交互工作&#xff0c;CSS 为用户呈现可视化的界面。有时&#xff0c;CSS 来进行部分交互效果是不是会比 JavaScript 更高效、更省事呢&#xff1f; 一、变…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...