C/C++教程

LeetCode1011. 在 D 天内送达包裹的能力(二分查找)

本文主要是介绍LeetCode1011. 在 D 天内送达包裹的能力(二分查找),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1011. 在 D 天内送达包裹的能力(二分查找)

解题思路:
先写一个方法判断船的最大运载重量为H时能否在D天内运完
然后二分查找就好了
暂时没有想到其他方法了

class Solution {
    public int shipWithinDays(int[] weights, int D) {
        int left = 0;
        int right = 0;
		for(int i = 0; i < weights.length; i++) {
        	left = Math.max(left, weights[i]);
        	right += weights[i];
        }
		int mid = 0;
		while(left < right) {
			mid = (left+right)/2;
			if(verification(weights, D, mid)) {
				right = mid;
			} else {
				left = mid+1;
			}
		}
		return left;
    }
	
	public boolean verification(int[] weights, int D, int H) {
		int count = 1;
		int weight = 0;
		for(int i = 0; i < weights.length; i++) {
			if(weights[i]+weight <= H) {
				weight += weights[i];
			} else {
				weight = weights[i];
				count++;
			}
		}
		return count <= D;
	}
}

链接:https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/solution/1011-zai-d-tian-nei-song-da-bao-guo-de-n-xwzq/

这篇关于LeetCode1011. 在 D 天内送达包裹的能力(二分查找)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!