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
defsplitArray(self,nums: List[int],m:int) ->int: n =len(nums) dp = [[sys.maxsize] * (m+1) for _ inrange(n+1)] dp[0][0] =0 accu_sum = [0] * (n+1)for i, num inenumerate(nums): accu_sum[i+1]= accu_sum[i]+ numfor i inrange(1, n+1):for j inrange(1, m+1):for k inrange(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 條件
defsplitArray(self,nums: List[int],m:int) ->int: l =max(nums) r =sum(nums ans = rwhile l < r: mid = (l+r)//2 sumUp =0 count =1for n in nums:if sumUp+n > mid: count+=1 sumUp=nelse: sumUp+=nif count <= m: ans =min(ans, mid) r = midelse: l = mid+1return 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 =5Output:15Explanation:A ship capacity of 15is the minimum to ship all the packages in5 days like this:1st day:1,2,3,4,52nd day:6,73rd day:84th day:95th day:10
Some logic as 410
defshipWithinDays(self,weights: List[int],D:int) ->int: left =max(weights) right =sum(weights) ans = rightwhile left < right: mid = (right+left)//2 sumUp, split =0,1for n in weights:if sumUp+n > mid: split+=1 sumUp = nelse: sumUp+=nif split > D: left = mid+1else: 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 =9Output: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^8A possible function 利用 利用distance 得到的 gas station 數比較"""defminmaxGasDist(self,stations: List[int],K:int) ->float: left, right =0,10**8defpossible(dis): count =0for i inrange(len(stations)-1): count += (stations[i+1]- stations[i])//disreturn count <= Kwhile right - left >10**-6: mid = (right + left)/2ifpossible(mid): right = midelse: left = midreturn left