今天和大家講講，在做算法題時常用的一些技巧。對于平時沒用過這些技巧的人，或許你可以考慮試著去看看在實踐中能否用的上這些技巧來優(yōu)化問題的解，相信一定會讓你有所收獲，不然你看我。

數(shù)組的下標是一個隱含的很有用的數(shù)組，特別是在統(tǒng)計一些數(shù)字，或者判斷一些整型數(shù)是否出現(xiàn)過的時候。例如，給你一串字母，讓你判斷這些字母出現(xiàn)的次數(shù)時，我們就可以把這些字母作為下標，在遍歷的時候，如果字母a遍歷到，則arr[a]就可以加1了，即 arr[a]++;

通過這種巧用下標的方法，我們不需要逐個字母去判斷。

我再舉個例子：

問題：給你n個無序的int整型數(shù)組arr，并且這些整數(shù)的取值范圍都在0-20之間，要你在 O(n) 的時間復(fù)雜度中把這 n 個數(shù)按照從小到大的順序打印出來。

對于這道題，如果你是先把這 n 個數(shù)先排序，再打印，是不可能O(n)的時間打印出來的。但是數(shù)值范圍在 0-20。我們就可以巧用數(shù)組下標了。把對應(yīng)的數(shù)值作為數(shù)組下標，如果這個數(shù)出現(xiàn)過，則對應(yīng)的數(shù)組加1。 代碼如下：

public void f(int arr[]) {
 
       int[] temp = new int[21];
       for (int i = 0; i < arr.length; i++) {
           temp[arr[i]]++;
       }
       //順序打印
       for (int i = 0; i < 21; i++) {
           for (int j = 0; j < temp[i]; j++) {
               System.out.println(i);
           }
       }
   }

利用數(shù)組下標的應(yīng)用還有很多，大家以后在遇到某些題的時候可以考慮是否可以巧用數(shù)組下標來優(yōu)化。

有時候我們在遍歷數(shù)組的時候，會進行越界判斷，如果下標差不多要越界了，我們就把它置為0重新遍歷。特別是在一些環(huán)形的數(shù)組中，例如用數(shù)組實現(xiàn)的隊列。往往會寫出這樣的代碼：

for (int i = 0; i < N; i++) {
       if (pos < N) {
        //沒有越界
        // 使用數(shù)組arr[pos]
        else {
          pos = 0;//置為0再使用數(shù)組
          //使用arr[pos]
         }
        pos++;
   }

實際上我們可以通過取余的方法來簡化代碼

for (int i = 0; i < N; i++) {
  //使用數(shù)組arr[pos]   (我們假設(shè)剛開始的時候pos < N)
  pos = (pos + 1) % N;
}

對于雙指針，在做關(guān)于單鏈表的題是特別有用，比如“判斷單鏈表是否有環(huán)”、“如何一次遍歷就找到鏈表中間位置節(jié)點”、“單鏈表中倒數(shù)第 k 個節(jié)點”等問題。對于這種問題，我們就可以使用雙指針了，會方便很多。我順便說下這三個問題怎么用雙指針解決吧。

例如對于第一個問題

我們就可以設(shè)置一個慢指針和一個快指針來遍歷這個鏈表。慢指針一次移動一個節(jié)點，而快指針一次移動兩個節(jié)點，如果該鏈表沒有環(huán)，則快指針會先遍歷完這個表，如果有環(huán)，則快指針會在第二次遍歷時和慢指針相遇。

對于第二個問題

一樣是設(shè)置一個快指針和慢指針。慢的一次移動一個節(jié)點，而快的兩個。在遍歷鏈表的時候，當(dāng)快指針遍歷完成時，慢指針剛好達到中點。

對于第三個問題

設(shè)置兩個指針，其中一個指針先移動k個節(jié)點。之后兩個指針以相同速度移動。當(dāng)那個先移動的指針遍歷完成的時候，第二個指針正好處于倒數(shù)第k個節(jié)點。

你看，采用雙指針方便多了吧。所以以后在處理與鏈表相關(guān)的一些問題的時候，可以考慮雙指針哦。

有時候我們在進行除數(shù)或乘數(shù)運算的時候，例如n / 2，n / 4, n / 8這些運算的時候，我們就可以用移位的方法來運算了，這樣會快很多。

例如:

n / 2 等價于 n >> 1

n / 4 等價于 n >> 2

n / 8 等價于 n >> 3。

這樣通過移位的運算在執(zhí)行速度上是會比較快的，也可以顯的你很厲害的樣子，哈哈。

還有一些 &(與)、|(或)的運算，也可以加快運算的速度。例如判斷一個數(shù)是否是奇數(shù)，你可能會這樣做

if(n % 2 == 1){
 dosomething();
}

不過我們用與或運算的話會快很多。例如判斷是否是奇數(shù)，我們就可以把n和1相與了，如果結(jié)果為1，則是奇數(shù)，否則就不會。即

if(n & 1 == 1){
 dosomething();
)

具體的一些運算技巧，還得需要你們多在實踐中嘗試著去使用，這樣用久后就會比較熟練了。

在鏈表的相關(guān)問題中，我們經(jīng)常會設(shè)置一個頭指針，而且這個頭指針是不存任何有效數(shù)據(jù)的，只是為了操作方便，這個頭指針我們就可以稱之為哨兵位了。

例如我們要刪除頭第一個節(jié)點是時候，如果沒有設(shè)置一個哨兵位，那么在操作上，它會與刪除第二個節(jié)點的操作有所不同。但是我們設(shè)置了哨兵，那么刪除第一個節(jié)點和刪除第二個節(jié)點那么在操作上就一樣了，不用做額外的判斷。當(dāng)然，插入節(jié)點的時候也一樣。

有時候我們在操作數(shù)組的時候，也是可以設(shè)置一個哨兵的，把arr[0]作為哨兵。例如，要判斷兩個相鄰的元素是否相等時，設(shè)置了哨兵就不怕越界等問題了，可以直接arr[i] == arr[i-1]");

當(dāng)然我這只是舉一個例子，具體的應(yīng)用還有很多，例如插入排序，環(huán)形鏈表等。

（1）.對于可以遞歸的問題考慮狀態(tài)保存

當(dāng)我們使用遞歸來解決一個問題的時候，容易產(chǎn)生重復(fù)去算同一個子問題，這個時候我們要考慮狀態(tài)保存以防止重復(fù)計算。例如我隨便舉一個之前舉過的問題

問題：一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法？

這個問題用遞歸很好解決。假設(shè) f(n) 表示n級臺階的總跳數(shù)法，則有

f(n) = f(n-1) + f(n - 2)。

遞歸的結(jié)束條件是當(dāng)0 <= n <= 2時, f(n) = n。因此我們可以很容易寫出遞歸的代碼

    public int f(int n) {
       if (n <= 2) {
           return n;
       } else {
           return f(n - 1) + f(n - 2);
       }
   }

不過對于可以使用遞歸解決的問題，我們一定要考慮是否有很多重復(fù)計算。顯然對于 f(n) = f(n-1) + f(n-2) 的遞歸，是有很多重復(fù)計算的。如

就有很多重復(fù)計算了。這個時候我們要考慮狀態(tài)保存。例如用hashMap來進行保存，當(dāng)然用一個數(shù)組也是可以的，這個時候就像我們上面說的巧用數(shù)組下標了?？梢援?dāng)arr[n] = 0時，表示n還沒計算過，當(dāng)arr[n] != 0時，表示f(n)已經(jīng)計算過，這時就可以把計算過的值直接返回回去了。因此我們考慮用狀態(tài)保存的做法代碼如下：

