木头加工
简单分析
暴力解法就是从1开始遍历所有的长度，对于长度L，计算所有木头可以切多少段，如果满足要求就记录长度并继续增加，如果不满足则终止循环，并返回记录的长度L。
暴力解法的复杂度是O(n*m)其中n是木头数组的长度，m指的是数组中数据最大值，因为对于每一个长度都需要遍历整个数组，而最后的数组大小基本正比于数组中的最大值。
在暴力解法的基础上，我们可以改进为O(n*log m)复杂度的算法，先找到最长的木头长度maxl（数组中的最大值），然后利用二分法搜索0-maxl之间的值，最后输出满足要求的最大值。
程序
public int woodCut(int[] L, int k) {
int l = L.length;
if(l == 0) return 0; //如果输入数组L为空则直接返回0
int maxL = L[0]; //找到数组中的最大值
for(int i = 1; i < l; i++){
int temp = L[i];
if(temp > maxL){
maxL = temp;
}
}
int up = maxL;
int down = 0;
int res = 0;
while(up >= down){ //二分法查找
int len = down + (up - down)/2;
if(len == 0) return 0;
int c = count(L,len);
if(c >= k) {res = res>=len?res:len;down = len + 1;} //符号是>=
else if(c < k) up = len - 1;
}
return res;
}
public int count(int[] L,int length){
int num = 0;
for(int l:L){
num += l/length;
}
return num;
}
}
上面的算法运行速度仍然很慢，在lintcode网站提交以后运行时间是3s以上，很慢。大家可以试着优化一下。
ps：提供一个教训，我是想法是，当最后分割的长度正好是k段时，我再更新最终的结果长度res。也就是把二分搜索部分修改如下
while(up >= down){
int len = down + (up - down)/2;
if(len == 0) return 0;
int c = count(L,len);
if(c < k) up = len - 1;
else{ if(c == k) res = res>=len?res:len; down = len + 1;}
}
首先，上面这个程序是错误的。如果最大值对应的段数不是k的话，那我们的程序就无法输出正确结果。这是我个人尝试中的一点经验。
一些闲话：
博客这边更新的题目都是略带难度的，还有一些只需要简单技巧的题目就不在这里写了，尽量写在github上了。一个不算项目的小项目,现在内容还比较少，大家喜欢可以支持一下。