一、 旋轉(zhuǎn)數(shù)組（數(shù)組開始有序），尋找最小數(shù)。（比如0,1,2,3,4,5,6可以旋轉(zhuǎn)為4,5,6,0,1,2,3等）。
旋轉(zhuǎn)數(shù)組特性：
- 部分有序，即變成兩個(gè)局部有序（但又特例）。
- 前面的有序子數(shù)組中的數(shù)總是大于等于后面有序子數(shù)組中的數(shù)（也有特例）。
- 特例是當(dāng)旋轉(zhuǎn)為0或者剛好為數(shù)組長(zhǎng)度的整數(shù)倍時(shí)，數(shù)組變回最開始的數(shù)組，即有序而非局部有序，還有一個(gè)特例是大部分元素都相等。
突破點(diǎn)：
- 因?yàn)槭怯行虻模ūM管是局部有序），我們還是可以利用這個(gè)有序的特性通過二分查找來解決問題。
- 傳統(tǒng)的二分查找是通過兩個(gè)下標(biāo)指針來指示我們要查找元素的的范圍，并且不停折半縮小范圍，縮小范圍的同時(shí)讓我們所查找的元素位置夾在兩個(gè)下標(biāo)之間；而這題也是類似，只是縮小范圍的時(shí)候，判斷方法有所不同弄，即上面的特性2，中間元素如果大于等于前面元素，則說明最小值在中間元素和以后，如果中間元素小于等于后面的元素，則說明最小值在中間值以前（包括中間值）。
- 特例處理，如果旋轉(zhuǎn)為數(shù)組的整數(shù)倍長(zhǎng)度時(shí)直接返回第0個(gè)袁術(shù)，如果大部分元素都相等時(shí)，使得中間值a[left]和a[right]以及a[mid]均相等，則采用順序查找。
二、 斐波那契數(shù)列
常見題目：
-
寫一個(gè)函數(shù)，輸入n，求斐波那契數(shù)列的第n項(xiàng)。
f(0) = 0; f(1) = 1; f(n) = f(n-1) + f(n-2); 一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階。求改青蛙跳上一個(gè)n級(jí)臺(tái)階總共有多少種跳法。
我們可以用2 X 1 的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問8個(gè)2 X 1的小矩形無重復(fù)的覆蓋一個(gè)2 X 8 的大矩形，總共有多少種方法？
這些題目都很類似，數(shù)列的第n項(xiàng)我們把它當(dāng)做第n種狀態(tài)，改變當(dāng)前狀態(tài)的方式（改變后為不同于當(dāng)前狀態(tài)的兩種不同狀態(tài)）通常有兩種。所以當(dāng)前狀態(tài)是由前面兩種不同狀態(tài)的結(jié)果的和。
三、 位運(yùn)算
一個(gè)整數(shù)n（大于0）減去1，在二進(jìn)制的表示中的特點(diǎn)，因?yàn)槎M(jìn)制的表示中，一個(gè)位不是0就是1，如果是1，則減1后變?yōu)?，運(yùn)算就此結(jié)束，而如果該位是0，則該位向前借1即該位變?yōu)?再減去1變?yōu)?，因?yàn)楦呶槐唤?其實(shí)也就相當(dāng)于減1，在該位的運(yùn)算與前面類似，直到遇到1，運(yùn)算才結(jié)束。
仔細(xì)看運(yùn)算過程發(fā)現(xiàn)，有如下特點(diǎn)：
- 運(yùn)算會(huì)在遇到最右邊的第一個(gè)1結(jié)束。
- 運(yùn)算使得包括最右邊第一個(gè)1右邊的所有位都變得和原來相反，結(jié)合第1特性，運(yùn)算后的二進(jìn)制表示變?yōu)閤xxx01111(原來為xxxx10000)。
- 如果與原來的整數(shù)做與位運(yùn)算，則獲得效果是將最右邊的1變?yōu)?.
四、 快速冪的理解
求x的n次方
快速冪的思路就是把n分解為若干2的冪之和，然后從低次冪開始求，由于高次冪可以直接由低次冪求得，因此可以非常高效得求得。
例如求 x 的 10次冪，10可以分解為8 + 2（二進(jìn)制表示為1000,10）
x的10次冪等于x的8次冪乘以x的2次冪，x的2次冪等于x * x, x的8次冪則等于4個(gè)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;
}