Skip to content

Instantly share code, notes, and snippets.

@yovnchine
Last active December 19, 2015 22:38
Show Gist options
  • Save yovnchine/6028450 to your computer and use it in GitHub Desktop.
Save yovnchine/6028450 to your computer and use it in GitHub Desktop.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Test {
public Test() {
// TODO Auto-generated constructor stub
}
static class StrPair implements Comparable<StrPair>{
public StrPair(String str, int idx) {
super();
this.str = str;
this.idx = idx;
}
String str;
int idx;
@Override
public int compareTo(StrPair o) {
int ret= str.compareTo(o.str);
if(ret==0){
return o.idx-idx;
}else{
return ret;
}
}
}
/*
* 输入数据格式:
* N
* n1 n2 n3 n4
* 第一行是表示多少个不一样的数字,第二行为具体的数字,空格隔开
*
*/
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
String line=null;
int N=0;
line=scanner.nextLine();
N=Integer.valueOf(line);
List<String> numbers=new ArrayList<String>();
for(int i=0;i<N;i++){
line=scanner.next();
numbers.add(line.trim());
}
//先排序,字典倒叙,首字母最大的在前面
Collections.sort(numbers,Collections.reverseOrder());
StringBuilder ret=new StringBuilder();
while(!numbers.isEmpty()){
int nn=numbers.size();
char c=numbers.get(0).charAt(0);
int end=nn;
for(int i=1;i<nn;i++){
//找到第一个首字母不是最大的位置,确定接下来要处理的范围
if(numbers.get(i).charAt(0)!=c){
end=i;
break;
}
}
if(end==1){
//如果首字母最大的数字只有一个,那么就用它了
ret.append(numbers.remove(0));
}else{
int i=0;
//最大数字的字符数
int maxLen=numbers.get(0).length();
List<StrPair> pairs=new ArrayList<StrPair>();
if(maxLen==1){
throw new IllegalStateException("inpout data error ,has some duplicate entry");
}
//最大字符剩余串参与排序,因为首字母都是一样的,就比较剩余字符
pairs.add(new StrPair(numbers.get(0).substring(1),0));
for(i=1;i<end;i++){
StringBuilder tmp=new StringBuilder(numbers.get(i).substring(1));
int slen=tmp.length();
//如果某个剩余数字的长度小于第一个,那么就给它添加上最大首字母,因为,挑了某个后,剩下来的数必然由这些首字母一样的数字构造出来。
if((slen+1)<maxLen){
tmp.append(numbers.get(0).charAt(0));
}
//加入待排序集合
pairs.add(new StrPair(tmp.toString(),i));
}
Collections.sort(pairs,Collections.reverseOrder());
// 取第一个,最大的,对应的原始位置
ret.append(numbers.remove(pairs.get(0).idx));
}
}
System.out.println("result is :"+ret.toString());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment