算法题:切木头
问题1
有这么一组木头(用数组int[]表示),木头长度>=1且长短不一
木头只能切短、不能拼接
给定一个要求的木头长度len和一组木头woods,要求将woods切成长度均为len的木头,请问最多能切出多少根?
解题思路
题目不难,因为只能切短不能拼接,所以直接循环遍历woods,分别将每根木头切成要求的长度
叠加每根木头能切出的要求长度木头的数量,即可求解
代码实现
public static Integer cutWoods2SpecifyLen(int[] woods, int len) {
if (woods == null || woods.length == 0) {
return 0;
}
int result = 0;
for (int wood : woods) {
result += wood / len;
}
return result;
}
时间复杂度O(n)
空间复杂度O(1)
测试验证一下
public static void main(String[] args) {
int[] woods = {100, 110, 50, 60, 100, 90};
int specifyLen = 30;
System.out.println(Arrays.toString(woods));
System.out.printf("给定一组木头,要求切成%d长度,最多能切成%d根%n", specifyLen, cutWoods2SpecifyLen(woods, specifyLen));
}
问题2
问题1是要求给定要求的长度,求能切成多少段等长的木头
进阶一下,如果给定需要的等长木头的数量,求切出木头的最长长度呢?
如上图,给定一组木头,要求切出9根等长的木头,求能满足条件木头的最长的长度?
解题思路
首先,这道题中其实一共有两个变量:切除木头的长度len、最终切出的木头根数num
并且这两个变量之间是相互制约的关系,此消彼长
如果len大,则num必然会变小
反之,则num必然会变大
num的大小同样也会影响len大小,同样成反比
那么我们就可以考虑先固定其中一个变量,然后就能求出另外一个变量了
其次我们应该思考,能满足要求的木头长度的范围
最短肯定是1,这种情况下木头可以切成100+110+50+60+100+90=510根
510>9,满足条件
易知这组木头中最长的长度是max=110,
这种情况下能切出满足条件的木头根数是1
1<9,不满足条件
所以题目要求的范围必定是在(1,110)范围内
那么我们现在就是需要在(1,110)这个范围内找到那个合适的值
一个增序的连续区间,要找到目标值,应该用什么办法呢?
很明显:二分法嘛
所以这道题的解题思路就是在(1,110)范围内使用二分查找
在指定能切出的最大木头长度len的情况下,判断得出的nums是否满足条件(nums>=9)
从而求出最大的nums
代码实现
public static Integer cutWoods2SpecifyNum(int[] woods, int num) {
if (woods == null || woods.length == 0) {
return 0;
}
int result = 0;
int min = 1;
int max = getMaxLen(woods);
while (min + 1 < max) {
result = (min + max) / 2;
// 计算在给定长度result的情况,能够切出几根
int numTemp = cutWoods2SpecifyLen(woods, result);
if (numTemp >= num) {
min = result;
} else {
max = result;
}
}
if (cutWoods2SpecifyLen(woods, max) >= num) {
return max;
}
if (cutWoods2SpecifyLen(woods, min) >= num) {
return min;
}
return result;
}
private static int getMaxLen(int[] woods) {
int result = woods[0];
for (int i = 1; i < woods.length; i++) {
if (woods[i] > result) {
result = woods[i];
}
}
return result;
}
时间复杂度O(l*logmax),l为woods的数量,max为woods中最长木头的长度
空间复杂度O(1)
可能有些人会觉得这个二分实现有点别扭
这是我从一位大牛那里学到的一个二分法通用公式
容易理解而且容易掌握,有兴趣的话我回头可以专门写一篇博客讲讲这个二分模板代码
测试验证一下
没有问题
public static void main(String[] args) {
int[] woods = {100, 110, 50, 60, 100, 90};
int specifyNum = 9;
System.out.println(Arrays.toString(woods));
System.out.printf("给定一组木头,要求切成等长的%d跟,能得到的最长长度为%d%n", specifyNum, cutWoods2SpecifyNum(woods, specifyNum));
}
文/戴先生@2021年11月15日