LintCode 183. Wood Cut 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/wood-cut/
Given n pieces of wood with length L[i]
(integer array). Cut them into small pieces to guarantee you could have equal or more than k pieces with the same length. What is the longest length you can get from the n pieces of wood? Given L & k, return the maximum length of the small pieces.
Notice
You couldn’t cut wood into float length.
For L=[232, 124, 456]
, k=7
, return 114
.
解题思路
题目意思要把一组L[i] 中的木头切成同样长度,并且需要至少切成k个木头。求能把这组木头切成至少k个木头的最大同样长度。
题目实际是考察Binary Search二分法的应用。类似常见二分法问题寻找一组数列中某个目标值的位置一样,这道题也是寻找一个位置,即一个最大的木头同样长度。
找到L[i]中最大的木头长度,作为二分法初始值的end。
创建count函数,用来计算把L[i]中的木头切成一定长度后,木头的数量之和。二分法查找木头单位长度的区间[1,end]。当二分发现在区间中间位置的木头数量 > k时,继续增大木头长度,start = mid。当二分发现在区间中间位置的木头数量 < k时,则需要减小木头长度,end = mid。因为L[i]中的原始木头也有可能有长度相等的情况,所以当二分发现在区间中间位置的木头数量 = k时,把start也是设为mid,start = mid。最后二分循环到只剩下两个数值时候,先检查end情况。若end放入count函数的返回值 >= k, 则end为最大单位可切木头长度。 若end放入count函数的返回值 < k,再检查start情况。若start放入count函数的返回值 >= k, 则start为最大单位可切木头长度。 若都不满足条件,则返回0。
参考代码
public class Solution { /** *@param L: Given n pieces of wood with length L[i] *@param k: An integer *return: The maximum length of the small pieces. */ public int woodCut(int[] L, int k) { if (L == null || L.length == 0 || k <= 0) { return 0; } int start = 0; int end = getMaxInArray(L); while (start + 1 < end) { int mid = start + (end - start) / 2; if (getNumberOfPieces(L, mid) < k) { end = mid; } else { start = mid; } } if (getNumberOfPieces(L, end) >= k) { return end; } else { return start; } } private int getMaxInArray(int[] L) { int max = L[0]; for (int number : L) { max = number >= max ? number : max; } return max; } private int getNumberOfPieces(int[] L, int unitLength) { int total = 0; for (int wood : L) { total += (wood / unitLength); } return total; } }