注意：本文適用于已刷過題目，想短短幾分鐘快速簡單回顧的情況洛巢。沒看過《劍指offer》的讀者建議先閱讀下括袒。
斐波那契數(shù)列
1、1稿茉、2锹锰、3类垦、5、8城须、13蚤认、21、34糕伐、……
在數(shù)學(xué)上砰琢，斐波納契數(shù)列以如下被以遞歸的方法定義：F(0)=1，F(xiàn)(1)=1, F(n)=F(n-1)+F(n-2)（n>=2良瞧，n∈N*）
解法比較：
- 遞歸
int F(int n)
{
if(n <= 0)
return 0;
else if(n == 1)
return 1;
else
return F(n-1) + F(n-2);
}
缺點：效率非常低陪汽，時間復(fù)雜度是指數(shù)級的。重復(fù)的計算量是無比巨大的褥蚯。
2.迭代法挚冤。
long Fib(int n)
{
int i;
unsigned long a = 0, b = 1, c;
if (n <= 1) {
return n;
} else {
for (i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
求Fibonacci數(shù)列第n項時雖然要用到前面兩項的值，但它們僅作為臨時計算的中間值赞庶，不作為結(jié)果輸出训挡，因此無保留的必要，完全可以轉(zhuǎn)化成迭代法求解
青蛙跳臺階
一次可跳1階或2階歧强，求n階跳法澜薄，變相斐波那契數(shù)列。
青蛙跳臺階變態(tài)版本
一只青蛙一次可以跳上1級臺階摊册，也可以跳上2級……它也可以跳上n級肤京。求該青蛙跳上一個n級的臺階總共有多少種跳法。
f(n)=2f(n-1)*
圖解：
效率更高的解法：
if(number<=0)
return 0;
if(number==1)
return 1;
int sum=1<<(number-1);//位運算代替*2 1<<n 意思為2的n次方
return sum;
矩形覆蓋
同青蛙跳臺階理
二進制中1的個數(shù)
int count = 0;
while(n!= 0){
count++;
n = n & (n - 1);
}
return count;
例：一個二進制數(shù)1100茅特，從右邊數(shù)起第三位是處于最右邊的一個1忘分。減去1后，第三位變成0白修，它后面的兩位0變成了1妒峦，而前面的1保持不變，因此得到的結(jié)果是1011.我們發(fā)現(xiàn)減1的結(jié)果是把最右邊的一個1開始的所有位都取反了熬荆。這個時候如果我們再把原來的整數(shù)和減去1之后的結(jié)果做與運算舟山，從原來整數(shù)最右邊一個1那一位開始所有位都會變成0。如1100&1011=1000.也就是說卤恳，把一個整數(shù)減去1累盗，再和原整數(shù)做與運算，會把該整數(shù)最右邊一個1變成0.那么一個整數(shù)的二進制有多少個1，就可以進行多少次這樣的操作。
數(shù)值的整數(shù)次方
給定一個double類型的浮點數(shù)base和int類型的整數(shù)exponent概漱。求base的exponent次方挺份。
考慮：
- 指數(shù)為0的情況
- 指數(shù)為負數(shù)->對指數(shù)求絕對值，算出次方結(jié)果后取倒數(shù)拭抬，倒數(shù)還要判斷底數(shù)為0的情況辈灼。
- 浮點數(shù)的比較是有誤差的甫匹，因此不能用簡單的a==0來比較傲须。一般的比較方式是蓝牲，相減的差在一個很小的區(qū)間內(nèi)，我們就認為是相等的
(float1- float2 > -0.0000001) && (float1 -float2 < 0.0000001)
最佳解決：
可用>>1代替/2
if(exponent==0)
return 1;
if(exponent==1)
return base;
if(exponent==-1)
return 1.0/base;
if((exponent&1)==1){
//奇數(shù)
double result=Power(base,(exponent-1)/2);
result*=result;
result*=base;
return result;
}else{
//偶數(shù)
double result=Power(base,exponent/2);
result*=result;
return result;
}
從尾到頭打印鏈表
采用棧臨時存儲遍歷的節(jié)點值泰讽，遍歷完后棧輸出例衍。
替換空格
將長度為1的空格替換為長度為3的“%20”，字符差的長度變長已卸。如果允許我們開辟一個新的數(shù)組來存放替換空格后的字符串佛玄，那么這道題目就非常簡單。但是如果面試官要求在原先的字符串上操作累澡，并且保證原字符串有足夠長的空間來存放替換后的字符串梦抢，那么我們就得另想方法。
如果從前往后替換字符串愧哟，那么保存在空格后面的字符串肯定會被覆蓋奥吩，那么我們就考慮從后往前進行替換。
首先遍歷原字符串翅雏，找出字符串的長度以及其中的空格數(shù)量圈驼，
根據(jù)原字符串的長度和空格的數(shù)量我們可以求出最后新字符串的長度。
設(shè)置兩個指針point1和point2分別指向原字符串和新字符串的末尾位置望几。
如果point1指向內(nèi)容不為空格，那么將內(nèi)容賦值給point2指向的位置萤厅，如果point1指向為空格橄抹，那么從point2開始賦值“02%”
直到point1==point2時表明字符串中的所有空格都已經(jīng)替換完畢。
二維數(shù)組中的查找
數(shù)組每一行都按照從左到右遞增的順序排序惕味，每一列都按照從上到下遞增的順序排序楼誓。
一張圖說明，查找7為例：
旋轉(zhuǎn)數(shù)組的最小數(shù)字
例：{3名挥，4疟羹，5，1禀倔，2}為{1榄融，2，3救湖，4愧杯，5}的旋轉(zhuǎn)數(shù)組，求最小數(shù)字鞋既。
可用二分查找法力九。
注意：存在該情況{1耍铜，2，3跌前，4棕兼，5}仍然是數(shù)組的選擇。
特殊情況：{1抵乓，0程储，1，1}（a[start]==a[end]==a[mid]）此時只能采用順序查找臂寝。
求鏈表中倒數(shù)第k個數(shù)
首先要先判斷k和鏈表的長度比較章鲤，如果k<=鏈表長度，
則先指針1走k步咆贬，指針2和指針1一起走败徊。指針1指向NULL的時候，指針2所指就是倒數(shù)第k個數(shù)掏缎。
從上往下打印二叉樹
采用隊列作為臨時存儲容器
二叉樹深度
int TreeDepth(TreeNode* pRoot)
{
if(pRoot==NULL)
return 0;
return max(TreeDepth(pRoot->left),TreeDepth(pRoot->right))+1;
}
連續(xù)子數(shù)組的和
例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個開始,到第3個為止)子向量的長度至少是1皱蹦。【動態(tài)規(guī)劃思想】
public int FindGreatestSumOfSubArray(int[] array) {
int sum=array[0];
int max=array[0];
for(int i=1;i<array.length;i++){
if(sum<=0){
sum=array[i];
}else
sum+=array[i];
if(max<sum)
max=sum;
}
return max;
}
兩個棧實現(xiàn)隊列
stack1只管push
stack2為空時把stack1內(nèi)容彈出眷蜈，一一入stack2棧沪哺，stack2棧頂為要pop的元素，若stack2不為空酌儒，直接出棧辜妓。
包含min函數(shù)的棧
例存儲為stack，采用棧minStack輔助存min忌怎，當(dāng)push進stack更小值時籍滴，minStack存入當(dāng)前push的值，若push的值比minStack棧頂值大榴啸，則minStack再次入棧棧頂?shù)闹的醵琛tack pop時，minStack比較大小鸥印，若小于pop的值勋功，minStack跟著pop。
數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
二分查找出頭和尾库说，尾下標-頭下標+1為出現(xiàn)次數(shù)狂鞋。
思路簡單，但是要注意越界的坑璃弄！
public int GetNumberOfK(int[] array, int k) {
int end = findEnd(array, 0, array.length-1, k);
int start = findStart(array, 0, array.length-1, k);
if (end == -1 || start == -1)
return 0;
return end-start+1;
}
public int findStart(int[] array, int start, int end, int k) {
if (start > end||end>=array.length||start<0)
return -1;
int mid = (start + end) / 2;
if (array[mid] == k) {
if (mid - 1 < 0)
return mid;
if (array[mid - 1] != k)
return mid;
else
return findStart(array, start, mid - 1, k);
} else if (array[mid] > k)
return findStart(array, start, mid - 1, k);
else
return findStart(array, mid + 1, end, k);
}
public int findEnd(int[] array, int start, int end, int k) {
if (start > end||end>=array.length||start<0)
return -1;
int mid = (start + end) / 2;
if (array[mid] == k) {
if (mid + 1 >= array.length)
return mid;
if (array[mid + 1] != k)
return mid;
else
return findEnd(array, mid + 1, end, k);
} else if (array[mid] > k)
return findEnd(array, start, mid - 1, k);
else
return findEnd(array, mid + 1, end, k);
}
數(shù)組中出現(xiàn)次數(shù)超一半的數(shù)字
沒什么好說的要销，出現(xiàn)次數(shù)超過一半，那么排序后該數(shù)字必然會在數(shù)組中位線處夏块。
另一種思路：符合條件的數(shù)字疏咐，則它出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)和還要多纤掸。在遍歷數(shù)組時保存兩個值：一是數(shù)組中一個數(shù)字，一是次數(shù)浑塞。遍歷下一個數(shù)字時借跪，若它與之前保存的數(shù)字相同，則次數(shù)加1酌壕，否則次數(shù)減1掏愁；若次數(shù)為0，則保存下一個數(shù)字卵牍，并將次數(shù)置為1果港。遍歷結(jié)束后，記得統(tǒng)計下數(shù)組糊昙，所保存的數(shù)字在數(shù)組中出現(xiàn)的次數(shù)是否超過數(shù)組的一半長度辛掠，不超過直接return 0，否則返回保存的數(shù)字释牺。
反轉(zhuǎn)鏈表
三個指針pPrev萝衩、p、pNext没咙、tmp猩谊，初始化時分別指向NULL、head祭刚、head->next牌捷、head->next->next。重復(fù)進行p->next=pPrev操作袁梗。再一一挪到下一個指向宜鸯。
if(pHead==NULL)
return NULL;
ListNode* pPrev=NULL;
ListNode* p=pHead;
ListNode* pNext=p->next;
while(p!=NULL)
{
ListNode* tmp;
if(pNext!=NULL)
tmp=pNext->next;
p->next=pPrev;
pPrev=p;
p=pNext;
pNext=tmp;
}
return pPrev;
合并兩個排序的鏈表
分別從link1和link2的頭部開始比較，誰小誰就作為新鏈表的next點遮怜。
需要注意的情況：
- 兩個鏈表都為NULL
- 有一個鏈表為NULL
- 兩個鏈表長度不一致
- 第一次比較時newLink表頭為NULL，賦值給頭鸿市，下一次比較賦值給newLink的next锯梁，且要有臨時變量存儲newLink的頭指針（最后返回臨時變量），因為在循環(huán)中不斷newLink=newLink->next后返回newLink焰情，此時newLink指向鏈表的中部而不是頭陌凳。
調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
- 不穩(wěn)定算法（不強調(diào)相對順序）：頭尾兩個指針，頭遇到偶數(shù)停止内舟，尾遇到奇數(shù)停止合敦，交換，一直到頭指針下標大于尾指針下標验游。
- 穩(wěn)定算法（調(diào)整完保證奇數(shù)和奇數(shù)充岛，偶數(shù)和偶數(shù)之間的相對位置不變）：
采用插入排序思想保檐。找到奇數(shù)時，往前0~奇數(shù)位置范圍新找偶數(shù)崔梗，交換位置夜只。
丑數(shù)
只包含因子2、3和5的數(shù)稱作丑數(shù)蒜魄，習(xí)慣上把1當(dāng)做是第一個丑數(shù)扔亥。
//1，2谈为，3旅挤，4，5伞鲫，6粘茄，8，9榔昔，10驹闰，12，15撒会，16嘹朗，18....
分析：
//用數(shù)組存儲計算出來的丑數(shù)，返回a[index-1]即可(數(shù)組從0開始)
（1）index=1诵肛，num=a[index-1]=a[0]=1
（2）index=2屹培，num=min（a[index-2]*2,a[index-2]*3,a[index-2]*5）;
//前一個數(shù)乘以3個因子的最小值 也就是1*2和1*3和1*5比較，min為2怔檩。
（3）index=3褪秀，num=min（a[index-3]*2,a[index-3]*3,a[index-3]*5,a[index-2]*2,a[index-2]*3,a[index-2]*5）;
//前2個數(shù)乘以3個因子的最小值。
也就是1*2和1*3和1*5和2*2和2*3和2*5比較薛训，min為2媒吗。
但是此時的丑數(shù)要大于前一個丑數(shù)！乙埃！闸英，所以取次小值3。
最好的辦法是循環(huán)計算得到 第一個 *2大于下一個目標數(shù)的丑數(shù)的下標
第一個 *3大于下一個目標數(shù)的丑數(shù)的下標
第一個 *5大于下一個目標數(shù)的丑數(shù)的下標
分別保存下來介袜，然后求這三個數(shù)的最小值甫何。
if (index <= 0)
return 0;
if (index == 1)
return 1;
int a[index];
a[0] = 1;
int index1 = 0, index2 = 0, index3 = 0;
for (int i = 1; i < index; i++) {
int min = getMin(a[index1] * 2, a[index2] * 3, a[index3] * 5);
a[i] = min;
while (a[index1] * 2 <= a[i])
index1++;
while (a[index2] * 3 <= a[i])
index2++;
while (a[index3] * 5 <= a[i])
index3++;
}
return a[index - 1];
第一次只出現(xiàn)一次的字符
java用哈希表，先掃描一遍遇伞，統(tǒng)計各個字符出現(xiàn)的次數(shù)辙喂。
再掃描第二遍，去哈希表取對應(yīng)的次數(shù)，一旦等于1巍耗，跳出循環(huán)秋麸，返回下標。
c用數(shù)組代替哈希表芍锦，總共只有256個字符竹勉，數(shù)組長度256即可。
二叉樹的鏡像
沒什么好說娄琉，上關(guān)鍵代碼次乓。
void Mirror(TreeNode* root)
{
if(root==NULL)
return ;
if(root!=NULL)
{
TreeNode* tmp=root->left;
root->left=root->right;
root->right=tmp;
if(root->left)
Mirror(root->left);
if(root->right)
Mirror(root->right);
}
}
棧的壓入彈出序列
輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序孽水，請判斷第二個序列是否為該棧的彈出順序票腰。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序女气，序列4杏慰，5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列炼鞠。（注意：這兩個序列的長度是相等的）
思路：
模擬堆棧操作：將原數(shù)列依次壓棧缘滥，棧頂元素與所給出棧隊列相比，如果相同則出棧谒主，接著比較出棧隊列下一位朝扼。如果不同則繼續(xù)壓棧，直到原數(shù)列中所有數(shù)字壓棧完畢霎肯。
檢測棧中是否為空擎颖，若空，說明出棧隊列可由原數(shù)列進行棧操作得到观游。否則搂捧，說明出棧隊列不能由原數(shù)列進行棧操作得到。
兩個鏈表的第一個公共結(jié)點
兩個單向鏈表存在公共點懂缕，類似“Y”
- 方法一：遍歷兩個鏈表允跑，存入棧。一一出棧搪柑，最后一個相同的結(jié)點吮蛹，即為第一個公共結(jié)點。
- 方法二：遍歷兩個鏈表拌屏，獲取長度，長的鏈表先走len1-len2步术荤，然后兩個鏈表一起遍歷倚喂，第一個相同的結(jié)點為第一個公共結(jié)點。
不用加減乘除做加法
寫一個函數(shù)，求兩個整數(shù)之和端圈，要求在函數(shù)體內(nèi)不得使用+焦读、-、*舱权、/四則運算符號矗晃。
int Add(int num1, int num2)
{
while(num2!=0)
{
int n=num1^num2;
num2=(num1&num2)<<1;
num1=n;
}
return num1;
}
根據(jù)先序和中序重建二叉樹
遞歸思想
假定已知二叉樹如下：
7
/ \
10 2
/ \ /
4 3 8
\ /
1 11
那么它的先序遍歷和中序遍歷的結(jié)果如下：
preorder = {7,10,4,3,1,2,8,11}
inorder = {4,10,3,1,7,11,8,2}
需要關(guān)注幾個重要的點：
1）先序遍歷的第一個結(jié)點總是根結(jié)點。先序遍歷時父結(jié)點總是在子結(jié)點前遍歷宴倍。
2）可以觀察到在中序遍歷中张症，7是第4個值（從0開始算起）。由于中序遍歷順序為：左子樹鸵贬，根結(jié)點俗他，右子樹。所以7左邊的{4,10,3,1} 這四個結(jié)點屬于左子樹阔逼，而根結(jié)點7右邊的{11,8,2}屬于右子樹兆衅。
3）可以從上面的結(jié)論得到遞歸式。在構(gòu)建了根結(jié)點7后嗜浮，我們可以根據(jù)中序遍歷{4, 10, 3, 1} 和{11,8,2}分別構(gòu)建它的左子樹和右子樹羡亩。我們同時需要相應(yīng)的先序遍歷結(jié)果用于發(fā)現(xiàn)規(guī)律。我們可以由先序遍歷知道左右子樹的先序遍歷分別是{10危融，4, 3, 1}和{2畏铆， 8， 11}专挪。左右子樹也分別為二叉樹及志，由此可以遞歸來解決問題。
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return build(pre,0,pre.length-1,in,0,in.length-1);
}
public TreeNode build(int [] pre,int prestart,int preend,int [] in,int instart,int inend) {
if(prestart>preend||instart>inend)
return null;
TreeNode root=new TreeNode(pre[prestart]);
for(int i=instart;i<=inend;i++){
if(in[i]==pre[prestart]){
root.left=build(pre,prestart+1,prestart+i-instart,in,instart,i-1);
root.right=build(pre,prestart+i-instart+1,preend,in,i+1,inend);
break;
}
}
return root;
}
二叉搜索樹的后序遍歷序列
判斷一個序列是否是二叉搜索樹的后序遍歷序列寨腔。二叉搜索樹的后序遍歷滿足以下條件速侈，例:{1,3,2,5,7,6,4}。最后一位4為根節(jié)點迫卢，{1,3,2}為左子樹倚搬，{5,7,6}為右子樹。再繼續(xù)遞歸乾蛤，2為根節(jié)點每界，1為左子樹，3為右子樹家卖。6為根節(jié)點眨层，5為左子樹，7為右子樹上荡。
public boolean VerifySquenceOfBST(int[] sequence) {
if (sequence.length <= 0)
return false;
return build(sequence, 0, sequence.length - 1);
}
public boolean build(int[] sequence, int start, int end) {
if (start > end || end < 0 || start >= sequence.length) {
return true;
}
int root = sequence[end];
int j = end - 1;
while (j >= start && sequence[j] > root) {
j--;//找到第一個小于根節(jié)點的下標
}
for (int i = start; i <= j; i++) {
if (sequence[i] > root)
return false;
//判斷左子樹序列是否都小于根節(jié)點趴樱，不小于則不滿足
}
//檢查左子樹和右子樹
return build(sequence, start, j) && build(sequence, j + 1, end - 1);
}
樹的子結(jié)構(gòu)
遞歸比較
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot1==NULL||pRoot2==NULL)
return false;
return find(pRoot1,pRoot2)||HasSubtree(pRoot1->left,pRoot2)||HasSubtree(pRoot1->right,pRoot2);
//用短路或代替flag
}
bool find(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot2==NULL)
return true;
if(pRoot1==NULL)
return false;
if(pRoot1->val==pRoot2->val)
return find(pRoot1->left, pRoot2->left)&&find(pRoot1->right, pRoot2->right);
return false;
}
順時針打印矩陣
如果覺得注意邊界情況太麻煩，可以采用魔方的逆時針旋轉(zhuǎn)的方法，一直做取出第一行的操作
例如
1 2 3
4 5 6
7 8 9
輸出并刪除第一行后叁征，再進行一次逆時針旋轉(zhuǎn)纳账，就變成：
6 9
5 8
4 7
繼續(xù)重復(fù)上述操作即可。
最小的k個數(shù)
快排后輸出前k個捺疼。
平衡二叉樹
空樹或它的左右兩個子樹的高度差的絕對值不超過1,且左右子樹都是平衡二叉樹疏虫。
bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot==NULL)
return true;
int height=getHeight(pRoot->left)-getHeight(pRoot->right);
if(height>1||height<-1)
return false;
return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);
}
int getHeight(TreeNode* pRoot){
if(pRoot==NULL)
return 0;
return max(getHeight(pRoot->left),getHeight(pRoot->right))+1;
}
本文持續(xù)更新中。啤呼。卧秘。。
