一、 旋轉(zhuǎn)數(shù)組（數(shù)組開始有序），尋找最小數(shù)蛀蜜。（比如0,1,2,3,4,5,6可以旋轉(zhuǎn)為4,5,6,0,1,2,3等）特碳。
旋轉(zhuǎn)數(shù)組特性：
- 部分有序诚亚，即變成兩個局部有序（但又特例）。
- 前面的有序子數(shù)組中的數(shù)總是大于等于后面有序子數(shù)組中的數(shù)（也有特例）午乓。
- 特例是當旋轉(zhuǎn)為0或者剛好為數(shù)組長度的整數(shù)倍時站宗，數(shù)組變回最開始的數(shù)組，即有序而非局部有序益愈，還有一個特例是大部分元素都相等梢灭。
突破點：
- 因為是有序的（盡管是局部有序），我們還是可以利用這個有序的特性通過二分查找來解決問題蒸其。
- 傳統(tǒng)的二分查找是通過兩個下標指針來指示我們要查找元素的的范圍敏释，并且不停折半縮小范圍，縮小范圍的同時讓我們所查找的元素位置夾在兩個下標之間摸袁；而這題也是類似钥顽，只是縮小范圍的時候，判斷方法有所不同弄靠汁，即上面的特性2蜂大，中間元素如果大于等于前面元素，則說明最小值在中間元素和以后蝶怔，如果中間元素小于等于后面的元素奶浦，則說明最小值在中間值以前（包括中間值）。
- 特例處理踢星，如果旋轉(zhuǎn)為數(shù)組的整數(shù)倍長度時直接返回第0個袁術(shù)澳叉，如果大部分元素都相等時，使得中間值a[left]和a[right]以及a[mid]均相等斩狱，則采用順序查找耳高。
二、 斐波那契數(shù)列
常見題目：
-
寫一個函數(shù)所踊，輸入n泌枪，求斐波那契數(shù)列的第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的小矩形無重復(fù)的覆蓋一個2 X 8 的大矩形修壕，總共有多少種方法愈捅？
這些題目都很類似，數(shù)列的第n項我們把它當做第n種狀態(tài)慈鸠，改變當前狀態(tài)的方式（改變后為不同于當前狀態(tài)的兩種不同狀態(tài)）通常有兩種蓝谨。所以當前狀態(tài)是由前面兩種不同狀態(tài)的結(jié)果的和。
三青团、 位運算
一個整數(shù)n（大于0）減去1譬巫，在二進制的表示中的特點，因為二進制的表示中督笆，一個位不是0就是1芦昔，如果是1，則減1后變?yōu)?娃肿，運算就此結(jié)束咕缎，而如果該位是0，則該位向前借1即該位變?yōu)?再減去1變?yōu)?料扰，因為高位被借1其實也就相當于減1凭豪，在該位的運算與前面類似，直到遇到1记罚，運算才結(jié)束墅诡。
仔細看運算過程發(fā)現(xiàn)，有如下特點：
- 運算會在遇到最右邊的第一個1結(jié)束桐智。
- 運算使得包括最右邊第一個1右邊的所有位都變得和原來相反末早，結(jié)合第1特性，運算后的二進制表示變?yōu)閤xxx01111(原來為xxxx10000)说庭。
- 如果與原來的整數(shù)做與位運算然磷，則獲得效果是將最右邊的1變?yōu)?.
四、 快速冪的理解
求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;
}