[Swift]LeetCode1011.在D天内送达包裹的能力|CapacityToShipPackagesWithinDDays ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10546244.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

A conveyor belt has packages that must be shipped from one port to another within D days.

The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.

Example 1:

Input: weights = 5
Output: 15
Explanation: 
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:

Input: weights = 3
Output: 6
Explanation: 
A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Example 3:

Input: weights = [1,2,3,1,1], D = 4
Output: 3
Explanation: 
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

Note:

1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500

Runtime: 276 ms

Memory Usage: 19.8 MB

 1 class Solution {
 2     func shipWithinDays(_ weights: [Int], _ D: Int) -> Int {
 3         var lo:Int = weights[0]
 4         var hi:Int = 0
 5         for i in 0..<weights.count
 6         {
 7             lo = max(weights[i], lo)
 8             hi += weights[i]
 9         }
10         while (lo < hi)
11         {
12             var mid:Int = (hi+lo)/2
13             if can(weights, D, mid)
14             {
15                 hi = mid
16             }
17             else
18             {
19                 lo = mid + 1
20             }
21         }
22         return lo        
23     }
24     
25     func can(_ weights: [Int], _ D: Int,_ cap:Int) -> Bool
26     {
27         var cd:Int = 0
28         var ans:Int = 1
29         for i in 0..<weights.count
30         {
31             if cd + weights[i] > cap
32             {
33                 ans += 1
34                 cd = 0
35             }
36             cd += weights[i]
37         }
38         return ans <= D        
39     }
40 }

456ms

 1 class Solution {
 2     func shipWithinDays(_ weights: [Int], _ D: Int) -> Int {
 3         let sum = weights.reduce(0) { $0 + $1 }
 4         var left = sum / D
 5         var right = sum
 6         
 7         while right - left > 1 {
 8             let mid = (right - left) / 2 + left
 9             let result = canShip(weights, D, c: mid)
10             
11             if result {
12                 right = mid
13             } else {
14                 left = mid + 1
15             }
16         }
17         
18         return canShip(weights, D, c: left) ? left : right
19     }
20     
21     private func canShip(_ weights: [Int], _ D: Int, c: Int) -> Bool {
22         var current = 0
23         var days = 1
24         
25         for weight in weights {
26             if weight > c {
27                 return false
28             } else if current + weight > c {
29                 days += 1
30                 current = weight
31             } else {
32                 current = current + weight
33             }
34             
35             if days > D {
36                 return false
37             }
38         }
39         
40         return true
41     }
42 }

460ms

 1 class Solution {
 2     func shipWithinDays(_ weights: [Int], _ D: Int) -> Int {
 3         // Binary serach on range [max value in array, sum]
 4         
 5         if weights.count == 0 { return 1 }
 6         
 7         var sum = 0
 8         var maxVal = Int.min
 9         
10         for weight in weights {
11             sum += weight
12             maxVal = max(maxVal, weight)
13         }
14         
15         var left = maxVal, right = sum
16         
17         
18         while left < right {
19             let W = (left + right) / 2
20             
21             if canSuccess(weights, D, W) {
22                 right = W
23             } else {
24                 left = W + 1
25             }
26             
27         }
28         
29         return max(right, 1)
30     }
31     
32     /*
33      * Checking if the task can be done with current res
34      *
35      */
36     private func canSuccess(_ weights:[Int], _ D: Int, _ W: Int) -> Bool {
37         var curWeight = 0
38         var curDay = 0
39         
40         
41         for weight in weights {
42             if curWeight + weight > W {
43                 curDay += 1
44                 curWeight = weight
45             } else {
46                 curWeight += weight
47             }
48             
49             if curDay > D { return false }
50         }
51         
52         if curWeight > 0 { curDay += 1 }
53 
54         return curDay <= D
55         
56     }
57 }

464ms

 1 class Solution {
 2     func shipWithinDays(_ weights: [Int], _ D: Int) -> Int {  
 3         let maxv = weights.max()!, sum = weights.reduce(0, +)
 4         var left = max(sum/weights.count, maxv), right = sum
 5         var ans = right
 6         var curCap = ans, curDayCost = 0
 7         while left < right {
 8             let midv = (left+right)/2
 9             curCap = midv; curDayCost = 1
10             for w in weights {
11                 if curCap < w {
12                     curCap = midv; curDayCost += 1
13                 }
14                 curCap -= w
15             }
16 
17             if curDayCost <= D {
18                 ans = midv
19                 right = midv
20             }
21             else {
22                 left = midv+1
23             }
24         }
25         return ans
26     }
27 }

476ms

 1 class Solution {
 2     func shipDay(weights: [Int], capacity: Int) -> Int {
 3         var current = 0, result = 0
 4         
 5         for weight in weights {
 6             if current + weight > capacity {
 7                 current = weight
 8                 result += 1
 9             } else {
10                 current += weight
11             }
12         }
13         
14         if current != 0 {
15             result += 1
16         }
17         return result
18     }
19     func shipWithinDays(_ weights: [Int], _ D: Int) -> Int {
20         var start = weights.reduce(Int.min, max), end = weights.reduce(0, +)
21         
22         while start != end {
23             let mid = (start + end) / 2
24             if shipDay(weights: weights, capacity: mid) > D {
25                 start = mid + 1
26             } else {
27                 end = mid
28             }
29         }
30         
31         return start
32     }
33 }