## 問題1

圖片

• 有這么一組木頭（用數(shù)組int[]表示），木頭長度>=1且長短不一

• 木頭只能切短、不能拼接

• 給定一個要求的木頭長度len和一組木頭woods，要求將woods切成長度均為len的木頭，請問最多能切出多少根？

### 解題思路

題目不難，因為只能切短不能拼接，所以直接循環(huán)遍歷woods，分別將每根木頭切成要求的長度

疊加每根木頭能切出的要求長度木頭的數(shù)量，即可求解

### 代碼實現(xiàn)

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

時間復(fù)雜度O(n)

空間復(fù)雜度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是要求給定要求的長度，求能切成多少段等長的木頭

• 進(jìn)階一下，如果給定需要的等長木頭的數(shù)量，求切出木頭的最長長度呢？

圖片

如上圖，給定一組木頭，要求切出9根等長的木頭，求能滿足條件木頭的最長的長度？

### 解題思路

首先，這道題中其實一共有兩個變量：切除木頭的長度len、最終切出的木頭根數(shù)num

并且這兩個變量之間是相互制約的關(guān)系，此消彼長

如果len大，則num必然會變小

反之，則num必然會變大

num的大小同樣也會影響len大小，同樣成反比

那么我們就可以考慮先固定其中一個變量，然后就能求出另外一個變量了

其次我們應(yīng)該思考，能滿足要求的木頭長度的范圍

最短肯定是1，這種情況下木頭可以切成100+110+50+60+100+90=510根

510>9，滿足條件

圖片

易知這組木頭中最長的長度是max=110，

這種情況下能切出滿足條件的木頭根數(shù)是1

1<9，不滿足條件

所以題目要求的范圍必定是在（1，110）范圍內(nèi)

那么我們現(xiàn)在就是需要在（1，110）這個范圍內(nèi)找到那個合適的值

一個增序的連續(xù)區(qū)間，要找到目標(biāo)值，應(yīng)該用什么辦法呢？

很明顯：二分法嘛

所以這道題的解題思路就是在（1，110）范圍內(nèi)使用二分查找

在指定能切出的最大木頭長度len的情況下，判斷得出的nums是否滿足條件（nums>=9）

從而求出最大的nums

### 代碼實現(xiàn)

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

時間復(fù)雜度O(l*logmax)，l為woods的數(shù)量，max為woods中最長木頭的長度

空間復(fù)雜度O(1)

可能有些人會覺得這個二分實現(xiàn)有點別扭

這是我從一位大牛那里學(xué)到的一個二分法通用公式

容易理解而且容易掌握，有興趣的話我回頭可以專門寫一篇博客講講這個二分模板代碼

測試驗證一下

沒有問題

    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日

---end---