3 .单词重排
【问题描述】
将LANQIAO中的字母重新排列,可以得到不同的单词,如LANQIAO、AAILNOQ等,注意这7个字母都要被用上,单词不一定有具体的英文意义。
请问,总共能排列如多少个不同的单词。
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
解析
求全排列,去重,计数
结果:2520
1、利用Java的Set特性可以自动对目标答案去重
2、利用深度优先遍历实现不断形成新的不同答案排列
代码如下:
import java.util.HashSet; import java.util.Set; public class Main { static char[] a="LANQIAO".toCharArray();//存放所要测试的字符 static Set<String> ans=new HashSet<String>();//存放所有数据结果 static char[] temp=new char[a.length];//测试数组,存放每种结果 static boolean[] vis=new boolean[a.length];//判断数组,判断每个位置是否访问过 public static void main(String[] args) { dfs(0); System.out.println(ans.size()); } public static void dfs(int k) { //如果k==7,说明temp数组已满,将结果存入set中(用set可以去重) if(k==7) { ans.add(new String(temp)); return ; } //深度优先遍历,将每个判断数组进行对反,然后不断回溯,去放开每个位置, for(int i=0;i<a.length;i++) { if(!vis[i]) { temp[k]=a[i]; vis[i]=true; dfs(k+1); vis[i]=false; } } } }