410. Split Array Largest Sum

https://leetcode.com/problems/split-array-largest-sum/

solution

• Binary search

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)]

  • 类似背包搜索的范围，从每一个可选中检查

378. Kth Smallest Element in a Sorted Matrix

668. Kth Smallest Number in Multiplication Table

1011. Capacity To Ship Packages Within D Days

*1231. Divide Chocolate

875. Koko Eating Bananas

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)

*774. Minimize Max Distance to Gas Station

1201. Ugly Number III

• 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

• binary search

• heap

1482. Minimum Number of Days to Make m Bouquets

*1891. Cutting Ribbons

2141. Maximum Running Time of N Computers