前言

作为一个大一大二还没有感觉当时学的数据结构以及操作系统多重要的人，在大三想找暑期实习的时候，总算是感觉到了紧迫，趁着这学期还有一门算法课，特地将所有的题目以及思路尽量的记录下来（貌似有些多，但都是基础而且喜欢考的东西奥）。本篇是递归开始，说实话一开始我接触也是花了一些时间去理解，做得多了才能感受到其实递归算是比较简单的了。记住，当需要重复做一件事情的时候，调用同一个方法去执行，这时候可以考虑使用递归。

递归（解决字母排序重复问题）

例题一：

题目描述

有n个字母，列出由该字母组成的字符串的全排列（相同的排列只计一次）。

输入

第一行输入是字母个数n，1<=n<=20。接下来一行输入的是待排列的n个字母。

输出

按字母升序顺序输出所有排列（每个排列占一行）

样例输入

4
acac

样例输出

aacc
acac
acca
caac
caca
ccaa

先来讲讲这题的思路。首先可以确保升序输出，就是对该数组进行排序。
而后我的思路是将每一个值，都放到第一个位置一次，这里就需要一个循环去执行。然后你会发现其实第二数也跟我前面的想法一样，让后面的值都来到第二个位置一次，这样重复的思路，就可以用递归去实现这题。

之后怎么去避免重复的问题呢？其实一开始我是有想过将所有的结果都存到HashMap中，然后再对结果进行查重。但是这样的时间和空间的代价就大了。那么有没有可能我们在执行这个递归的时候就排除掉重复的可能呢？

我们看一下这些值，其实会发现，当一列中一个值出现重复的时候，你只用确保这个值在第一个位置只出现一次，如果下次循环发现该值已经到过第一个位置，就不执行。第二个位置的想法也是一样的，如果确定这个值已经到过第二个位置，则不再执行，以此类推。

可能我的表述还是不够清楚，也行代码可能很好的解决我们沟通的问题，嘿嘿。

大胆的做法（想法）

import java.util.Arrays;

public class Test{
    char[] A;//这里用字符串数组也是可以的，下面我会演示我一个不成熟的版本
    public Test(){
        A = "acac".toCharArray();
        Permute(0);
    }
    private void Permute(int index){ //这个index是当前交换位置的下标
        if(index>=A.length){ //临界条件，这里每一个符合条件的数直接输出
            System.out.println(String.valueOf(A));
            return; //这个不要漏了，漏了会gg的
        }
        
        char last='$'; //创建一个临时值，记录上一次的值。
        for(int i=index;i<A.length;i++)
        {
            Arrays.sort(A,index,A.length); //每一次执行这个循环就排序以此，这样确保是升序输出的。
            if(A[i]==last) continue;//如果与上一次的值相同，则不执行
            char temp = A[index];A[index]=A[i];A[i]=temp;
            last = A[index];//能够这样记录，得益于上面的排序，如果有重复的值，则在排序之后必然会紧随在上一个值之后。
            Permute(index+1);//注意不能使用index++之类的存在赋值的语句，我同学就不小心出现这样的错误了（滑稽）。
        }
    }
    public static void main(String[] args){
        new Test();
    }
}

以上算是我听到比较成熟的方法，而且时间跟空间上都算比较好的，下面我要贴的就是我一开始的不成熟想法，毕竟有对比，才会有伤害（我的算法是真的辣鸡）。

我相对的并不是拿上一次的数直接与现在的值比较，因为我是在录入该数组之后马上执行且执行一次排序，并且我在递归的时候向下一层传递了一个全新的数组，如果不这么做，按照我的方法，该层循环的数组，会被下一层循环打乱，我是将两个数交换后没有再换回来（在这里也就是排序）。这样的坏处是我使用的空间就会一直扩大。

再比较去重，我也是采用额外的方法，加了一个循环去判断，这样就会增加运算的时间，甚至会运行超时，这取决于你使用的OJ平台测试数据。

不成熟的做法（建议）

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)){ //在进行交互之前我就需要判断该值是否有重复的
                temp = charStrs[index];
                charStrs[index] = charStrs[i];
                charStrs[i] = temp;
                
                CharArray(index+1,charStrs.clone());//使用深复制创建新的数组到下一层，糟糕的地方，但是勉强做了出来。
            }
        }
    }
    
    public boolean isSweap(String[] charStrs,int index,int i){
        if(index==i)return true; //这里要除去第一个数
        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();
    }
}

结语

咳咳，对于你大胆的想法，我有一个不成熟的建议。
开玩笑。上面就是一个简单的例题演示，如有什么意见/建议，欢迎提出来。芥末是前端方向的，不过这些基础的东西，自己还是要懂得。这些文章更多的是在做自己的笔记同时分享出去，希望能帮到一些同学。
GitHub：https://github.com/Eugenehyj
另有篇关于RN的一些新手心得（待更新）
——“小白”的前端之路