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

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道

文/法律实务观察组 在债务重组领域&#xff0c;专业机构的核心价值不仅在于减轻债务数字&#xff0c;更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明&#xff0c;合法债务优化需同步实现三重平衡&#xff1a; 法律刚性&#xff08;债…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...