本文約1500字,閱讀大概需要8分鐘

今天分享的題目來源於 LeetCode 上的劍指 Offer 系列 面試題14.I 剪繩子。根據統計,近期出現在快手的算法面試環節,屬於中等難度,需要一定的數學功底。

題目鏈接:https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

題目描述

給你一根長度爲 n 的繩子,請把繩子剪成整數長度的 m 段(m、n都是整數,n>1並且m>1),每段繩子的長度記爲 k[0],k[1]...k[m-1] 。請問可能的最大乘積是多少?例如,當繩子的長度是8時,我們把它剪成長度分別爲2、3、3的三段,此時得到的最大乘積是18。

示例1

輸入: 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1

示例2

輸入: 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

題目解析

一、數學推導法

設繩子長度爲,總共拆分爲段,每一段的長度均爲,請問 每一段的長度爲多少時,乘積最大呢?

設繩子的長度爲,且切分爲段,則得到的乘積爲(這裏我們假設每一段的長度均爲,則這道題目就轉化爲一個求函數  關於的一個最大值問題,稍微翻一下大學課本里的高等數學書中求導相關的內容,接着看;

對函數兩邊同時取對數:

上式兩邊對求導,注意,得:

於是

令,則,則;

即,當每一段繩子的長度取時,乘積取得最大值,但是每一段繩子的長度只能取整數,到底是取 2 好 還是取 3 好呢?

當時,等分的話,可以是,也可以是  ,乘積則分別對應和,顯然  ,所以當然是取 3 好了。

也就是說對於長度爲的繩子,我們儘可能以每一段爲 3 進行分割,得到的乘積最大。

當繩子的長度時,也就兩種情況(因爲題目中繩子的長度要求是:

  1. ,只能拆爲,乘積爲 1 ;

  2. ,只能拆爲,乘積爲 2 ;

當繩子的長度時,我們就可以直接用對 3 進行求餘運算,設商數爲,餘數爲,即,其中餘數又分爲三種情況進行處理:

  1. 餘數,此時直接返回即爲最大的乘積,比如是,最大乘積爲;時,最大乘積爲;整除的情況都是如此。

  2. 餘數,此時直接返回是不對的,爲什麼呢?因爲

    所以當時,而是返回. 比如,最大乘積爲;當,最大乘積爲;

  3. 餘數, 此時直接返回即可。比如,最大乘積爲;當,最大乘積爲。

實現代碼

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3){
            return n-1;
        }
        int a = n / 3;
        int b = n % 3;
        if(0 == b){
            return (int)Math.pow(3,a);
        }else if(1 == b){
            return (int)Math.pow(3,a-1) * 4;
        }else{
            return (int)Math.pow(3,a) * 2;
        }
    }
}

複雜度分析

  • 時間複雜度:,實現中僅涉及取整、求餘和求冪運算。

  • 空間複雜度:保存商數的變量 a 和保存餘數的變量 b 僅使用常量空間。

二、動態規劃

當時,就分爲兩種情況:

  1. 時,繩子只能剪爲兩個長度 1 的繩子,最大乘積爲 1;

  2. 時,繩子只能剪爲長度爲 2 和 1 的兩段,最大乘積爲 2;直接返回。

當 n > 3 時,就可以按照動態規劃的邏輯進行處理了:

  1. 初始值爲:

爲什麼這麼設置呢?

因爲對於的繩子而言,我們完全可以拆分得到長度爲 3、2 和 1 的繩子,拆分得到長度爲 3 的繩子不必再拆分,算入乘積的話最大就是 3本身,2 和 1 同理。在舉個栗子,比如,我們可以拆分爲、和,而 3 、2 和 1 都是最終直接作爲計算乘積時的因子出現的,所以.

  1. 遞推公式爲:

對於長度爲的繩子而言,要取得最大乘積,就需要知道它的前 3 個狀態和,而相應的最大乘積分別爲:、和,的最大乘積則取三者中的最大值。

動態規劃的遞推公式爲:

動畫演示

實現代碼

class Solution {
    public int cuttingRope(int n) {
         if(n <= 3){
             return n-1;
         }
         int dp[] = {1,2,3};
         for(int i = 3; i < n; i++) {
          int tmp = Math.max(3 * dp[0],Math.max(2 * dp[1], 1 * dp[2]));
          dp[0] = dp[1];
          dp[1] = dp[2];
          dp[2] = tmp;
         }
         return dp[2];
    }
}

複雜度分析

  • 時間複雜度

  • 空間複雜度,使用的是長度爲 3 的定長數組。

三、貪心方法

按照貪心策略來剪繩子,當時,我們儘可能多地剪長度爲 3 的繩子;當剩下的繩子長度爲 4 時,把繩子剪成長度爲 2 的兩段繩子,因。

實現代碼

class Solution {
    public int cuttingRope(int n) {
      if (n <= 3) {
       return n-1;
      }

      int NumOf3 = n / 3;
      if (n - NumOf3 * 3 == 1) {
       NumOf3--;
      }
      
      int NumOf2 = (n - NumOf3 * 3) / 2;
      
      return (int)Math.pow(3, NumOf3) * (int)Math.pow(2, NumOf2);
    }
}

複雜度分析

  • 時間複雜度:

  • 空間複雜度:

知識點

貪心思想、動態規劃、數學推導

Read More

《隱祕的角落》開播之後就沒下過熱搜?

20年前的幾行代碼竟如此牛逼?驚了

一文湊齊四種變量轉換方法!

End

奶糖貓   

優秀的人都在看   

在看點一下

相關文章