2016年百度之星资格赛Problem D Java版

Problem D Accepts: 2042 Submissions: 5880

度熊所居住的 D 国，是一个完全尊重人权的国度。以至于这个国家的所有人命名自己的名字都非常奇怪。一个人的名字由若干个字符组成，同样的，这些字符的全排列的结果中的每一个字符串，也都是这个人的名字。例如，如果一个人名字是 ACM，那么 AMC， CAM， MAC， MCA， 等也都是这个人的名字。在这个国家中，没有两个名字相同的人。

度熊想统计这个国家的人口数量，请帮助度熊设计一个程序，用来统计每一个人在之前被统计过多少次。

Input
这里包括一组测试数据，第一行包含一个正整数NN，接下来的NN 行代表了 NN 个名字。NN 不会超过100,000100,000，他们的名字不会超过40位.

Output
对于每输入的一个人名，输出一个整数，代表这个人之前被统计了多少次。

Sample Input
5
ACM
MAC
BBA
ACM
BAB
Sample Output
Copy
0
1
0
2


思想：先获取每个名字的排列组合，每个排列，放到map中，有重复的value++。

public static void main(String[] args) throws Exception {
		File file = new File("C:/D.txt");
		getFiles(file);
	}
	//数据这里放在文件中
	public static void getFiles(File file) throws Exception{
		InputStream in = new FileInputStream(file);
		InputStreamReader fr = new InputStreamReader(in,"gb2312");
		BufferedReader buff = new BufferedReader(fr);
		String line = buff.readLine();
		Map<String,Integer> map = new HashMap<String,Integer>();
		while(line!=null){
			char[] ss = line.toCharArray();
			Map<String,Integer> repeatMap = new HashMap<String,Integer>();
			permutation(ss, 0, repeatMap);
			for (Entry<String, Integer> entry  : repeatMap.entrySet()) {
				if(map.containsKey(entry.getKey())){
					int v = map.get(entry.getKey());
					map.put(entry.getKey(),++v);
				}else{
					map.put(entry.getKey(),0);
				}
			}
			System.out.println(line+"  "+map.get(line));
			line =  buff.readLine();
		}
	
	}
	
	 //获取字符的排列集合  用map剔除重复的排列
	 public static void permutation(char[]ss,int i,Map<String,Integer> map){  
	        if(ss==null||i<0 ||i>ss.length){  
	            return;  
	        }  
	        if(i==ss.length){  
				map.put(new String(ss), 0);
	        }else{  
	            for(int j=i;j<ss.length;j++){
	                char temp=ss[j];//交换前缀,使之产生下一个前缀  
	                ss[j]=ss[i];  
	                ss[i]=temp;  
	                permutation(ss,i+1,map); 
	                temp=ss[j]; //将前缀换回来,继续做上一个的前缀排列.  
	                ss[j]=ss[i];  
	                ss[i]=temp;  
	            }  
	        }  
	    }  

参考地址：http://www.cnblogs.com/longhs/archive/2013/06/14/3135433.html

D.txt



有更好的思想，更快的欢迎指导