一、 旋转数组（数组开始有序），寻找最小数。（比如0,1,2,3,4,5,6可以旋转为4,5,6,0,1,2,3等）。
旋转数组特性：
- 部分有序，即变成两个局部有序（但又特例）。
- 前面的有序子数组中的数总是大于等于后面有序子数组中的数（也有特例）。
- 特例是当旋转为0或者刚好为数组长度的整数倍时，数组变回最开始的数组，即有序而非局部有序，还有一个特例是大部分元素都相等。
突破点：
- 因为是有序的（尽管是局部有序），我们还是可以利用这个有序的特性通过二分查找来解决问题。
- 传统的二分查找是通过两个下标指针来指示我们要查找元素的的范围，并且不停折半缩小范围，缩小范围的同时让我们所查找的元素位置夹在两个下标之间；而这题也是类似，只是缩小范围的时候，判断方法有所不同弄，即上面的特性2，中间元素如果大于等于前面元素，则说明最小值在中间元素和以后，如果中间元素小于等于后面的元素，则说明最小值在中间值以前（包括中间值）。
- 特例处理，如果旋转为数组的整数倍长度时直接返回第0个袁术，如果大部分元素都相等时，使得中间值a[left]和a[right]以及a[mid]均相等，则采用顺序查找。
二、 斐波那契数列
常见题目：
-
写一个函数，输入n，求斐波那契数列的第n项。
f(0) = 0; f(1) = 1; f(n) = f(n-1) + f(n-2); -
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求改青蛙跳上一个n级台阶总共有多少种跳法。
-
我们可以用2 X 1 的小矩形横着或者竖着去覆盖更大的矩形。请问8个2 X 1的小矩形无重复的覆盖一个2 X 8 的大矩形，总共有多少种方法？
这些题目都很类似，数列的第n项我们把它当做第n种状态，改变当前状态的方式（改变后为不同于当前状态的两种不同状态）通常有两种。所以当前状态是由前面两种不同状态的结果的和。
三、 位运算
一个整数n（大于0）减去1，在二进制的表示中的特点，因为二进制的表示中，一个位不是0就是1，如果是1，则减1后变为0，运算就此结束，而如果该位是0，则该位向前借1即该位变为2再减去1变为1，因为高位被借1其实也就相当于减1，在该位的运算与前面类似，直到遇到1，运算才结束。
仔细看运算过程发现，有如下特点：
- 运算会在遇到最右边的第一个1结束。
- 运算使得包括最右边第一个1右边的所有位都变得和原来相反，结合第1特性，运算后的二进制表示变为xxxx01111(原来为xxxx10000)。
- 如果与原来的整数做与位运算，则获得效果是将最右边的1变为0.
四、 快速幂的理解
求x的n次方
快速幂的思路就是把n分解为若干2的幂之和，然后从低次幂开始求，由于高次幂可以直接由低次幂求得，因此可以非常高效得求得。
例如求 x 的 10次幂，10可以分解为8 + 2（二进制表示为1000,10）
x的10次幂等于x的8次幂乘以x的2次幂，x的2次幂等于x * x, x的8次幂则等于4个x的2次幂相乘。
double pow(double base, int n)
{
double res = 0.0;
if(n == 0)
return 1;
while(n & 1 == 0){
base *= base;
n >= 1;
}
res = base;
n >= 1;
while(n){
base *= base;
if(n & 1)
res *= base;
n >= 1;
}
return res;
}
网友评论