演算法的魅力
A. 全世界最強的演算法平台codeforces究竟有什麼魅力
簡單介紹一下codeforces這個網站，codeforces位於宇宙編程最強的毛國。據說最早是由俄羅斯的一群大學生維護的，它最大的特點就是代碼和題解的公開。所有人都可以隨意查看其它大牛的代碼，可以說是非常具有開源精神了。
codeforces很大的特點就是題目兼容並蓄，什麼難度等級的題目都可以找到。並且題目很有意思，往往思維陷阱比較多，也就是思維題比較多。對於數據結構以及演算法的考察相對弱一些，更多的時候往往是告訴你用什麼演算法你也不知道怎麼做……
codeforces另外一個很大的特點就是它有自己的上分系統，基本上每周會舉辦一到兩次在線的演算法比賽。一般的比賽時長是兩個小時，只要注冊賬號就可以免費參加。我記得當年第一次參加比賽會獲得一個初始分是1500，然後根據你在比賽當中的表現上分或者減分。由於參加的選手水平實力強度不一，所以它開設了好幾個檔次(div)，不同層次的選手面對的題目難度也不一樣，這樣保證了大家都可以愉快地參賽。
codeforces在比賽的時候只會測試一小部分數據，真正的測試集會放到賽後進行測試。所以在比賽中測試通過的代碼，只是通過了小數據驗證，很有可能有隱藏的問題沒被發現。當你通過了這道題之後，你就可以去查看其他通過人的代碼，去分析它們有沒有問題，如果發現了bug，可以構造一份數據hack掉他的提交。hack成功之後，你會獲得分數的獎勵。
你可以雙擊打開其他人的提交記錄，去閱讀他們的代碼。到了比賽後期，能做的問題做的差不多了之後，就進入了緊張刺激的互相hack階段。講道理，這比只是單純做題的競賽要有趣多了。
以前我們acm集訓隊經常晚上一起打codeforces的比賽，有時候看到隊友在一個房間里，還會互相關注一下近況，互相hack一把，不得不說現在懷念起來還是非常有意思的。
好了，關於codeforces網站就介紹到這里了，如果你也對演算法感興趣的話，不妨試著用一下它吧，相信你也會找到演算法的樂趣。
B. 遞歸演算法有何特點
遞歸4—遞歸的弱點
之所以沒有把這段歸為演算法的討論，因為這里討論的不在是演算法，而只是討論一下濫用遞歸的不好的一面。
遞歸的用法似乎是很容易的，但是遞歸還是有她的致命弱點，那就是如果運用不恰當，濫用遞歸，程序的運行效率會非常的低，低到什麼程度，低到出乎你的想像！當然，平時的小程序是看不出什麼的，但是一旦在大項目里濫用遞歸，效率問題將引起程序的實用性的大大降低！
例子：求1到200的自然數的和。
第一種做法：
#include <stdio.h>
void main()
{
int i;
int sum=0;
for(i=1;i<=200;i++)
{
sum+=i;
}
printf("%d\n",sum);
}
該代碼中使用變數2個，計算200次。再看下個代碼：
#include <stdio.h>
int add(int i)
{
if(i==1)
{
return i;
}
else
{
return i+add(i-1);
}
}
void main()
{
int i;
int sum=0;
sum=add(200);
printf("%d\n",sum);
}
但看add（）函數，每次調用要聲明一個變數，每次調用要計算一次，所以應該是200個變數，200次計算，對比一下想想，如果程序要求遞歸次數非常多的時候，而且類似與這種情況，我們還能用遞歸去做嗎？這個時候寧願麻煩點去考慮其他辦法，也要嘗試擺脫遞歸的干擾。
21:21 | 添加評論 | 固定鏈接 | 引用通告 (0) | 記錄它 | 計算機與 Internet
程序演算法5—遞歸3—遞歸的再次挖掘
遞歸的魅力就在於遞歸的代碼，寫出來實在是太簡練了，而且能解決很多看起來似乎有規律但是又不是一下子能表達清楚的一些問題。思路清晰了，遞歸一寫出來問題立即就解決了，給人一重感覺，遞歸這么好用。我們在此再更深的挖掘一下遞歸的用法。
之前再強調一點，也許有人會問，你前邊的例子用遞歸似乎是更麻煩了。是，是麻煩了，因為為了方便理解，只能舉一些容易理解的例子，一般等實際應用遞歸的時候，遠遠不是這種狀態。
好了我們現在看一個數字的序列；有一組數的集合{1，2，4，7，11，16，22，29，37，46，56……}我故意多給幾項，一般是只給前4項讓你找規律的。序列給了，要求是求前50項的和。規律？有？還是沒有？一看就象有，但是又看不出來，我多給了幾項，應該很快看出來了，哦，原來每相鄰的兩項的差是個自然數排列，2-1=1，4-2=2，7-4=3，11-7=4，16-11=5……
好了，把規律找出來了，一開始可能覺得沒頭緒，沒問題，卜派咱們把這個序列存放到一個數組總可以吧！那我們就聲明一個數組，存放前50個逗輪數據，一個一個相加總可以了。於是有了下邊的寫法：
#include <stdio.h>
void main()
{
int i,a[50],sum=0;
a[0]=1;
for(i=1;i<50;i++)
{
a[i]=a[i-1]+i;
}
for(i=0;i<50;i++)
{
sum+=a[i];
}
printf("%d\n",sum);
}
好了，代碼運行一下，結果出來了，正確不正確呢？自己測試吧，把50項改成1、2、3、4、5……項，試試前多少項是不是正確，雖然這不是正確的測試方法，但是的確是常用的測試方法。
等到這個代碼已經完全理解了，完全明白了正個計算過程，我們就型指賀應該對這段代碼進行改寫優化了，畢竟這個代碼還是不值得用一個數組的，那麼我們嘗試著只用變數去做一下：
#include <stdio.h>
void main()
{
int i;
int number=1;
int sum=0;
for(i=0;i<50;i++)
{
number+=i;
sum+=number;
}
printf("%d\n",sum);
}
不知道我這樣寫是不是跨度大了點，但是我不準備詳細解釋了，很多東西需要你去認真分析的，所以很多東西如果不懂，自己想清楚比別人解釋的效果會更好，因為別人講只能讓你理解，如果你自己去想，你就在理解的同時學會了思考。
這個代碼寫出來，不要繼續看下去，先自己嘗試著把這個題目用遞歸做一下看看自己能不能寫出來，當然，遞歸並不是那麼輕松就能使用的，有時候也是需要去細心設計的。如果做出來了，對比一下下邊的代碼，如果沒有寫出來，建議認真分析後邊的代碼，然後最好是能完全掌握，能自己隨時把這行代碼寫出來：
#include <stdio.h>
int add(int n,int num,int i)
{
num+=i;
if(i>=n-1)
{
return num;
}
else
{
return num+add(n,num,i+1);
}
}
void main()
{
int sum;
sum=add(50,1,0); /*50表示前50象項*/
printf("%d\n",sum);
}
當然這個代碼中的n只是一個參考變數，如果把if(i>=n-1)中的n該成50，那麼就不需要這個n了，函數兩個參數就可以了，這樣寫是為了修改方便。
20:28 | 添加評論 | 固定鏈接 | 引用通告 (0) | 記錄它 | 計算機與 Internet
程序演算法4—遞歸2—遞歸的魅力
兩天沒有再寫下去，因為畢竟有時候會有點心情問題，有時候覺得心情不好，一下子什麼東西都想不起來了，很多時候寫一些東西是需要狀態的，一旦狀態有了，想的東西才能順利的寫出來，雖然有些東西寫出來在別人看來很垃圾，但是起碼自己覺得還是相當滿意的，我寫這個本來就沒有多少技術含量，只是想給初學程序的人一些指引，加快他們對程序的領悟！
好了，言歸正傳，繼續上次遞歸的討論，看看遞歸的魅力所在。
有這樣一個問題，說一個猴子和一堆蘋果，猴子一天吃一半，然後再吃一個，10天後剩下一個了，也就是說吃了10次，剩下1個了。問原來一共有多少蘋果。
當然我們的目的不是求出蘋果的數量，而是尋求一種解決問題的方法，這個問題一出來，通常對程序掌握深度不一樣的朋友對這個題會有不同的認識，首先介紹一種解決方法，這種人腦袋還是比較聰明的，思路非常的明確，也有可能語言工具掌握的也不錯，代碼寫出來非常准確，先看一下代碼再做評價吧：
#include <stdio.h>
void main()
{
int day=10;
int apple;
int i,j;
for(i=1;;i++)
{
apple=i;
for(j=0;j<day;j++)
{
if(apple%2==0&&apple>0)
{
apple/=2;
apple--;
}
else
{
break;
}
}
if(j==day&&apple==1)
{
printf("%d\n",i);
return;
}
}
}
程序的大概思路很明確，簡單介紹一下，這種寫法就是從一個蘋果開始算起，for(i=1;;i++)的作用就是改變蘋果的數量，如果1個符合條件，那就試試2個，然後3個、4個一直到適合為止，里邊的for循環就是把每一次取得的蘋果的數目進行計算，如果每次都能順利的被2整除（也就是說每次都能保證猴子能正好吃一半），然後再減一一直到最後，如果最後蘋果剩下是一個而且天數正好是10天，那麼就輸出一下蘋果的數目，整個程序退出，如果看不明白的沒關系，這個寫法非常的不適用，我們叫寫出這種演算法的人傻X，雖然這種人腦袋也挺聰明，能寫出一些新鮮的寫法，但是又臟又臭，代碼既不簡練又不高效。
所以說，有時候有些人以為自己學的很好了，自己所做的一切都是最好的，這種想法是不正確的，也許有些初學者沒有什麼經驗寫出來的代碼卻更讓人容易明白點，那麼也是先看看代碼：
#include <stdio.h>
void main()
{
int day[11];
int i;
day[0]=1;
for(i=1;i<11;i++)
{
day[i]=(day[i-1]+1)*2;
}
printf("%d\n",day[10]);
}
代碼不長，而且也恰當的應用了題目中的規律，不是說要吃一半然後再吃一個嗎？那我用數組來存放每天蘋果的數量，用day[0]表示最後一天的蘋果數量，那就是剩下的一個，然後就是找規律了，什麼規律？就是如果猴子不多吃一個的話，那就是正好吃了一半，也就是說猴子當天吃了之後剩餘的蘋果的數目加1個然後再乘以2就是前一天的數目了，這樣一想這個題目就簡單的多了，於是這個題用數組就輕松的做出來了。
那麼這個代碼究竟是不是已經很好了呢，我們注意到，這里邊每個數組元素只用了一次並沒有被重復使用，再這種情況下我們是不是可以用一種方法代替數組呢？於是就有了更優化的寫法，這個寫法似乎已經是相當簡練了：
#include <stdio.h>
void main()
{
int apple=1;
int i;
for(i=0;i<10;i++)
{
apple=(apple+1)*2;
}
printf("%d\n",apple);
}
代碼寫到這里已經把問題完全抽象化了，所以我們就應該站在數學的角度去分析了。也許我們就應該結束了討論，但是偏偏這個時候，又來了遞歸，悄悄的通過美麗的調用顯示了一下她的魅力：
#include <stdio.h>
int apple(int i)
{
if(i==0)
{
return 1;
}
else
{
return (apple(i-1)+1)*2;
}
}
void main()
{
int i;
i=apple(10);
printf("%d\n",i);
}
原理都還是一樣的，但是寫出來的格式已經完全變掉了，沒有了for循環。假想一個復雜的問題遠比這個問題復雜，而且沒有固定循環次數，那麼我們再使用循環雖然也能解決問題，但是可能面臨循環難以設計、控制等問題，這個時候用遞歸可能就會讓問題變的非常的清晰。
另外說一點，一般我這里的代碼，並不是從最差到最好的，基本排列是從最差到最合適的代碼（當然是本人認為最合適的，也許還有更好的，本人能力所限了），然後最後給出一種比較違反常規的代碼，一般是不贊成用最後一種代碼的，當然有時候最後一種代碼也許是最好的選擇，看情況吧！
20:25 | 添加評論 | 固定鏈接 | 引用通告 (0) | 記錄它 | 計算機與 Internet
10月15日
程序演算法3—遞歸1—遞歸小顯威力
現在用C語言實現一個字元串的倒序輸出，當然，方法也是很多的，但是如果程序中能有相對優化的方法或者簡單明了易讀的方法，那對你自己或者別人都是一種幸福。
第一種寫法，這類寫法既浪費內存又不實用，一般是剛學程序的才這樣做，程序的結構很簡單，利用的是數組：
#include <stdio.h>
void main()
{
char c[2000];
int i,length=0;
for(i=0;i<2000;i++)
{
scanf("%c",&c[i]);
if(c[i]=='\n')
{
break;
}
else
{
length++;
}
}
for(i=length;i>0;i--)
{
printf("%c",c[i-1]);
}
printf("\n");
}
這段代碼中的數組，聲明大了浪費內存空間，聲明小了又怕不夠，所以寫這種代碼的人一般寫完之後會祈禱，祈禱測試的人不要輸入的太多，太多就不能完全顯示了！
與其這么提心吊膽，於是又有人想出了第二種方法，終於解決了一些問題，而且完全實現了程序的實際要求，於是，這種人經過一番苦想，覺得問題終於可以解決了，這種方法看起來是一種很不錯的方法。
#include <stdio.h>
#include <malloc.h>
void main()
{
int i;
char *c;
c=(char *)malloc(1*sizeof(char));
for(i=0;;i++)
{
*(c+i)=getchar();
if(*(c+i)=='\n')
{
*(c+i)='\0';
break;
}
else
c=(char *)realloc(c,(i+2)*sizeof(char));
}
for(--i;i>=0;i--)
{
putchar(*(c+i));
}
printf("\n");
free(c);
}
怎麼樣？不錯，准確的應用內存，幾乎沒有浪費什麼空間，這種方法也體現了一下指針的強大功能，寫這個程序雖然不敢說這個人已經掌握了指針的應用，但是起碼可以說他已經會用指針了。代碼寫出來，看起來已經有點美感。
但是也有一些人還是比較喜歡動腦筋的，經過一番思考，終於想出了第三種比較容易寫的方法，也許有寫初學者可能覺得有些難度，但是事實上這個東西一點都不難，如果稍微有點程序功底之後再看這段代碼，應該是相當輕松！
#include <stdio.h>
void run()
{
char c;
c=getchar();
if(c!='\n')
{
run();
}
else
{
return;
}
putchar(c);
}
void main()
{
run();
printf("\n");
}
寫出的代碼讓人眼前一亮，哇！原來遞歸功能簡單而又好用，那我們為什麼不好好利用呢？但是遞歸也不一定就是最好的選擇，因為有時候雖然遞歸用起來很方便，但是效率卻不高，以後的討論中還會詳細說明。
C. C++關於製作游戲，演算法對游戲真的有用嘛！~~o(>_<)o ~~
13歲肯好好學的話前途無量啊。
你學那些東西 是學語言最基本的，
做游戲至少少需要懂的東西如下
1 精通一門語言
2 常用數據結構和演算法 （數組 鏈表 樹 圖 隊列 堆棧 對這些數據結構的 增刪改查排序）
1 和2 是任何開發里都會要用到的東西
3 圖形圖像的常用演算法 （包括這些演算法的基礎 線性代數 和 解析幾何 特別是3D游戲，不會這個就和沒手沒腳一樣）
4 網路通信（如果想做網路游戲的話）
5 一套可用作游戲開發的開發庫（比如 OPENGL DIRECTX 或者一些游戲引擎 HGE IRRLICHT 之類的）
除了基礎必須要自己學意外，其他的工具庫網上有很多
編程這東西不是教出來的，都是自學出來的。
比如遞歸， 對樹的數據結構的操作就全是遞歸的，當然為了提高效率還需要把遞歸改成非遞歸的
你現在的情況，就老老實實先把語言學會。C++ 沒你想得那麼簡單。
另外沒有做游戲的簡易教程，如果你只是想做著玩，體驗一下的，可以用游戲工廠之類的軟體或者魔獸爭霸的編輯器。
如果你覺得自己C++語言已經學得差不多了，下面附一段求常量階乘的代碼,用的是遞歸，
接觸到這樣的代碼後，我開始使用模板元編程的，這段程序最大的好處是運算時間為0
template<int N>
struct fact
{
enum
{
value = N * fact<N-1>
};
};
template<>
struct fact<1>
{
enum
{
value = 1
};
};
template<>
struct fact<0>
{
enum
{
value = 0
};
};
std::cout << (fact<5>::value) << std::endl //求5的階乘
所以不管你做什麼基礎是很重要的，
建議的學習流程 C++ ->數據結構-> STL -> WINDOWS 或者 LINUX 的基礎圖形編程->boost::asio（網路） boost::gil（圖像）
->directX 或者 OPENGL， 以及線性代數和解析幾何 ->游戲引擎使用
當然以你的情況來說，最好先把大學計算機系的課程全都學一遍
包括
數據結構 （所有開發相關）
高等數學 （所有開發相關）
離散數學（所有開發相關）
線性代數（游戲開發相關）
解析幾何（游戲開發相關）
操作系統原理 （至少要了解）
資料庫概論（網路游戲相關）
編譯原理 （游戲開發相關，本來是編譯器如何開發的，但是很多演算法游戲開發里用的到）
計算機組成原理（至少要了解）
計算機體系結構（至少要了解）
計算機網路通信（網路游戲開發相關）
計算機圖形學（游戲開發相關）
多媒體處理（游戲開發相關）
軟體工程（所有開發相關，至少要先做到了解）
最後建議你測下IQ 如果低於120的話建議轉行吧
D. 最近打算看演算法導論,在如何看方面有什麼好的建議
演算法導論，不適合入門，建議有數據結構和高等數學基礎再讀
這書上面有些內容太難了，剛開始不適合全看，挑些自己能看懂的來學。
很適合演算法初學者體會演算法的魅力.這本書講解的很全面.演算法都用偽碼實現.對編程語言要求不高.書的前幾章是一些數學和概率基礎和演算法分析的一些說明.後面幾章是一些演算法的描述.對NP問題感興趣的話.可以看看這本書的VII部分中的NP-Completeness.我覺得這本書比較好的一部分是它的附錄部分.對前面的一些背景知識公式進行了詳細的闡述和證明以及一些專有名詞進行了索引方便檢索.這本書在國內目前只有英文版的.但南大有個中文版的(不過他們太無恥了居然說是他們自己編著)我看了那個版本的.其實是第一版的中文翻譯叫<現代計算機常用數據結構和演算法>.其他的我想我不需要多說了.有興趣的可以去體會一下,
E. 為什麼抖音能推送剛好需要的
抖音的演算法是極具魅力的。這個魅力在於，抖音的流量分配是去中心化的。
抖音的演算法是中心化的，會根據用戶的喜好推送視頻內容，讓平台流量更加公平。
這套演算法是抖音必不可少的評判機制，對平台的所有用戶都有效，無論是內容生產者（拍視頻的人）還是內容消費者（看視頻的人）。抖音會根據演算法給每一個作品的人分配一個流量池。之後，抖音根據你在這個流量池裡的表現，決定是把你的作品推送給更多人，還是就此打住。
F. 程序員需要怎樣的數學基礎
LZ不要杞人憂天了，那些說數學重要的，首先數學你會嗎？數學包含的范疇太多了，常見的有高等幾何 微積分 線性代數 概率論 離散數學 數論 圖論等等你指的是具體哪一樣呢？就算是前人科學巨匠泰鬥牛頓，毆幾里德，愛因斯坦，他也只是擅長自己從事的那領域，要說所有數學領域都精通我想他們也不敢吹這樣的牛逼。
所以對大多數人來說，在數學方面都不太可能取得什麼很深的造詣。等到你所謂的把數學學好，那鬍子都快白完了，數學是又深奧又費解學習成本巨大需要耗費大量時間學完不用立馬就忘的學科。所以說數學重要，先問問你自己能不能學會。
其次，計算機學科跟數學根本就不是一門學科， 包含內容極其有限。計算機編程有自己的理論知識體系，很多跟數學關系不大。學好編程尤其對新手來說最重要的是對你學的編程語言的熟練運用和工具SDK的爛熟於心。每個語言都有自己獨特的設計理念，不存在什麼好學的編程語言。
所以說，題主， 你想得太遠了。軟體開發需要用到的知識比數學重要的太多了。拋開計算機不說，英語比起數學的重要性就大的多的多。英語不好你看不懂函數API說明你一切就是白瞎。而數學對於大多數人來說是最難學也是最不重要的知識，基本上是學了就忘忘了就扔扔了也沒感覺的那種，很多搞編程的可能一輩子也用不到數學知識。為什麼？理解C++的指針和多態需要數學嗎？一個復雜的系統架構也不需要半點數學知識，而你就是看不懂。
還有就是程序調試技術，很多IDE給出的出錯語句非常費解，什麼指針為空，數組越界，內存溢出，SDK找不到， 你沒經驗時打死你也看不懂你的編程工具提示的是什麼。這時你那高大上的數學真是P用沒有，它能幫你排查錯誤找出程序崩掉的原因嗎？我看不行吧，你還是得到論壇網路去問人家這些基本的問題。
在你擔心數學好不好之前，你更應該關心編程環境怎麼搭建，連IDE都搞不定不知道程序怎麼跑起來你還搞什麼呀，下一步就是程序基本的語法和SDK庫函數的掌握，基本SDK都不知道什麼意思怎麼去用，如字元串函數，文件讀寫和資料庫常用操作，這些你都不會你還有學下去的必要嗎？還有更重要的更基本的程序調試技術，程序老出錯老崩潰怎麼辦呀，哪裡變數為空了內存寫錯了？為什麼程序老編不過去呀，誰能幫幫我呀!!!這個時候你發現那牛逼的數學知識真是屁用沒有，你還是感嘆自己基本功底不行經驗太少，這個時候打死你也不會再關心數學好不好的問題了。
如果說用到數學的大概只有3D游戲引擎，很智能的人工智慧，如格鬥游戲的電腦應對玩家的復雜AI，生化危機中僵屍怪物的配合商量運用策略包抄玩家和記憶功能，還有航空航天領域這樣高精尖技術學科才會用到復雜一點的數學知識。而這些都是計算機專家才要掌握的內容。所以題主你是想多了，還是先關心下自己程序為什麼編不過老是報錯的問題吧
G. 散列演算法可以做哪些事
查找並判斷狀態是否出現過，出現過幾次
比如說一個物品a有四個特徵,為a[1],a[2],a[3],a[4]
那麼令f(a)=a[1]*(p^1)+a[2]*(p^2)+a[3]*(p^3)+a[4]*(p^4)
hash[f(a)]=a;
若又有一個物品b，特徵b[1],b[2],b[3],b[4]
f(b)=b[1]*(p^1)+b[2]*(p^2)+b[3]*(p^3)+b[4]*(p^4)
那麼a=b時，f(a)=f(b)
反過來f(a)=f(b)時，a很有可能等於b （只要p設定的足夠大，a不等於b的幾率也很小）
為了節省內存，我們可以讓f(a)=f(a)%q;
這樣hash數組只需要開q的大小
就算在mod了之後a不等於b的概率也是非常小的（所以出題人一般不怎麼能卡Hash，反而還天天考Hash）
像這樣一個題：
有n個圖，每個圖都有m個點，有一些帶權的邊，詢問每個圖中的u點能否都不經過權值小於w的邊到達v點（n*m<=200000，邊數<=300000）
首先，你可以dfs，O（n*m）可以過，
但是如果改成q<=200000次詢問，你就不能dfs了
實際上對於一個詢問，當權值大於等於w的邊全部放完之後就轉化為判斷此時uv是否都聯通，
所以我們考慮離線，將詢問按w從大到小，邊也是按權值從大到小，邊放邊，邊判斷聯通，
動態判斷聯通可以用並查集的按大小啟發式合並，id[i][k]表示在第i個圖中k所在並查集的頭，
i圖中u，v聯通等價於id[i][u]==id[i][v](表示第i個圖，需要枚舉n次)。所以可以枚舉i判斷是不是都聯通，總復雜度=O（邊數 * log2(n*m) +邊數 * n）log2（n*m）為啟發式合並的時間復雜度。最後一個n為枚舉i的耗費，如果n>500這方法就炸了，想辦法優化，這時候就可以用哈希。
設f(u)=id[1][u]*(p^1)+id[2][u]*(p^2)+...+id[n][u]*(p^n) % q
如果id[i][u]=id[i][v](i=1~n) 則f(u)==f(v)
如果f(u)==f(v)則很大可能 id[i][u]=id[i][v](i=1~n)
令Hash[u]=f(u)
則在每次修改id[i][u]時順便O(1)修改Hash(u)即可O（1）查詢,判斷Hash[u]是否等於Hash[v].
這樣時間復雜度優化為O(邊數*log2(n*m)+邊數)是一個非常優秀的演算法，散列的魅力就在於此，空間換時間，效率高，比賽時只要p和q設的大一些，一些考演算法的題可以水個八九十分，還特別好寫，不會寫炸。
H. React diff演算法
react 作為一款最主流的前端框架之一，在設計的時候除了簡化操作之外，最注重的地方就是節省性能了。diff演算法就是為 節省攔蠢戚性能 而設計的，diff演算法和虛擬DOM的完美結合是react最有魅力的地方。其中，diff 是 different 的簡寫，這樣一來，diff 演算法是什麼也就顧名思義了——找不同。
在DOM需要更新的時候，通過diff演算法可以 計算出 虛擬DOM 中真正變化的部分，從而只針對變化的部分進行更新渲染，避免」牽一發而動全身「，造成性能浪費。
雖然完美地實現了找不同的功能，但是傻瓜式的 循環遞歸對節點進行依次的對比 ，使其演算法的時間復雜度為 O(n^3) ，其中n是dom樹的節點數。如果dom數足夠大的話，這個演算法將對cpu形成絕殺。
為了優化diff演算法，react中對普通的diff演算法實行了三大策略，成功將時間復雜度降為 O(n)
tree diff 是diff演算法的基礎策略，它的重點在於 同層比較 。
出於對diff演算法的優化，react的tree diff對DOM節點的跨層級移動的操作忽略不計，react對Virtual DOM樹進行層級控制，也就是說 只對相同層級的DOM節點進行比較 （即同一個父節點下的所有子節點）。對比時，一旦發現節點不存在，則直接刪除掉該節點以及之下的所有子節點。這樣秩序對DOM樹進行依次遍歷，就可以完成整個樹的對比。時間復雜度為O(n)
一個疑問：既然tree diff忽略了跨層級移動的操作，如果這種情況出現了，diff演算法會怎麼處理呢？
答：不管，多了就新增，少了就刪簡陵除（ 只有創建節點和刪除節點的操作 ）。所以官方明確建議不要進行DOM節點的跨層級操作。
component diff是組件間的對比
在遇到組件之間的比較時，有三種策略
優化點：
element diff 是針對同一層級的element節點的
在雙方同一層級的節點對比時，有三種情況
子節點更新時，會出現以下幾種情況：
react中的key值，它不是給開發者使用的。在一般情況下key值是當我們在做子元素遍歷的時候需要使用的。因為我們如果要進行數據的更新，就需要進行虛擬dom的對比，而key值就是每個元素節點對應的唯一值。這個時候就需要對比子元素的key值是否有匹配項，如果有的情況下則會進行數據的更新；如果key值沒有匹配項，那麼這個節點就需要進行刪除和重新創建。
因此我們在遍歷的時候千萬不要用檔如 index下標 或者 時間戳、隨機數 等進行key值的賦值。這樣會造成元素的移除重新創建浪費性能。
I. 《數據結構與演算法分析C語言描述》真的適合初學者嗎
數據結構課程一般都是在大學大一第二學期進行開設，從基礎上來說至少需要兩項
計算機基礎知識（學會正常使用電腦）
一門計算機語言（這本書是C語言的，所以應該學會C語言）
整體來說是適合初學者學習的，但是這個初學者的空間想像能力和邏輯思維能力不能太弱。因此最好要有一定的數學基礎，例如有一定的高數和線性數學基礎，能夠理解一般的圖形，矩陣，階乘等數學概念。
J. 程序員需要怎樣的數學基礎
離散數學對程序員來說非常重要，還有組合數學、線性代數、概率論、數論等等，即使你將來不做研究，這些基礎知識也能極大地提高你的水平。計算機科學對離散數學的要求很高，建議你先學習前面提到的這些課程，然後學習計算機演算法和數據結構，再配合到網上的在線題庫做題，過程很艱辛，但是對你的幫助會很大。
推薦書目：
《具體數學》（先學完前面的數學課程，罩衫在水平有一定進步以後再看）
《演算法導論》（應該人手一本的好書）
簡單來說，學數學的目的，一方面是活躍你的思維；另一方面是為了深入學習演算法打基礎，設畢老想物數腔一下，同樣的問題，普通人的程序要幾十分鍾甚至幾小時幾天才能解決出來，甚至根本無法解決，而你精心設計的程序卻能在1秒內解決出來，這就是數學的魅力、演算法的魅力。
其實，一切取決於你是否想做一個高級程序員。如果你做體力活（其實一般編程別人都認為是體力活），那你可以不學，因為你用不到，但是，你要是做技術上的創新，做個很強的程序員，沒有數學的支持，很難。
你既然學習了C，c++,你也知道演算法的重要性，同樣一個問題，我用13行程序解決了，我的同學居然用了33行，因為他不懂的用數學。你要達到什麼高等，取決於你的數學修養。當然，要做一個普通的程序員就不用學習了。要挑戰自己，做個好的，優秀的，學習數學吧！