Split Array Largest Sum
410. Split Array Largest Sum
Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.
Input:
nums = [7,2,5,10,8]
m = 2
Output:
18
[7,2,5] and [10,8]
DP
dp[i][j] = 前 i 個 num 構成 j 個 subarray 的 minimize largest sum
先計算每個index的presum
dp[i][j] = min(dp[i][j], max(dp[k][j-1], presum[i] - presum[k]))
def splitArray(self, nums: List[int], m: int) -> int:
n = len(nums)
dp = [[sys.maxsize] * (m+1) for _ in range(n+1)]
dp[0][0] = 0
accu_sum = [0] * (n+1)
for i, num in enumerate(nums):
accu_sum[i+1] = accu_sum[i] + num
for i in range(1, n+1):
for j in range(1, m+1):
for k in range(0, i):
dp[i][j] = min(dp[i][j], max(dp[k][j-1], accu_sum[i]-accu_sum[k]))
return dp[n][m]
Binary Search
利用binary search 找到upperbound
利用 count subarray numbers 作為 left and right 條件
def splitArray(self, nums: List[int], m: int) -> int:
l = max(nums)
r = sum(nums
ans = r
while l < r:
mid = (l+r)//2
sumUp = 0
count = 1
for n in nums:
if sumUp+n > mid:
count+=1
sumUp=n
else:
sumUp+=n
if count <= m:
ans = min(ans, mid)
r = mid
else:
l = mid+1
return ans
1011. Capacity To Ship packages Within D Days
Find the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D
days.
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
Some logic as 410
def shipWithinDays(self, weights: List[int], D: int) -> int:
left = max(weights)
right = sum(weights)
ans = right
while left < right:
mid = (right+left)//2
sumUp, split = 0, 1
for n in weights:
if sumUp+n > mid:
split+=1
sumUp = n
else:
sumUp+=n
if split > D:
left = mid+1
else:
ans = min(ans, mid)
right = mid
return ans
774. Minimize Max Distance to Gas Station
On a horizontal number line, we have gas stations at positions stations[0], stations[1], ..., stations[N-1]
, where N = stations.length
.
Now, we add K
more gas stations so that D, the maximum distance between adjacent gas stations, is minimized.
Return the smallest possible value of D.
Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9
Output: 0.500000
stations.length
will be an integer in range[10, 2000]
.stations[i]
will be an integer in range[0, 10^8]
.K
will be an integer in range[1, 10^6]
.Answers within
10^-6
of the true value will be accepted as correct.
"""
Binary Search
找出最大的可能number 0 ~ 10^8
A possible function 利用 利用distance 得到的 gas station 數比較
"""
def minmaxGasDist(self, stations: List[int], K: int) -> float:
left, right = 0, 10**8
def possible(dis):
count = 0
for i in range(len(stations)-1):
count += (stations[i+1] - stations[i])//dis
return count <= K
while right - left > 10**-6:
mid = (right + left)/2
if possible(mid):
right = mid
else:
left = mid
return left
Last updated
Was this helpful?