1011. Capacity To Ship Packages Within D Days

Medium

A conveyor belt has packages that must be shipped from one port to another within D days.

The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.

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

Note:

1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500

题目大意：有一批货物需要从码头运出，货物的重量已知，码头每天的运载能力固定。要求最小的码头运载能力，能够将所有的货物在D天内运完。

解题思路：码头运载能力要小于货物中最大的一个，这样货物才有可能被运完，同时，运载能力要小于货物的总重，否则全部货物一天就运完了，肯定不是目标运载能力。目标运载能力显然在两者之间。对运载能力进行二分搜索，每次用一个运载能力进行试验，看完成运载的天数是否最小。

下面用Go来尝试解题

//1014. Capacity To Ship Packages Within D Days
func shipWithinDays(weights []int, D int) int {
    maxEle := func(xs []int) (max int) {
        max = math.MinInt32
        for _, x := range xs {
            if x > max {
                max = x
            }
        }
        return
    }

    sumEle := func(xs []int) (sum int) {
        for _, x := range xs {
            sum += x
        }
        return
    }

    //the target daily capcity must be within [low, high]
    low := maxEle(weights)
    high := sumEle(weights) + 1
    for low < high {
        mid := low + (high-low)/2
        days := 1  //count days take to ship
        trans := 0 //count weights can be ship in one day
        //try to ship out all weights with selected dayily capcity
        //  mid
        for _, w := range weights {
            if trans+w > mid {
                days++ //need to ship in the next day
                trans += w
                trans = w
            } else {
                trans += w //can be ship today
            }
        }

        if days > D {
            low = mid + 1
        } else {
            high = mid
        }
    }

    return low
}

在Leetcode上测试代码

Success

[Details]
Runtime: 40 ms, faster than 42.67% of Go online submissions for Capacity To Ship Packages Within D Days.
Memory Usage: 7.4 MB, less than 100.00% of Go online submissions for Capacity To Ship Packages Within D Days.

74. Search a 2D Matrix

Medium

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true

Example 2:

Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false

题目大意：在排序好的矩阵中搜索一个元素是否存在。

解题思路：二维矩阵可以描述为一个一维数组，一维索引变为二维索引 matrix[index / cols][index % cols]。

下面尝试用Go解题，

//74. Search a 2D Matrix
func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 {
        return false
    }
    row, col := len(matrix), len(matrix[0])
    if col == 0 {
        return false
    }

    low, high := 0, row*col
    //treat matrix as array and parse row/col index when need to
    //  access element
    for low < high {
        mid := low + (high-low)/2
        r, c := mid/col, mid%col
        if matrix[r][c] == target {
            return true
        }
        if matrix[r][c] > target {
            high = mid
        } else {
            low = mid + 1
        }
    }
    return false
}

在Leetcode上测试代码

Success
[Details]
Runtime: 4 ms, faster than 99.50% of Go online submissions for Search a 2D Matrix.
Memory Usage: 3.8 MB, less than 13.33% of Go online submissions for Search a 2D Matrix.