class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
left = max(nums)
right = sum(nums)
while left < right:
mid = (left + right) // 2
if self.check(nums, mid, k):
right = mid
else:
left = mid + 1
return left
def check(self, nums, mid, k):
count = 1
cur_sum = 0
for num in nums:
cur_sum += num
if cur_sum > mid:
count += 1
cur_sum = num
if count > k:
return False
return True
时间复杂度：O()
空间复杂度：O()
dynamic programming
follow up
二分搜索范围: [max(nums), sum(nums)]
类似背包搜索的范围，从每一个可选中检查
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
left = 1 # 注意左边界, 不是min(piles)
right = max(piles)
while left < right:
mid = left + (right - left) // 2
if self.get_eating_hours(piles, mid) > h: # 注意 等于是在right中
left = mid + 1
else:
right = mid
return left
def get_eating_hours(self, piles, speed):
hour = 0
for pile in piles:
hour += math.ceil(pile / speed)
return int(hour)
brute force
class Solution:
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
i = j = k = 1
while n > 0:
smallest = min(a * i, b * j, c * k) # 解决不同ijk会产生相同重复值的问题
n -= 1
if i * a == smallest:
i += 1
if b * j == smallest:
j += 1
if c * k == smallest:
k += 1
return smallest