- 前言
- 一、在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 {
// 逆向思维 + 二分法灵活变体(变判定方式,超有意思。)变体也称抽象类二分。
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);
}
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天内送达包裹的能力–官方题解


![在D天内送达包裹的能力[抽象类二分--抽象判定方式] 在D天内送达包裹的能力[抽象类二分--抽象判定方式]](http://www.mshxw.com/aiimages/31/961554.png)
