当前位置: 首页 > 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; 一、变…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...