前言

作為一個大一大二還沒有感覺當(dāng)時學(xué)的數(shù)據(jù)結(jié)構(gòu)以及操作系統(tǒng)多重要的人，在大三想找暑期實習(xí)的時候，總算是感覺到了緊迫，趁著這學(xué)期還有一門算法課，特地將所有的題目以及思路盡量的記錄下來（貌似有些多，但都是基礎(chǔ)而且喜歡考的東西奧）。本篇是遞歸開始，說實話一開始我接觸也是花了一些時間去理解，做得多了才能感受到其實遞歸算是比較簡單的了。記住，當(dāng)需要重復(fù)做一件事情的時候，調(diào)用同一個方法去執(zhí)行，這時候可以考慮使用遞歸。

遞歸（解決字母排序重復(fù)問題）

例題一：

題目描述

有n個字母，列出由該字母組成的字符串的全排列（相同的排列只計一次）。

輸入

第一行輸入是字母個數(shù)n，1<=n<=20。接下來一行輸入的是待排列的n個字母。

輸出

按字母升序順序輸出所有排列（每個排列占一行）

樣例輸入

4
acac

樣例輸出

aacc
acac
acca
caac
caca
ccaa

先來講講這題的思路。首先可以確保升序輸出，就是對該數(shù)組進行排序。
而后我的思路是將每一個值，都放到第一個位置一次，這里就需要一個循環(huán)去執(zhí)行。然后你會發(fā)現(xiàn)其實第二數(shù)也跟我前面的想法一樣，讓后面的值都來到第二個位置一次，這樣重復(fù)的思路，就可以用遞歸去實現(xiàn)這題。

之后怎么去避免重復(fù)的問題呢？其實一開始我是有想過將所有的結(jié)果都存到HashMap中，然后再對結(jié)果進行查重。但是這樣的時間和空間的代價就大了。那么有沒有可能我們在執(zhí)行這個遞歸的時候就排除掉重復(fù)的可能呢？

我們看一下這些值，其實會發(fā)現(xiàn)，當(dāng)一列中一個值出現(xiàn)重復(fù)的時候，你只用確保這個值在第一個位置只出現(xiàn)一次，如果下次循環(huán)發(fā)現(xiàn)該值已經(jīng)到過第一個位置，就不執(zhí)行。第二個位置的想法也是一樣的，如果確定這個值已經(jīng)到過第二個位置，則不再執(zhí)行，以此類推。

可能我的表述還是不夠清楚，也行代碼可能很好的解決我們溝通的問題，嘿嘿。

大膽的做法（想法）

import java.util.Arrays;

public class Test{
    char[] A;//這里用字符串?dāng)?shù)組也是可以的，下面我會演示我一個不成熟的版本
    public Test(){
        A = "acac".toCharArray();
        Permute(0);
    }
    private void Permute(int index){ //這個index是當(dāng)前交換位置的下標(biāo)
        if(index>=A.length){ //臨界條件，這里每一個符合條件的數(shù)直接輸出
            System.out.println(String.valueOf(A));
            return; //這個不要漏了，漏了會gg的
        }
        
        char last='$'; //創(chuàng)建一個臨時值，記錄上一次的值。
        for(int i=index;i<A.length;i++)
        {
            Arrays.sort(A,index,A.length); //每一次執(zhí)行這個循環(huán)就排序以此，這樣確保是升序輸出的。
            if(A[i]==last) continue;//如果與上一次的值相同，則不執(zhí)行
            char temp = A[index];A[index]=A[i];A[i]=temp;
            last = A[index];//能夠這樣記錄，得益于上面的排序，如果有重復(fù)的值，則在排序之后必然會緊隨在上一個值之后。
            Permute(index+1);//注意不能使用index++之類的存在賦值的語句，我同學(xué)就不小心出現(xiàn)這樣的錯誤了（滑稽）。
        }
    }
    public static void main(String[] args){
        new Test();
    }
}

以上算是我聽到比較成熟的方法，而且時間跟空間上都算比較好的，下面我要貼的就是我一開始的不成熟想法，畢竟有對比，才會有傷害（我的算法是真的辣雞）。

我相對的并不是拿上一次的數(shù)直接與現(xiàn)在的值比較，因為我是在錄入該數(shù)組之后馬上執(zhí)行且執(zhí)行一次排序，并且我在遞歸的時候向下一層傳遞了一個全新的數(shù)組，如果不這么做，按照我的方法，該層循環(huán)的數(shù)組，會被下一層循環(huán)打亂，我是將兩個數(shù)交換后沒有再換回來（在這里也就是排序）。這樣的壞處是我使用的空間就會一直擴大。

再比較去重，我也是采用額外的方法，加了一個循環(huán)去判斷，這樣就會增加運算的時間，甚至?xí)\行超時，這取決于你使用的OJ平臺測試數(shù)據(jù)。

不成熟的做法（建議）

import java.util.Arrays;
import java.util.Scanner;

public class MyTest{
    
    int number;
    String temp = null;
    
    public MyTest(){
        Scanner sc = new Scanner(System.in);
        number = sc.nextInt();
        String charStr = sc.next();
        String[] charStrs = new String[number];
        for(int i=0;i<number;i++)charStrs[i] = charStr.charAt(i)+"";
        Arrays.sort(charStrs);
        CharArray(0,charStrs);
    }
    
    public void CharArray(int index,String[] charStrs){
        if(index==number-1){//這里依然是判斷條件不變
            for(int k=0;k<number;k++)
                System.out.print(charStrs[k]);
            System.out.println();
            return;
        }
        
        for(int i=index;i<number;i++){
            if(isSweap(charStrs,index,i)){ //在進行交互之前我就需要判斷該值是否有重復(fù)的
                temp = charStrs[index];
                charStrs[index] = charStrs[i];
                charStrs[i] = temp;
                
                CharArray(index+1,charStrs.clone());//使用深復(fù)制創(chuàng)建新的數(shù)組到下一層，糟糕的地方，但是勉強做了出來。
            }
        }
    }
    
    public boolean isSweap(String[] charStrs,int index,int i){
        if(index==i)return true; //這里要除去第一個數(shù)
        for(int k=index;k<i;k++)
            if(charStrs[i].equals(charStrs[k]))return false;
        return true;
    }
    
    public static void main(String[] args){
        new MyTest();
    }
}

結(jié)語

咳咳，對于你大膽的想法，我有一個不成熟的建議。
開玩笑。上面就是一個簡單的例題演示，如有什么意見/建議，歡迎提出來。芥末是前端方向的，不過這些基礎(chǔ)的東西，自己還是要懂得。這些文章更多的是在做自己的筆記同時分享出去，希望能幫到一些同學(xué)。
GitHub：https://github.com/Eugenehyj
另有篇關(guān)于RN的一些新手心得（待更新）
——“小白”的前端之路