最近参加了很多面试，然后手撕代码环节也没有我想象的那么恐怖，但是感觉自身题目还是写的太少了，之后要多多总结。

剪绳子 剪绳子II

这道题是一个数学问题，要点有两点：

1. 尽量分割的绳子长度相等：这点通过不等式证明

2. 长度分成三段时有最大的乘积：这点通过隐函数求导，求驻点可以得到

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

1. b == 0 

2. b == 1 此时，n = 3^a < n = 3^(a-1)*4 所以可以从a中取一个出来

3. b == 2 此时，n = 2*(3^a)

剪绳子II和I差不多，但是因为3^a可能溢出，所以需要取mod。通过取余运算可知：

(3^a)%p = ((3^(a-k)%p) *  (3^(k)%p)) % p，所以可以通过将a分解成比较小的数字然后取余，之后的乘积再取余的方式避免溢出。

这两题还需要额外注意一个点，就是当n小于3的时候因为，m>1所以也要进行分割，直接返回n-1。

代码如下：

数值的整数次方

主要的思路是将指数分解成二进制的数，这样就可以将大的数分解成小的数字处理。这里还可以计算当指数为负数的情况，如果直接取负数会出现溢出，所以需要使用long保证。

重建BST

给定先序和中序遍历的数组，需要构建一个BST。具体的逻辑是对于先序遍历中的每一个val，在中序遍历中找到，然后将数组分成左右两个部分，分别构建新的树。但是需要注意的是，这个查找的过程可以使用hashMap进行加速。

最小的K个数字

这道题我在字节跳动的面试被闻到过，当时在面试官的引导下，勉勉强强的完成了算法。

这道题主要使用了二分的思想：

对于数组[5 4 2 1 3 6]而言，因为只需要找到最小的K个数字，不需要使用排序。所以可以通过快速排序中的划分操作，以一个数字为枢轴，左边的全部小于，右边的全部大于。假设满足条件的枢轴的下标为i，i的左边一定有i个数字，当i==k时，左边的就是最小的K个数字。如果不满足条件，当i>k时，最小的K个数字一定在不包括枢轴自身的左边，反之则在右边。最后可以得到如下所示的代码：