[数据结构与算法]下一个排列，字符串排列

一个整数的下一个排列

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

算法推导

以 1,2,3,4,5,6 为例，其排列依次为：
123456 123465 123546 … 654321
可以看到有这样的关系：123456 < 123465 < 123546 <… < 654321。

如何得到这样的排列顺序？这是本文的重点。我们可以这样来分析：

我们希望下一个数比当前数大，这样才满足“下一个排列”的定义。因此只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如123456，将 5 和 6 交换就能得到一个更大的数 123465。我们还希望下一个数增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，我们需要：在尽可能靠右的低位进行交换，需要从后向前查找 将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换 将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列。以 123465为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比123564 更小，123546 就是 123465 的下一个排列 以上就是求“下一个排列”的分析过程。

算法过程

标准的“下一个排列”算法可以描述为：

• 从后向前查找第一个相邻升序的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
  在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
• 将 A[i] 与 A[k] 交换
• 可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
• 如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4

    public static void main(String[] args) {
        int[] a = new int[]{1,2,3};
        Solution solution = new Solution();
        solution.nextPermutation(a);
//升序序列就是最小数，先从个位十位开始调换，每次调换都要反转是因为换了较大位之后，可以继续从个位到十位换  如1234  、 1432（要重排 1423 //反转后的才是最小的）
        int i = nums.length = 2;
        while(i >= 0 && nums[i] >= nums[i + 1]){   //找到不是12 543（降序的）然后使前面的最低位，和后面的和最低位相差最近/大的最少的/的数字（这样变化的最高位变化最小）
            i--;
        }
        if(i >= 0){  //防止越界
            int j = nums.length - 1;
            while(j >= 0 && nums[i] >= nums[j]){
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);         //i之后都是降序了（因为较高位i已经变了，所以要把后边的数字变成最小的全升序）
    }
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void reverse(int[] nums, int start){
        int left = start, right = nums.length - 1;
        while(left < right){
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

字符串排列

输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:

输入：s = “abc” 输出：[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]

方法一：当成数字，利用下一个排列

class Solution {
    public String[] permutation(String s) {
        List<String> ret = new ArrayList<String>();
        char[] arr = s.toCharArray();
        Arrays.sort(arr);            //把传进来的字符串排序
        do{
            ret.add(new String(arr));  //用list储存方便添加
        }while(nextPermutation(arr));
        int size  = ret.size();
        String[] retArr = new String[size];
        for(int i = 0 ; i < size; i++){
            retArr[i] = ret.get(i);
        }
        return retArr;
    }

    public boolean nextPermutation(char[] arr){
        int i = arr.length - 2;
        while(i >= 0 && arr[i] >= arr[i + 1]){
            i--;
        }
        if(i < 0){
            return false;
        }
        int j = arr.length - 1;
        while(j >= 0 && arr[j] <= arr[i]){
            j--;
        }
        swap(arr, i, j);
        reverse(arr, i + 1);
        return true;
    }

    public void swap(char[] arr, int i, int j){
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void reverse(char[] arr, int i){
        int left = i, right = arr.length - 1;
        while(left < right){
            swap(arr, left, right);
            left++;
            right--;
        }
    }
}

方法二： 回溯法

递归解析：

终止条件： 当 x = len? - 1 时，代表所有位已固定（最后一位只有 11 种情况），则将当前组合 c 转化为字符串并加入
res ，并返回； 递推参数： 当前固定位 x ； 递推工作： 初始化一个 Set ，用于排除重复的字符；将第 x 位字符与 i \in∈
[x, len?] 字符分别交换，并进入下层递归； 剪枝： 若 c[i] 在 Set? 中，代表其是重复字符，因此 “剪枝” ； 将
c[i] 加入 Set? ，以便之后遇到重复字符时剪枝； 固定字符： 将字符 c[i] 和 c[x] 交换，即固定 c[i] 为当前位字符；
开启下层递归： 调用 dfs(x + 1) ，即开始固定第 x + 1 个字符； 还原交换： 将字符 c[i] 和 c[x]
交换（还原之前的交换）；

class Solution {
    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s){
        c = s.toCharArray();
        dfs(0);                //从第0位开始固定
        return res.toArray(new String[res.size()]);
    }

    void dfs(int x){
        if(x == c.length - 1){
            res.add(String.valueOf(c));//所有位都填完了
            return;
        }
        HashSet<Character> set = new HashSet<>(); //每层一个set（记录该位置遍历过的数字）
        for(int i = x; i < c.length; i++){   //从第x位开始（因为x为之前的数字都被调换固定了）
            if(set.contains(c[i])){        //如果发生重复了（这个位置这个数字已经占过了），则跳过该点
                continue;
            }
            set.add(c[i]);
            swap(i, x);              //讲c【x】和c【i】换位置 （也就是为了下层略过c【i】）
            dfs( x + 1);            //固定第x + 1位字符
            swap(i, x);            //还原位置
        }
    }
    //将下标i，x的字符互换（即固定第x位）
    void swap(int a, int b){
        char temp = c[a];
        c[a] = c[b];
        c[b] = temp;
    }
}

toArray()

• 不带参数的toArray()方法，是构造的一个Object数组，然后进行数据copy，此时进行转型就会产生ClassCastException。

• 而带参数的toArray(T[] a) 方法，则是根据参数数组的类型，构造了一个对应类型的，长度跟ArrayList的size一致的空数组，虽然方法本身还是以 Object 数组的形式返回结果，不过由于构造数组使用的组件类型跟需要转型的组件类型一致，就不会产生转型异常。

正确方法：

String[] str_a = (String []) arr.toArray(new String[0]);
 String[] a = new String[size];
String [] str_a = (String []) arr.toArray(a);

Java valueOf() 方法

Java String类:
valueOf() 方法有以下几种不同形式：

1. valueOf(boolean b): 返回 boolean 参数的字符串表示形式。.
2. valueOf(char c): 返回 char 参数的字符串表示形式。
3. valueOf(char[] data): 返回 char 数组参数的字符串表示形式。
4. valueOf(char[] data, int offset, int count): 返回 char 数组参数的特定子数组的字符串表示形式。
5. valueOf(double d): 返回 double 参数的字符串表示形式。
6. valueOf(float f): 返回 float 参数的字符串表示形式。
7. valueOf(int i): 返回 int 参数的字符串表示形式。
8. valueOf(long l): 返回 long 参数的字符串表示形式。
9. valueOf(Object obj): 返回 Object 参数的字符串表示形式。

public class Test {
    public static void main(String args[]) {
        double d = 1100.00;
        boolean b = true;
        long l = 1234567890;
        char[] arr = {'r', 'u', 'n', 'o', 'o', 'b' };

        System.out.println("返回值 : " + String.valueOf(d) );
        System.out.println("返回值 : " + String.valueOf(b) );
        System.out.println("返回值 : " + String.valueOf(l) );
        System.out.println("返回值 : " + String.valueOf(arr) );
    }
}