段位:4
说明:
输入一个字符串,然后将穷举下非重复排序序列字符串,返回一个list。
输入案例:
// 它弄了个类来输入一个string,然后后面那个就列出所有非重复排序序列。Permutations.singlePermutations("a") `shouldBe` ["a"]Permutations.singlePermutations("ab") `shouldBe` ["ab", "ba"]Permutations.singlePermutations("aabb") `shouldBe` ["aabb","abab","abba","baab","baba","bbaa"] 我的代码:抄了别人思路,利用递归的分治方法(递归学完之后几个处理方法全忘了,就像二分那几个模板),然后递归中循环。
数学方面这个就是一个阶乘的概念,有多少种组合方法,然后我处理出来之后,拿个hashset去重就行(对,我叫他hash去重)
class Permutations { // 利用builder做数组拼接 private static StringBuilder builder = new StringBuilder(); // 寄存输入string长度 private static int len = -1; public static List<String> singlePermutations(String s) { // 判下空 List<String> res = new ArrayList<String>(); if(s == null || s.length() == 0) return res; // 进行递归循环处理,hashset去重(我去面试说"hash去重"面试官就会打我) len = s.length(); HashSet<String> set = new HashSet<String>(); recurtion(s, new boolean[s.length()], builder, set); res = new ArrayList<String>(set); return res; } public static void recurtion(String s, boolean[] used, StringBuilder builder, HashSet<String> res) { // 判断是否拼接完成,不然进入循环 if(builder.length() == s.length()) { res.add(builder.toString()); return; } // 进行循环拼接,并且子序列递归 for(int i = 0;i < len;i++) { if(!used[i]) { used[i] = true; builder.append(s.charAt(i)); recurtion(s, used, builder, res); // 下一个子序列处理,需要把stringbuilder末位减去 if(builder.length() != 0) builder.deleteCharAt(builder.length() - 1); used[i] = false; } } }}