在D天Leetcode解决方案中运送包裹的能力


难度级别 中等
经常问 亚马逊
排列 二进制搜索

问题陈述

在“在D天之内运送包裹的能力”问题中,我们在端口A中有必须在D天之内传输到端口B的数据包。

我们得到一个weights数组,其中包含每个数据包的权重以及需要传输这些数据包的天数。 我们的任务是找到在D天之内用于将数据包从端口A传输到端口B的船舶的最小负载能力。

leetcode解决方案,可在D天之内寄出包裹

使用案列

weights = [1,2,3,4,5,6,7,8,9,10], D = 5
15

说明: 船舶将通过以下方式传输数据包:

首日:1,2,3,4,5

第二天2:6,7

第三天3:8

第四天4:9

第五天:5

这样,船舶的最小装载量应为15,才能在5天内传输所有数据包。

在D日内通过Leetcode解决方案运送包裹的方法

解决此问题的第一也是最重要的事情就是提出观察结果。 以下是关于我们的搜索间隔的一些观察结果:

  1. 船舶的承载能力应至少等于最大重量为max(weights)的包裹。 让我们将其命名为 Start 开始.
  2. 我们可以将船的最大容量限制为所有小包的重量之和,即sum(weights)。 让我们将其命名为 结束.

现在我们有了搜索间隔。 假设间隔的大小是 长度 数据包的数量是 n.  幼稚的方法可能是检查间隔中的每个值,以确保负载能力能否在D天之内成功传输数据包并从中选择最小值。 天真的方法的时间复杂度将为Length * n。

我们可以使用二进制搜索代替线性搜索来提高时间复杂度。

使用的时间复杂度 二进制搜索 方法将为log(Length)* n。

实施

可以在D天之内通过Leetcode解决方案运送包裹的能力的C ++代码

#include <bits/stdc++.h>
using namespace std; 
    int shipWithinDays(vector<int>& weights, int D) {
        int left = 0, right = 0;
        for (int w: weights) {
            left = max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = (left + right) / 2, requirement = 1, tillnow = 0;
            for (int w: weights) {
                if (tillnow + w > mid) {
                   requirement += 1;
                   tillnow = 0;
                }
                tillnow += w;
            }
            if (requirement > D) left = mid + 1;
            else right = mid;
        }
        return left;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4,5,6,7,8,9,10}; 
 int d=5;                               

 cout<<shipWithinDays(arr,d)<<endl;
 return 0;
}
15

可以在D天之内通过Leetcode解决方案运送包裹的Java代码

public class Tutorialcup {
    public static int shipWithinDays(int[] weights, int D) {
        int left = 0, right = 0;
        for (int w: weights) {
            left = Math.max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = (left + right) / 2, requirement = 1, tillnow = 0;
            for (int w: weights) {
                if (tillnow + w > mid) {
                   requirement += 1;
                   tillnow = 0;
                }
                tillnow += w;
            }
            if (requirement > D) left = mid + 1;
            else right = mid;
        }
        return left;
    }
  public static void main(String[] args) {
    int [] arr = {1,2,3,4,5,6,7,8,9,10}; 
     int d=5; 
    int ans= shipWithinDays(arr,d);
    System.out.println(ans);
  }
}
15

D天Leetcode解决方案中运送包裹的能力的复杂性分析

时间复杂度

上面代码的时间复杂度是 O(n * log(长度)) 因为我们遍历权重数组的log(Length)次。 在这里,n和Length分别是数据包的数量和搜索间隔的大小。

空间复杂度

上面代码的空间复杂度是 O(1) 因为我们只使用一个变量来存储答案。

參考資料