全排列模板类型
1.数组-全排列模板：
private static void f(int []arr,int k) { if(k==arr.length) { return; } for(int i=k;i<arr.length;i++) { swap(arr, i, k); f(arr, k+1); swap(arr, i, k+1); } } public static void swap(int [] a,int i,int k) { int temp = a[i]; a[i] = a[k]; a[k] = temp;
例：13年蓝桥-带分数
> 100 可以表示为带分数的形式：100 = 3 + 69258 / 714 还可以表示为：100 = 82 + 3546 / 197
> 注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。 类似这样的带分数，100 有 11 种表示法。
> 例如： 用户输入： 100 程序输出： 11
> 再例如： 用户输入： 105 程序输出： 6
代码实现：
public class test2 { public static int ans=0; public static int arr[] = {1,2,3,4,5,6,7,8,9}; static int N ; public static void main(String[]args) { Scanner s = new Scanner(System.in); N= s.nextInt(); f(0); System.out.println(ans); } private static void f(int k) { if(k==arr.length) { operation(); } for(int i=k;i < arr.length;i++) { swap(arr, i, k); f(k+1); swap(arr, i, k); } } public static void operation() { for(int i =0;i<=6;i++) { for(int j =i+1;j<=7;j++) { int num1=into1(0,i); int num2=into1(i+1, j); int num3=into1(j+1, arr.length-1); if(num2 % num3 == 0 && num1+num2/num3==N) { ans++; } } } } //一种分段的方法 public static int into1(int i,int j) { int t= 1; int a =0; for(int m =i;m<=j;m++) { a+=arr[m]*t; t*=10; } return a; } public static void swap(int [] a,int i,int k) { int temp = a[i]; a[i] = a[k]; a[k] = temp; } }
2.字符-全排列模板：
class test2 { //字符数组 public static char [] a = {'A','A','2','2','3','3','4','4'}; public void dfs(char [] a,int k) { if(k==a.length) return; for(int i =k;i<a.length;i++) { swap(a, i, k); dfs(a, k+1); swap(a, i, k); } } public void swap(char [] a,int m,int n) { char c = a[m]; a[m] = a[n]; a[n] = c; } public void yunsuan() { // } }
hashset集合特点：无序，唯一性，index0f检索字符第一次出现的位置，lastindex0f() 检索字符最后一次出现的位置
例：14年蓝桥-扑克排序(字符数组)
AA223344，一共4对扑克牌。请你把它们排成一行。
要求：两个A中间有1张牌，两个2之间有2张牌，两个3之间有3张牌，两个4之间有4张牌。
4A3A2432， 2342A3A4
请填写出所有符合要求的排列中，字典序最小的那个。
例如：
22AA3344 比 A2A23344 字典序小。当然，它们都不是满足要求的答案。
请通过浏览器提交答案。“A”一定不要用小写字母a，也不要用“1”代替。字符间一定不要留空格。
import java.util.HashSet; import java.util.Set; class test2 { static Set<String> set = new HashSet<String>(); public static void f(char [] a,int k) { if(k == a.length) { String s = new String(a); if(operation(s)) { set.add(s); } } for(int i = k;i<a.length;i++) { swap(a, i, k); f(a, k+1); swap(a, i, k); } } public static boolean operation(String s) { if(s.lastIndexOf('A')-s.indexOf('A') == 2 && s.lastIndexOf('2')-s.indexOf('2') == 3 && s.lastIndexOf('3')-s.indexOf('3') == 4 && s.lastIndexOf('4')-s.indexOf('4') == 5 ) return true; return false; } public static void swap(char [] a,int i,int j) { char temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void main(String[]args) { char [] a = {'A','A','2','2','3','3','4','4'}; f(a, 0); for(String x:set) { System.out.println(x); } } }
例：16年蓝桥-凑算式
这个算式中A-I代表1-9的数字，不同的字母代表不同的数字。
比如：
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？
class test2 { static int count = 0; public static void f(int [] a,int k) { if(k==9) if(operation(a)) count++; for(int i =k;i<a.length;i++) { swap(a, i, k); f(a,k+1); swap(a, i, k); } } public static void swap(int [] a,int i ,int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } public static boolean operation(int [] a) { int x = a[5]*100+a[6]*10+a[7]; int y = a[8]*100+a[3]*10+a[4]; double result = a[0]+a[1]*1.0/a[2]+x*1.0/y ; if(result == 10) return true; return false; } public static void main(String[]args) { int a [] = {1,2,3,4,5,6,7,8,9}; f(a, 0); System.out.println(count); } }
方格填数
如下的10个格子
+--+--+--+
| | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | |
+--+--+--+
（如果显示有问题，也可以参看【图1.jpg】）
填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
class test2 { static int c = 0; static int a [] = {0,1,2,3,4,5,6,7,8,9}; public static void main(String[]args) { f(a, 0); System.out.println(c); } public static void f(int [] a,int k) { if(k==a.length) { if(operation()) { c++; } } for(int i =k;i<a.length;i++) { swap(a, i, k); f(a, k+1); swap(a, i, k); } } public static boolean operation() { if(Math.abs(a[0]-a[1]) != 1 && Math.abs(a[0]-a[3]) != 1 && Math.abs(a[0]-a[4]) != 1 && Math.abs(a[0]-a[5]) != 1 && Math.abs(a[1]-a[2]) != 1 && Math.abs(a[1]-a[4]) != 1 && Math.abs(a[1]-a[5]) != 1 && Math.abs(a[1]-a[6]) != 1 && Math.abs(a[2]-a[5]) != 1 && Math.abs(a[2]-a[6]) != 1 && Math.abs(a[3]-a[4]) != 1 && Math.abs(a[3]-a[7]) != 1 && Math.abs(a[3]-a[8]) != 1 && Math.abs(a[4]-a[5]) != 1 && Math.abs(a[4]-a[8]) != 1 && Math.abs(a[4]-a[7]) != 1 && Math.abs(a[4]-a[9]) != 1 && Math.abs(a[5]-a[6]) != 1 && Math.abs(a[5]-a[8]) != 1 && Math.abs(a[5]-a[9]) != 1 && Math.abs(a[6]-a[9]) != 1 && Math.abs(a[7]-a[8]) != 1 && Math.abs(a[8]-a[9]) != 1) return true; return false; } public static void swap(int [] a,int i,int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } }
注：参考文献：全排列
