Java编程

java字符串排序牛客网,牛客网java错题知识点总结

题目描述输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 输入描述: 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

这里尤其需要注意2点:1.所有组合不能重复,比如输入”aa”,  那么输出的结果应当是“aa” ; 2. 输出结果按字典序排序

如果用《剑指offer》上的方法,显然这两点都不能满足,比如输入”abc”,输出结果为:”abc” “acb” “bac” “bca”  “cba” “cab” ,如果输入”aa”,输出解过为”aa” “aa” 。显然,这两种结果都是有问题的。

下面是《剑指offer》版本的代码:

1 import java.util.ArrayList;2 import java.util.List;3 public class Solution {4 private List list = new ArrayList<>();5 private StringBuffer buffer;6 public ArrayList Permutation(String str) {7 if(str==null

str.length()==0) return (ArrayList) list;8 buffer = new StringBuffer(str);9 PermutationCore(0);10 return (ArrayList) list;11 }12 public void PermutationCore(int begin) {13 if(begin==buffer.length()-1){14 list.add(buffer.toString());15 }16 for(int i = begin;i

TreeSet这个数据结构本身采用红黑树实现,能够自动将字符串按照字典序排序,同时因为其实现了Set接口,所以又能同时保证所有的结果是一个集合。而学过离散数学的朋友都知道,集合中的元素是不会重复的,所以如果我们采用TreeSet对排列的结果进行存储,那么就能轻易的达到上述要求。下面是本人实现的代码:

1 import java.util.ArrayList;2 import java.util.Iterator;3 import java.util.List;4 import java.util.Set;5 import java.util.TreeSet;6 public class Solution {7 private List list = new ArrayList<>();8 private Set set = new TreeSet<>();9 private StringBuffer buffer;10 public ArrayList Permutation(String str) {11 if(str==null

str.length()==0) return (ArrayList) list;12 buffer = new StringBuffer(str);13 PermutationCore(0);14 Iterator iterator = set.iterator();15 while(iterator.hasNext()){16 list.add(iterator.next());17 }18 return (ArrayList) list;19 }20 public void PermutationCore(int begin) {21 if(begin==buffer.length()-1){22 set.add(buffer.toString());23 }24 for(int i = begin;i

最后我们来看一看TreeSet的层次结构:

类似的结构还有ArrayList,LinkedList,HashSet,HashMap,TreeMap,PriorityQueue,Stack。另外重要的接口有:List,Set,Map,Queue,Deque,Comparator,Comparable,Itrerator。这些都是在编写数据结构和算法的时候经常用到的,尤其需要留意。《剑指offer》面试题28:字符串排序(牛客网版本) java

Similar Posts

发表评论

邮箱地址不会被公开。 必填项已用*标注