算法题：切木头

你好戴先生

发布于 2021-11-25 14:55:44

5740

发布于 2021-11-25 14:55:44

文章被收录于专栏：戴言泛滥

## 问题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日

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-11-16，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自你好戴先生微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度