【每日一题】1011. 在 D 天内送达包裹的能力
2021/4/26 10:25:30
本文主要是介绍【每日一题】1011. 在 D 天内送达包裹的能力,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/
思路:
分析题目有两个临界值,容量足够,能够送达;容量不够,不能送达。我们要找的那个容量是满足条件的最小容量,可以考虑使用二分法。
/** * 切分成 D 段,求满足条件的最小容量 * 这道题有两个临界值,最小值是物品中的最大重量。最小值是所有物品重量的和 * 可以考虑使用二分法,逐渐逼近正确值 */ class Solution { public int shipWithinDays(int[] weights, int D) { int left = Integer.MIN_VALUE, right = 0; for(int w : weights){ left = Math.max(left, w); right += w; } while(left < right){ //mid 就是我们进行试探的值 int mid = (left + right) / 2; //下面就是一个判断条件 int need = 0;//需要的运输次数 int cur = 0; for(int i = 0; i < weights.length; i++){ //已经超出了最大运载能力 if(cur + weights[i] > mid){ need ++; cur = 0; } cur += weights[i]; } //当前的 mid 满足条件,说明我们的运载能力是足够的 if(need < D){ right = mid; } else{ left = mid + 1; } } return left; } }
这篇关于【每日一题】1011. 在 D 天内送达包裹的能力的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)