一道快手的算法面試題,沒想到對數學要求還蠻高的!
本文約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 ;
-
,只能拆爲,乘積爲 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;
-
時,繩子只能剪爲長度爲 2 和 1 的兩段,最大乘積爲 2;直接返回。
當 n > 3 時,就可以按照動態規劃的邏輯進行處理了:
-
初始值爲:
爲什麼這麼設置呢?
因爲對於的繩子而言,我們完全可以拆分得到長度爲 3、2 和 1 的繩子,拆分得到長度爲 3 的繩子不必再拆分,算入乘積的話最大就是 3本身,2 和 1 同理。在舉個栗子,比如,我們可以拆分爲、和,而 3 、2 和 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
End
奶糖貓
優秀的人都在看
在看點一下