在D天内送达包裹的能力[抽象类二分--抽象判定方式]

前言

个人刷题感觉，从基础 -> (基础抽象/数学/脑筋急转弯/dp/高级数据结构/逆向思维/逻辑分析与整理/等) -> 基础灵活组合成困难题 -> 组合抽象。该题很好的诠释了抽象的魅力。

一、在D天内送达包裹的能力

二、抽象二分判定方式

target:顺序将数组截成days个子数组，求里面最大和即承载重量。
而分成days个子数组，要求子数组分配是非常均匀的，意思就是最大值和尽可能小。
----------------------
// 上面思路是以days为参照物，去寻找承载重量x.但是想不出来。（直观法，自己的初始想法，解不出来。）
// 下面的思路是以x为参照物，去寻找days,让days满足要求。（逆向思维法，借鉴官方答案。）
----------------------
承载重量一定是从max(weights)(不能拆分包裹) - sum(weights)(一下装完)的，所以可二分寻找这个承载重量是多少。
当承载重量x分成的子数组为y组时，
情况1：y如果大于days，那么就说明x小了，需要把寻找更大的x，即left = mid + 1
情况2：y如果小于等于days，那么说明x大了，也可能刚好，需要把上边界定在mid，即right = mid

package everyday;

import java.util.Arrays;

// 在D天内送达包裹的能力。
public class ShipWithinDays {
    
    /* target:顺序将数组截成days个子数组，求里面最大和即承载重量。 而分成days个子数组，要求子数组分配是非常均匀的，意思就是最大值和尽可能小。 ---------------------- // 上面思路是以days为参照物，去寻找承载重量x.但是想不出来。（直观法，自己的初始想法，解不出来。） // 下面的思路是以x为参照物，去寻找days,让days满足要求。（逆向思维法，借鉴官方答案。） ---------------------- 承载重量一定是从max(weights)(不能拆分包裹) - sum(weights)(一下装完)的，所以可二分寻找这个承载重量是多少。 当承载重量x分成的子数组为y组时， y如果大于days，那么就说明x小了，需要把寻找更大的x，即left = mid + 1 y如果小于等于days，那么说明x大了，也可能刚好，需要把上边界定在mid，即right = mid */
    // 逆向思维 + 二分法灵活变体（变判定方式，超有意思。）变体也称抽象类二分。
    public int shipWithinDays(int[] weights, int days) {
    
        // 取数组最小值、数组和，作为二分夹逼寻找的初始左右边界。
        int low = Arrays.stream(weights).max().getAsInt();
        int high = Arrays.stream(weights).sum();
        // 二分寻找最佳承载x
        return binarySearch(weights, low, high, days);
    }

    /** * 二分寻找最佳承载重量x * * @param weights * @param low * @param high * @param days * @return */
    private int binarySearch(int[] weights, int low, int high, int days) {
    
        // 二分夹逼寻找。
        while (low < high) {
    
            int mid = low + (high - low >>> 1);
            // 获取承载重量x = mid时，需要的天数。
            int need = 1, sum = 0;
            for (int w : weights) {
    
                if ((sum += w) > mid) {
    
                    ++need;
                    sum = w;
                }
            }
            // 通过判断所需天数和实际天数的大小，来推断承载重量x是否过大还是过小。
            if (need > days) low = mid + 1;
            else high = mid;
        }
        // 夹逼找到最佳承载重量
        return low;
    }

}

总结

1）抽象基础的魅力，实践–抽象二分判定方式。
2）正向走不通时，试试逆向思维。
3）刷题感觉，从基础 -> (基础抽象/数学/脑筋急转弯/dp/高级数据结构/逆向思维/逻辑分析与整理/等) -> 基础灵活组合成困难题 -> 组合抽象。

参考文献

[1] LeetCode 在D天内送达包裹的能力
[2] LeetCode 在D天内送达包裹的能力–官方题解