ゼロから始めるLeetCode Day90「1011. Capacity To Ship Packages Within D Days」
概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。
と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。
ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
Python3で解いています。
前回
ゼロから始めるLeetCode Day89 「62. Unique Paths」
次回
ゼロから始めるLeetCode Day91「153. Find Minimum in Rotated Sorted Array」
Twitterやってます。
問題
1011. Capacity To Ship Packages Within D Days
難易度はMedium。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。
コンベアベルトには，ある港から別の港へD日以内に出荷しなければならない荷物がある．
コンベヤベルト上のi番目の荷物には重み[i]がある． 毎日，コンベヤベルト上の荷物を船に積み込む（重さで与えられた順序で）．船の最大重量容量を超える重量を積むことはできない．
コンベヤベルト上のすべての荷物がD日以内に出荷されるようになる船の最小重量容量を返します。
Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 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,2,2,4,1,4], D = 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
解法
class Solution:
def shipWithinDays(self, weights: List[int], D: int) -> int:
min_num = max_num = 0
min_num = max(weights)
max_num = sum(weights)
while min_num < max_num:
mid = (min_num + max_num)//2
days = temp_weight = 0
for i in weights:
temp_weight += i
if temp_weight > mid:
days += 1
temp_weight = i
if days + 1 <= D:
max_num = mid
else:
min_num = mid+1
return min_num
# Runtime: 508 ms, faster than 92.24% of Python3 online submissions for Capacity To Ship Packages Within D Days.
# Memory Usage: 17.1 MB, less than 7.21% of Python3 online submissions for Capacity To Ship Packages Within D Days.
二分探索で考えました。
ここでの最小値はリストの中の最大値、そして最大値はリストの合計値となります。
それぞれの値を取得し、保管、そして二分探索にかけて日程と照らし合わせていくことで、最低の積載量を導くことにつながるため、こういった条件になります。
この二つの値である理由としてはどんなに値が変わったとしても積載量は下限はリストの中の最低値でありますし、積載量の最大値はリストの総和となるためです。逆に言えばこの下限と上限の値の設定さえ行えられればかなり楽になると思います。
例1のテストケースの場合、min_numとmax_numにはそれぞれ10と55が入ります。そして、この関係がmin_num < max_numであり続ける間、中間の値のmidには二分探索おなじみの処理を行います。
そしてその後にdaysとDの関係性を元に処理をかけ、どんどん範囲を狭めていき、最終的に最小積載量が導かれる、という原理です。
なかなか、説明するのが難しいな、と思って分かりやすい例はないかなと探し回っていたらJavaで解説している動画がありました。
書かれている言語自体はJavaなのですが、根本的な考え方は一緒なので、僕の解説で分かりづらい場合はこちらをみてみるとよいかもしれません。
では今回はここまで。お疲れ様でした。
コメント
コメントを投稿