//數(shù)組的大小根據(jù)具體情況來，由于int數(shù)組元素的的默認值是0
   //因此我們不用初始化
   int[] arr = new int[1000];
   public int f(int n) {
       if (n <= 2) {
           return n;
       } else {
           if (arr[n] != 0) {
               return arr[n];//已經(jīng)計算過，直接返回
           } else {
               arr[n] = f(n-1) + f(n-2);
               return arr[n];
           }
       }
   }

這樣，可以極大著提高算法的效率。也有人把這種狀態(tài)保存稱之為備忘錄法。

(2).考慮自底向上

對于遞歸的問題，我們一般都是從上往下遞歸的，直到遞歸到最底，再一層一層著把值返回。

不過，有時候當(dāng)n比較大的時候，例如當(dāng) n = 10000時，那么必須要往下遞歸10000層直到 n <=2 才將結(jié)果慢慢返回，如果n太大的話，可能棧空間會不夠用。

對于這種情況，其實我們是可以考慮自底向上的做法的。例如我知道

f(1) = 1;

f(2) = 2;

那么我們就可以推出 f(3) = f(2) + f(1) = 3。從而可以推出f(4),f(5)等直到f(n)。因此，我們可以考慮使用自底向上的方法來做。

代碼如下：

public int f(int n) {
       if(n <= 2)
           return n;

       int f1 = 1;
       int f2 = 2;
       int sum = 0;

       for (int i = 3; i <= n; i++) {
           sum = f1 + f2;
           f1 = f2;
           f2 = sum;
       }
       return sum;
   }

我們也把這種自底向上的做法稱之為遞推。

總結(jié)一下

當(dāng)你在使用遞歸解決問題的時候，要考慮以下兩個問題

(1). 是否有狀態(tài)重復(fù)計算的，可不可以使用備忘錄法來優(yōu)化。

(2). 是否可以采取遞推的方法來自底向上做，減少一味遞歸的開銷。

如果你覺得這篇內(nèi)容對你挺有啟發(fā)，那么你可以：

1、點贊，讓更多的人也能看到這篇內(nèi)容（收藏不點贊，都是耍流氓 -_-）

2、*關(guān)注我，讓我們成為長期關(guān)系。

3、關(guān)注公眾號「苦逼的碼農(nóng)」，里面已有100多篇原創(chuàng)文章，我也分享了很多視頻、書籍的資源，以及開發(fā)工具，歡迎各位的關(guān)注，第一時間閱讀我的文章。