LeetCode1011.https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/
暴力解法：
复杂写法，一次一次尝试，超时！！！
// // 超时 // class Solution { // int[] sumN; // public int shipWithinDays(int[] weights, int D) { // // 前N个货物的总重量 // sumN = new int[weights.length]; // int curSum=0; // for (int i = 0; i < weights.length; i++) { // sumN[i] =curSum+weights[i]; // // System.out.println(sumN[i]); // curSum += weights[i]; // } // // 边界条件 // if(D==1){ // return sumN[sumN.length-1]; // } // sol(weights,0,0,0,D); // return bestValue; // } // int bestValue = Integer.MAX_VALUE; // /** // * 有两种放法，自己单独放一堆，或者与前面的放一在堆 // * @param weights // * @param curIndex // * @param lastSum 上一个堆的和 // * @param maxSum 前面所有堆的最大值 // * @param D 剩余堆数 // * @return // */ // public void sol(int[] weights,int curIndex,int lastSum,int maxSum, int D){ // // D为1则剩余所有放一堆(注！！！有可能D为一堆的时候可以将当前与之前的合并！！而不是往后放！！) // // 应该改为D==0 的时候return D等于1 不需要return！！！ // if(D==0){ // return; // } // //(注!!!在没有return的条件下，不要修改形参中的值) 该语句不能省，当堆分配完必须计算后续结果，但不能return由于后面的可能会分配到已有的堆中。 // if(D==1){ // // 将curIndex和以后的堆放一起的情况 // int temp = Math.max(maxSum,sumN[sumN.length-1]-sumN[curIndex-1]); // bestValue = Math.min(bestValue,temp); // } // if(curIndex == weights.length ){ // bestValue = Math.min(bestValue,maxSum); // return ; // } // // 当剩下的数刚好只剩D那么每一个数放一堆(注!!!在没有return的条件下，不要修改形参中的值) // if(weights.length-curIndex == D){ // // 比较之前的堆，与剩余堆的最大值 // for(int i = curIndex; i<weights.length; i++){ // maxSum = Math.max(maxSum,weights[i]); // } // bestValue = Math.min(bestValue,maxSum); // return; // } // // 自己放一堆 // sol(weights,curIndex+1,weights[curIndex],Math.max(weights[curIndex],maxSum),D-1); // // 和上一组放一堆(排除上一组没有的情况:第一次放) // if(lastSum>0) { // sol(weights, curIndex + 1, weights[curIndex] + lastSum, Math.max(weights[curIndex] + lastSum, maxSum), D); // } // } // }
看了解答：二分法
正确解：
class Solution { // 利用二分法，找到承载能力，判断该值是否可以运完所有的货 // 承载能力一定是在第一个货物的重量和所有货物重量之间的（存在问题） // 注!!!必须是最大的一个货物的重量开始，否则中间会有装不下的!!! public int shipWithinDays(int[] weights, int D) { // 前N个货物的总重量 int[] sumN = new int[weights.length]; int curSum=0; // 最大货物重量 int maxSize=0; for (int i = 0; i < weights.length; i++) { maxSize = Math.max(maxSize,weights[i]); sumN[i] =curSum+weights[i]; curSum += weights[i]; } return midSearch(maxSize, curSum, sumN, D); } public int midSearch(int start, int end, int[] sumN, int D){ if(start == end){ return start; } // 找到当前中间承载量 int mid = (start + end)/2; // System.out.println("尝试装载："+mid); // 判断当前中间承载量能否满足 if(canLoad(mid, D, sumN)){ // 往左边找，因为右边一定可以承载 return midSearch(start, mid, sumN, D); }else{ // 不能承载，说明在右边 return midSearch(mid+1, end, sumN, D); } } // 判断是否可以承载 // 贪心 public boolean canLoad(int load, int D, int[] sumN){ // 上一次装的重量 int lastload=0; // 装了几次,注!!!从1开始因为装不下当前值的时候，说明前面已经装了一次，本次开始是第二次!!! int times=1; // System.out.println("*****当前装载******"+load); for(int i=0; i<sumN.length; i++){ // 下面成立表示当前货物装不下 if(sumN[i] - lastload > load){ lastload = sumN[i-1]; times++; // System.out.println("当前装不下，上次装载量："+lastload+",当前装载次数："+times); } if(times>D){ return false; } } // System.out.println("装载成功使用次数"+times); return true; } }
看到类似题：
Leetcode875
class Solution { public int minEatingSpeed(int[] piles, int h) { // 类似Q1011送包裹问题二分法解决 int maxPile=0; for(int i=0; i<piles.length; i++){ maxPile = Math.max(maxPile,piles[i]); } return find(1, maxPile, piles, h); } // 在最小速度和最大速度之间 public int find(int start, int end, int[] piles,int h){ if(start == end){ return start; } // 当前速度(取中值) int mid = (start+end)/2; System.out.println("当前速度："+mid); if(canFinish(mid ,h ,piles)){ return find(start, mid, piles, h); }else{ return find(mid+1, end, piles, h); } } // 是否可以以当前速度完成 public boolean canFinish(int V, int h, int[] piles){ int times=0; for(int i=0; i<piles.length; i++){ // times += (piles[i]/V + 1); 注！！！，当piles刚好为V时吃了两次，因此错误。所以使用向右取整数 times += Math.ceil((float)piles[i]/V); } // 使用次数大于h表示吃不完 if(times > h){ System.out.println("只能吃"+h+"次，吃了"+times+"次,没吃完"); return false; } System.out.println("只能吃"+h+"次，吃了"+times+"次,吃完了"); return true; } }
二分法思路：
1.取值有一定的范围，从可能的最小的范围和最大的范围每次取中间值逼近。
就如第一题送货，最小量是最大货物的重量，最大量是所有的货物重量之和。
第二题中，最小量是1（每次吃1根香蕉），最大量是所有堆的最大值（一次只能吃一堆）。
2.取中间值mid=(start+end)/2.
3.判断中间值的情况：
中间值如果可以满足，那么最后的结果一定在左边或者中间位置，那么递归调用solution(start,mid)。
相反就是solution(mid+1,end)。