程序員如何巧妙學習演算法技巧？
作者 | 帥地
責編 | 胡巍巍
今天和大家講講，在做演算法題時常用的一些技巧。對於平時沒用過這些技巧的人，或許你可以考慮試著去看看在實踐中能否用的上這些技巧來優化問題的解。
巧用數組下標
數組的下標是一個隱含的很有用的數組，特別是在統計一些數字，或者判斷一些整型數是否出現過的時候。
例如，給你一串字母，讓你判斷這些字母出現的次數時，我們就可以把這些字母作為下標，在遍歷的時候，如果字母a遍歷到，則arr[a]就可以加1了，即arr[a]++。
通過這種巧用下標的方法，我們不需要逐個字母去判斷。
我再舉個例子：
問題：給你n個無序的int整型數組arr，並且這些整數的取值範圍都在0-20之間，要你在 O(n) 的時間複雜度中把這n個數按照從小到大的順序列印出來。
對於這道題，如果你是先把這n個數先排序，再列印，是不可能O(n)的時間列印出來的。
但是數值範圍在0-20。我們就可以巧用數組下標了。把對應的數值作為數組下標，如果這個數出現過，則對應的數組加1。
代碼如下：
publicvoidf(intarr[]){
int[] temp =newint[21];
for(inti =; i
temp[arr[i]]++;
}
//順序列印
for(inti =; i
for(intj =; j
System.out.println(i);
}
}
}
利用數組下標的應用還有很多，大家以後在遇到某些題的時候可以考慮是否可以巧用數組下標來優化。
巧用取余
有時候我們在遍曆數組的時候，會進行越界判斷，如果下標差不多要越界了，我們就把它置為0重新遍歷。特別是在一些環形的數組中，例如用數組實現的隊列。往往會寫出這樣的代碼：
for(inti =; i
if(pos
//沒有越界
// 使用數組arr[pos]
else{
pos=;//置為再使用數組
//使用arr[pos]
}
pos++;
}
實際上我們可以通過取余的方法來簡化代碼。
for(inti =; i
//使用數組arr[pos] (我們假設剛開始的時候pos
pos= (pos+1) % N;
}
巧用雙指針
對於雙指針，在做關於單鏈表的題是特別有用，比如「判斷單鏈表是否有環」、「如何一次遍歷就找到鏈表中間位置節點」、「單鏈表中倒數第k個節點」等問題。
對於這種問題，我們就可以使用雙指針了，會方便很多。我順便說下這三個問題怎麼用雙指針解決吧。
例如對於第一個問題，我們就可以設置一個慢指針和一個快指針來遍歷這個鏈表。
慢指針一次移動一個節點，而快指針一次移動兩個節點，如果該鏈表沒有環，則快指針會先遍歷完這個表，如果有環，則快指針會在第二次遍歷時和慢指針相遇。
對於第二個問題，一樣是設置一個快指針和慢指針。慢的一次移動一個節點，而快的兩個。
在遍歷鏈表的時候，當快指針遍歷完成時，慢指針剛好達到中點。
對於第三個問題，設置兩個指針，其中一個指針先移動k個節點。之後兩個指針以相同速度移動。
當那個先移動的指針遍歷完成的時候，第二個指針正好處於倒數第k個節點。
你看，採用雙指針方便多了吧。所以以後在處理與鏈表相關的一些問題的時候，可以考慮雙指針哦。
巧用移位運算
有時候我們在進行除數或乘數運算的時候，例如n / 2，n / 4, n / 8這些運算的時候，我們就可以用移位的方法來運算了，這樣會快很多。
例如：
n / 2等價於n >> 1；
n / 4等價於n >> 2；
n / 8等價於n >> 3。
這樣通過移位的運算在執行速度上是會比較快的，也可以顯得你很厲害的樣子，哈哈。
還有一些&(與)、|(或)的運算，也可以加快運算的速度。例如判斷一個數是否是奇數，你可能會這樣做：
if(n % 2 == 1){
dosomething();
}
不過我們用與或運算的話會快很多。例如判斷是否是奇數，我們就可以把n和1相與了，如果結果為1，則是奇數，否則就不會。即：
if(n & 1 == 1){
dosomething();
)
具體的一些運算技巧，還得需要你們多在實踐中嘗試著去使用，這樣用久後就會比較熟練了。
設置哨兵位
在鏈表的相關問題中，我們經常會設置一個頭指針，而且這個頭指針是不存任何有效數據的，只是為了操作方便，這個頭指針我們就可以稱之為哨兵位了。
例如我們要刪除頭第一個節點是時候，如果沒有設置一個哨兵位，那麼在操作上，它會與刪除第二個節點的操作有所不同。
但是我們設置了哨兵，那麼刪除第一個節點和刪除第二個節點那麼在操作上就一樣了，不用做額外的判斷。當然，插入節點的時候也一樣。
有時候我們在操作數組的時候，也是可以設置一個哨兵的，把arr[0]作為哨兵。
例如，要判斷兩個相鄰的元素是否相等時，設置了哨兵就不怕越界等問題了，可以直接arr[i] == arr[i-1]?了。不用怕i = 0時出現越界。
當然我這只是舉一個例子，具體的應用還有很多，例如插入排序，環形鏈表等。
與遞歸有關的一些優化
對於可以遞歸的問題考慮狀態保存
當我們使用遞歸來解決一個問題的時候，容易產生重複去算同一個子問題，這個時候我們要考慮狀態保存以防止重複計算。例如我隨便舉一個之前舉過的問題
問題：一隻青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個n級的台階總共有多少種跳法？
這個問題用遞歸很好解決。假設f(n)表示n級台階的總跳數法，則有f(n) = f(n-1)+f(n - 2)。
遞歸的結束條件是當0
publicintf(intn){
if(n
returnn;
}else{
returnf(n -1) + f(n -2);
}
}
不過對於可以使用遞歸解決的問題，我們一定要考慮是否有很多重複計算。顯然對於f(n) = f(n-1) + f(n-2)的遞歸，是有很多重複計算的。如：
就有很多重複計算了。這個時候我們要考慮狀態保存。例如用hashMap來進行保存，當然用一個數組也是可以的，這個時候就像我們上面說的巧用數組下標了。
可以當arr[n] = 0時，表示n還沒計算過，當arr[n] != 0時，表示f(n)已經計算過，這時就可以把計算過的值直接返回回去了。因此我們考慮用狀態保存的做法代碼如下：
//數組的大小根據具體情況來，由於int數組元素的的默認值是0
//因此我們不用初始化
int[] arr =newint[1000];
publicintf(intn){
if(n
returnn;
}else{
if(arr[n] !=) {
returnarr[n];//已經計算過，直接返回
}else{
arr[n] = f(n-1) + f(n-2);
returnarr[n];
}
}
}
這樣，可以極大提高演算法的效率。也有人把這種狀態保存稱之為備忘錄法。
考慮自底向上
對於遞歸的問題，我們一般都是從上往下遞歸的，直到遞歸到最底，再一層一層著把值返回。
不過，有時候當n比較大的時候，例如當n = 10000時，那麼必須要往下遞歸10000層直到n
對於這種情況，其實我們是可以考慮自底向上的做法的。例如我知道：
f(1)=1；
f(2)=2。
那麼我們就可以推出f(3)= f(2)+f(1)=3。從而可以推出f(4),f(5)等直到f(n)。
因此，我們可以考慮使用自底向上的方法來做。
代碼如下：
publicintf(intn){
if(n
returnn;
intf1 =1;
intf2 =2;
intsum =;
for(inti =3; i
sum = f1 + f2;
f1 = f2;
f2 = sum;
}
returnsum;
}
我們也把這種自底向上的做法稱之為遞推。
總結一下
當你在使用遞歸解決問題的時候，要考慮以下兩個問題。
（1）是否有狀態重複計算的，可不可以使用備忘錄法來優化。
（2）是否可以採取遞推的方法來自底向上做，減少一味遞歸的開銷。
今天就先講到這裡，之後有時間再來多謝一些其他的。如果覺得不錯，不妨點個贊。
聲明：本文為作者個人投稿，版權歸其所有。
TAG:CSDN |