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

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.

Example

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; 
    } 
}

发表回复

您的电子邮箱地址不会被公开。