最近參加了很多面試，然后手撕代碼環(huán)節(jié)也沒有我想象的那么恐怖，但是感覺自身題目還是寫的太少了，之后要多多總結(jié)。

剪繩子 剪繩子II

這道題是一個(gè)數(shù)學(xué)問題，要點(diǎn)有兩點(diǎn)：

1. 盡量分割的繩子長度相等：這點(diǎn)通過不等式證明

2. 長度分成三段時(shí)有最大的乘積：這點(diǎn)通過隱函數(shù)求導(dǎo)，求駐點(diǎn)可以得到

則：n = m^a?+?b，m等于3，即分成三段，b有三種取值的可能：

1. b == 0?

2. b == 1 此時(shí)，n = 3^a < n = 3^(a-1)*4 所以可以從a中取一個(gè)出來

3. b == 2 此時(shí)，n = 2*(3^a)

剪繩子II和I差不多，但是因?yàn)?^a可能溢出，所以需要取mod。通過取余運(yùn)算可知：

(3^a)%p?= ((3^(a-k)%p)?*??(3^(k)%p)) % p，所以可以通過將a分解成比較小的數(shù)字然后取余，之后的乘積再取余的方式避免溢出。

這兩題還需要額外注意一個(gè)點(diǎn)，就是當(dāng)n小于3的時(shí)候因?yàn)?，m>1所以也要進(jìn)行分割，直接返回n-1。

代碼如下：

數(shù)值的整數(shù)次方

主要的思路是將指數(shù)分解成二進(jìn)制的數(shù)，這樣就可以將大的數(shù)分解成小的數(shù)字處理。這里還可以計(jì)算當(dāng)指數(shù)為負(fù)數(shù)的情況，如果直接取負(fù)數(shù)會出現(xiàn)溢出，所以需要使用long保證。

重建BST

給定先序和中序遍歷的數(shù)組，需要構(gòu)建一個(gè)BST。具體的邏輯是對于先序遍歷中的每一個(gè)val，在中序遍歷中找到，然后將數(shù)組分成左右兩個(gè)部分，分別構(gòu)建新的樹。但是需要注意的是，這個(gè)查找的過程可以使用hashMap進(jìn)行加速。

最小的K個(gè)數(shù)字

這道題我在字節(jié)跳動的面試被聞到過，當(dāng)時(shí)在面試官的引導(dǎo)下，勉勉強(qiáng)強(qiáng)的完成了算法。

這道題主要使用了二分的思想：

對于數(shù)組[5 4 2 1 3 6]而言，因?yàn)橹恍枰业阶钚〉腒個(gè)數(shù)字，不需要使用排序。所以可以通過快速排序中的劃分操作，以一個(gè)數(shù)字為樞軸，左邊的全部小于，右邊的全部大于。假設(shè)滿足條件的樞軸的下標(biāo)為i，i的左邊一定有i個(gè)數(shù)字，當(dāng)i==k時(shí)，左邊的就是最小的K個(gè)數(shù)字。如果不滿足條件，當(dāng)i>k時(shí)，最小的K個(gè)數(shù)字一定在不包括樞軸自身的左邊，反之則在右邊。最后可以得到如下所示的代碼：