把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数 n
输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一
一比较，字典序较小的排在前面。
数据范围
1≤n≤9
输入样例：
输出样例：
1
2
3
4
5
6
| 1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
|
分析
每到一层root含义
和这道题相比，上一题每一层是当前层的数选还是不选从而分叉，本题是选哪一个从而分叉
isVisited
记录当前root是否访问过
data
记录输出序列
count
记录当前root是序列里第几个元素
回溯（往往与递归相辅相成）
每一个root退出递归后，要将isVisited和data，count恢复成原样
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| import java.util.Scanner;
public class Main {
static boolean[] isVisited = new boolean[10];
static int[] data = new int[10];
static int n;
static void dfs(int root, int count) {
if(count == n) {
for(int i = 1; i <= n; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
} else {
for(int i = 1; i <= n; i++) {
if(i != root && isVisited[i] == false) {
isVisited[i] = true;
data[count + 1] = i;
dfs(i, count + 1);
isVisited[i] = false;
data[count + 1] = 0;
}
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
for(int i = 1; i <= n; i++) {
isVisited[i] = true;
data[1] = i;
dfs(i, 1);
isVisited[i] = false;
data[1] = 0;
}
scan.close();
}
}
|
全排列dfs代码模板
作为递归参数传递，记录当前层数的count，当count等于全排列数字位数后，意味着搜索树到底
记录当前这个数是否访问过的isVisited数组
回溯还原
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| static int n;
static StringBuffer stringNum = new StringBuffer();
static boolean[] isVisited = new boolean[MAX];
static void dfs(int count) { //count表示当前层
if(count == n) {
根据题意的其他操作
}
for(int i = 1; i <= n; i++) {
if(isVisited[i] == false) {
isVisited[i] = true;
stringNum.append(i);
dfs(count + 1);
isVisited[i] = false;
stringNum.deleteCharAt(stringNum.length() - 1);
}
}
}
|
举一反三
这一题关键在如何剪枝：首先将数组排个序，然后每一层的root返回后，一直向下遍历到和当前root不相同的位置位置，因为从排列角度来说，只要前一个遍历过了，后一个如果相同，一定是重复的
另外关于java中如何加速读写
使用StreamTokenizer和PrintWriter加速
1
2
3
4
5
6
7
8
9
10
11
| static StreamTokenizer tokenizer;
static PrintWriter writer;
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
writer = new PrintWriter(System.out);
tokenizer = new StreamTokenizer(reader);
static int nextInt(){
tokenizer.nextToken();
return (int) tokenizer.nval;
}
|
使用时就是
分析：
通过枚举解决，难点是如何枚举
题目实际上是n = a + b / c
等式两边同乘以c，得到n * c = a * c + b
先通过dfs全排列找到所有排列，在对排列按照位数划分得到a， b，
剩下的位组成c，代入看是否满足公式
举个例子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| import java.util.Scanner;
public class Main {
static StringBuffer stringNum = new StringBuffer();
static boolean[] isVisited = new boolean[100000];
static int n;
static int m = 9;
static int count = 0;
static int totalNum = 0;
static void dfs(int count) {
if(count == m + 1) {
for(int i = 0; i < stringNum.length(); i++) {
String subStringa = stringNum.substring(0, i);
if(subStringa.length() > 0) {
int a = Integer.parseInt(subStringa);
for(int j = i; j < stringNum.length(); j++) {
String subStringb = stringNum.substring(i, j);
if(subStringb.length() > 0) {
int b = Integer.parseInt(subStringb);
String subStringc = stringNum.substring(j, stringNum.length());
if(subStringc.length() > 0) {
int c = Integer.parseInt(subStringc);
if(n * c == a * c + b) {
totalNum++;
}
}
}
}
}
}
}
for(int i = 1; i <= m; i++) {
if(isVisited[i] == false) {
isVisited[i] = true;
stringNum.append(i);
dfs(count + 1);
isVisited[i] = false;
stringNum.deleteCharAt(stringNum.length() - 1);
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
for(int i = 1; i <= m; i++) {
isVisited[i] = true;
stringNum.append(i);
dfs(2);
isVisited[i] = false;
stringNum.deleteCharAt(0);
count = 0;
}
System.out.println(totalNum);
scan.close();
}
}
|
补充：java中StringBuffer可变字符串的使用
切割子字符串：左闭右开
1
| String subString = stringNum.subString(start, end);
|
字符串转数字
1
| int num = Integer.parseInt(subString)
|