LintCode 183. Wood Cut 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/wood-cut/

解题思路

题目意思要把一组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; 
    } 
}